خوارزمية HyperLogLog: كيف نقدّر عدد القيم المختلفة بدقة عالية
تستمر سلسلة الخوارزميات التي تقدّر عدد القيم المختلفة في مجموعة متعددة بمقالة عن خوارزمية HyperLogLog، وهي من أحدث ما وصل إليه هذا المجال (state of the art). لكنّ كل الأفكار التي تقوم عليها هذه الخوارزمية مأخوذة من خوارزمية LogLog التي وصفناها من قبل، ولذلك ينبغي قبل متابعة القراءة التأكد من فهم خوارزمية LogLog جيداً.
كانت لخوارزمية LogLog مشكلتان رئيسيتان:
القيم المتطرفة
التقدير الناتج عن خوارزمية LogLog شديد التأثر بالقيم المتطرفة (outliers)، أي القيم البعيدة جداً عن باقي القيم. فكثيراً ما يحدث أن تكون معظم الأطوال العظمى للواحق الصفرية في المجموعات متقاربة، تتراوح مثلاً بين 12 و 15، ثم فجأة يكون طول إحدى اللواحق الصفرية 27. هذا الفرق الكبير يُفسد التقدير الناتج لعدد القيم المختلفة، لأنّ الوسط الحسابي المعتاد لا يتعامل معه جيداً. وهو في جوهره المبدأ نفسه الذي يجعل بعض كبار المديرين يرفعون متوسط الراتب في البلد برواتبهم المرتفعة.
حاول مؤلفو الخوارزمية حل ذلك بالتخلّص من القيم المتطرفة، فلم يُدخلوا في الوسط الحسابي بعض القيم العظمى الأعلى، لكنّ ذلك لم يكن حلاً جيداً. ثم جرّبوا طريقة أخرى: استعملوا بدلاً من الوسط الحسابي الوسط التوافقي، وخواصه أفضل بكثير عندما تكون لدينا قيم بعيدة عن المتوسط.
نتائج سيئة جداً للأعداد الكاردينالية الصغيرة
نتائج خوارزمية LogLog سيئة جداً عندما تقدّر العدد الكاردينالي لمجموعات متعددة صغيرة. فإذا كان في المجموعة المتعددة عدد قليل من العناصر المختلفة، أعادت LogLog تقديراً كبيراً بلا معنى. وقد حلّ المؤلفون ذلك بذكاء: إذا كانت في المدخلات مجموعة متعددة ذات عدد كاردينالي صغير، فلا تُستعمل خوارزمية LogLog، بل خوارزمية أخرى تماماً، وهي خوارزمية Linear counting المعروفة. حسناً، لكن كيف نعرف أنّ في المدخلات مجموعة متعددة ذات عدد كاردينالي صغير، ونحن لا نعرف هذا العدد أصلاً؟
نترك خوارزمية LogLog تقدّر عدد العناصر المختلفة، فإذا وجدنا أنّ هذا التقدير صغير نسبياً، تخلّصنا منه وحسبناه من جديد بخوارزمية Linear counting. ولنتذكر سريعاً كيف تعمل خوارزمية Linear counting. في البداية نحجز مصفوفة (بتات) صفرية ذات حجم محدد مسبقاً، يكون عادةً قوة للعدد اثنين. ثم نمرّ على كل عناصر المجموعة المتعددة، ونحسب قيمة التجزئة لكل منها، ونحوّلها إلى عدد صحيح i من 0 إلى طول المصفوفة ناقص 1. ونخزّن في المصفوفة الرقم 1 عند الموضع i. وفي النهاية نحسب عدد الأصفار والآحاد في المصفوفة، ونقدّر العدد الكاردينالي بصيغة بسيطة.
لكنّ خوارزمية LogLog لا تستعمل أي مصفوفة بتات «تخزّن» فيها قيم التجزئة المحسوبة. بل تستعمل مصفوفة تحتفظ فيها بالأطوال العظمى للواحق. ويمكن أن تكون المصفوفة مثلاً كما يلي:
[2, 5, 9, 0, 5, 4, 4, 0]
وكل عدد فيها يمثّل الطول الأعظم للاحقة الصفرية في مجموعة من قيم التجزئة المحسوبة. والقيمة غير الصفرية في الموضع ذي الدليل i تعني حتماً أنه يوجد بين قيم المجموعة المتعددة عنصر تساوي قيمة تجزئته (ذات البتات الثلاثة) العدد i. بعبارة أخرى، يمكننا أن نحوّل هذه المصفوفة إلى مصفوفة بتات لخوارزمية Linear counting، بأن نترك الأصفار كما هي ونحوّل كل عدد موجب إلى واحد. فنحصل من المصفوفة السابقة على مصفوفة البتات:
[1, 1, 1, 0, 1, 1, 1, 0]
ويمكننا الآن أن نطبّق خوارزمية Linear counting ونقدّر بها العدد الكاردينالي.
لكنّ في ذلك عقبة واحدة. فنحن نخزّن في المصفوفة الطول الأعظم للاحقة الصفرية، فماذا لو انتهت كل قيم التجزئة في مجموعة ما بالواحد؟ إذا استعملنا مثلاً آخر ثلاثة بتات معرّفاً للمجموعة التي تنتمي إليها قيمة التجزئة، فإنّ طول اللاحقة الصفرية لقيمة التجزئة «01001100» يساوي صفراً، لأنّ المتجه «01001» ينتهي بالواحد. فنخزّن في مصفوفة القيم العظمى عند الموضع 4 (1002=410) صفراً. لكنّ ذلك يظهر في خوارزمية Linear counting على أننا لم نجد قيمة تجزئتها 4، وهذا غير صحيح.
لذلك نعدّل الخوارزمية بحيث لا تخزّن في مصفوفة القيم العظمى طول أطول لاحقة صفرية، بل موضع «أول واحد من اليمين» (للتوضيح: نبدأ الترقيم من الواحد)، وهذا يعادل إضافة واحد إلى طول اللاحقة الصفرية. وبذلك يصبح الصفر في الموضع i دالاً على أنه لا توجد قيمة تساوي قيمة تجزئتها i، ويمكننا عندئذٍ أن نستعمل هذه المصفوفة لخوارزمية Linear counting.
تطبيق خوارزمية HyperLogLog
خطوة بخطوة:
def alpha(num_buckets):
return (0.7213 / (1 + 1.079 / num_buckets))
تعيد الدالة alpha تصحيحاً للتقدير المحسوب، وهذا ما نعرفه من المرة السابقة، غير أنّ قيمة alpha في خوارزمية HyperLogLog تتوقف على عدد المجموعات.
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
دالة تعيد عدد البتات الصفرية في نهاية العدد.
def count_maxims(values, k):
num_buckets = 2 ** k
max_zeroes = [0] * num_buckets
for value in values:
h = hash(value)
bucket_index = h & (num_buckets - 1)
bucket_hash = h >> k
num_zeros = trailing_zeroes(bucket_hash) + 1
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
return max_zeroes
دالة تمرّ على كل القيم، وتقسمها إلى num_buckets مجموعة، وتحسب لكل مجموعة موضع أول واحد من اليمين (طول أطول لاحقة صفرية زائد واحد).
def linear_counting(number_of_ones, num_buckets):
number_of_zeros = num_buckets - number_of_ones
Z = float(number_of_zeros) / num_buckets
p = (-num_buckets) * log(Z)
return p
دالة معدّلة قليلاً لحساب خوارزمية Linear counting.
def estimate_cardinality(values, k):
num_buckets = 2 ** k
max_zeroes = count_maxims(values, k)
estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)
if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
return linear_counting(number_of_ones, num_buckets)
else:
return estimate
الدالة الرئيسية التي تجمع ذلك كله. فهي تحسب أولاً التقدير بخوارزمية LogLog المعدّلة، وتستعمل في السطر الرابع الوسط التوافقي بدلاً من الوسط الحسابي، ثم تطبّق التصحيح بخوارزمية Linear counting إذا كان التقدير المحسوب أصغر من 2.5 ضعف عدد المجموعات (فنتوقع عندئذٍ أن يكون تقدير LogLog المعتاد أسوأ من تقدير Linear counting)، وإذا كان في مصفوفة القيم العظمى صفر واحد على الأقل (فالمصفوفة التي كل عناصرها آحاد لا يمكن استعمالها في خوارزمية Linear counting، كما في المقالة السابقة). فما نتائج خوارزمية HyperLogLog؟
نشغّل شيفرة اختبار تقدّر العدد الكاردينالي لمجموعات أعدادها الكاردينالية على التوالي 10 و 100 و… و 1,000,000:
for x in range(1, 7):
num_values = 10**x
values = (str(uuid4()) for _ in xrange(num_values))
cardinality = estimate_cardinality(values, 14)
print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)
النتائج:
Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408
نرى أنّ النتائج تنحرف دائماً عن النتيجة الصحيحة بأقل من واحد في المئة. وهذا جيد!
تحسينات أخرى لخوارزمية HyperLogLog
حظيت خوارزمية HyperLogLog بعدة تحسينات أخرى مثيرة للاهتمام. ومن المشكلات الباقية ارتفاع متطلبات الذاكرة. قد يبدو هذا غريباً، فقد أثنينا في المرة السابقة على متطلبات الذاكرة كثيراً، وحسبنا أنّ تخزين مصفوفة القيم العظمى لا يحتاج إلا إلى 768 بايتاً. لكنّ المشكلة تظهر عندما لا نريد حساب العدد الكاردينالي لمجموعة متعددة ضخمة واحدة، بل لعدة ملايين من المجموعات المتعددة الصغيرة بالتوازي، أو عندما نريد الاحتفاظ بمصفوفات القيم العظمى المحسوبة في قاعدة بيانات لاستعمالات لاحقة.
فلو حسبنا مثلاً في آن واحد العدد الكاردينالي لمليار مجموعة متعددة، لاحتجنا بالتطبيق الحالي إلى 1,000,000,000 مرة 768 بايتاً، أي 768 GB. وهذا ليس سيئاً من جهة… لكننا من جهة أخرى نستطيع تطبيق HyperLogLog بطريقة أفضل.
التمثيل المتناثر
لنفرض أننا نضع k=12، أي نستعمل 12 بتاً لتعريف المجموعات، فنحصل على 212 مجموعة مختلفة من قيم التجزئة. علينا في بداية الخوارزمية أن نحجز مصفوفة طولها 4096 (كما في السطر 3 من الدالة count_maxims). ولنفرض أنّ مجموعتنا المتعددة تحتوي على ثلاثة عناصر مختلفة. فهذا يعني أننا نضع قيماً في ثلاثة مواضع مختلفة من المصفوفة، وتبقى القيم الأخرى في المصفوفة، وعددها 4093، أصفاراً، أي أننا لم نستعمل هذه القيم إطلاقاً. وهذا ليس فعّالاً، أليس كذلك؟
ولكي نتجنّب مصفوفة معظمها صفري وغير مستعمل، ومع ذلك تشغل جزءاً ثميناً من الذاكرة، يمكننا في البداية أن نخزّن القيم في صورة أزواج [index, value]. ولنأخذ مثالاً للتوضيح. هذه المصفوفة
[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
يمكننا أن نمثّلها بكفاءة أكبر بكثير من حيث الذاكرة بزوجين:
[0, 7], [4, 12]
فبدلاً من أن نحجز في الذاكرة كومة من المساحة غير المستعملة، يمكننا أن نحجز تدريجياً المساحة التي نحتاجها فعلاً فقط. نسمّي هذا التمثيل التمثيل المتناثر (sparse). لكنّ هذا التمثيل يصبح عند لحظة ما أكثر استهلاكاً للذاكرة من التخزين في المصفوفة، وعندئذٍ يمكننا أن نحوّل التمثيل المتناثر إلى مصفوفة عادية دون فقدان أي معلومة.
الإزاحات
أظهرت التجربة أنّ كل القيم في المصفوفة متقاربة تقريباً. فمصفوفة القيم العظمى تكون عادةً مثلاً كما يلي:
[12, 13, 11, 13, 15, 12, 14, 11, 12, ..., 13, 14, 11]
كل القيم تدور حول العدد 13. ومن الاستراتيجيات الأخرى لتصغير حجم مثل هذه المصفوفة أن نطرح من كل عنصر قيمة ثابتة، تُسمّى الإزاحة (offset)، ونحفظها. فيمكننا مثلاً أن نطرح العدد 8:
[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]
عندئذٍ تستهلك كل قيمة في المصفوفة مقداراً أقل من الذاكرة: ففي المصفوفة الأولى نحتاج إلى تخزين الأعداد من 0 إلى 15، ونحتاج لذلك إلى 4 بتات، أما المصفوفة الثانية فتكفيها 3 بتات، لأننا نخزّن الأعداد من 0 إلى 7 فقط. وهذا يفترض بالطبع تطبيق المصفوفة على مستوى البتات المفردة. وعندما نريد قراءة القيم من المصفوفة، علينا أن نضيف إليها القيمة المحفوظة من جديد.
…وكومة من التحسينات الأخرى. وما زال البحث في هذا المجال مستمراً، ولذلك يمكننا أن نتطلع إلى أفكار أخرى مثيرة للاهتمام. وسنتحدث في المرة القادمة عن اتحاد متجهات HyperLogLog وتقاطعها، ثم في المستقبل القريب عن سبب حاجتنا أحياناً إلى تخزين مليارات من متجهات HyperLogLog.
الروابط والمصادر
- يمكن الاطلاع على التطبيق الكامل على GitHub.
- HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF]: المقالة الأصلية التي قُدّمت فيها خوارزمية HyperLogLog.
- HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF]: نسخة محسّنة من خوارزمية HyperLogLog الأصلية، تضيف مثلاً التمثيل المتناثر المذكور.
المحتويات: خوارزمية Linear counting: كيف نقدّر عدد القيم المختلفة, خوارزمية Min Value: كيف نقدّر عدد القيم المختلفة, خوارزمية LogLog: كيف نقدّر عدد القيم المختلفة, خوارزمية HyperLogLog: كيف نقدّر عدد القيم المختلفة بدقة عالية