✖

خوارزمية LogLog: كيف نقدّر عدد القيم المختلفة

بعد الجزأين السابقين عن خوارزمية Linear Counting وخوارزمية Min Value، نصل أخيراً إلى خوارزمية LogLog، وهي من أفضل الخوارزميات الاحتمالية لتقدير عدد القيم المختلفة في مجموعة بيانات. ولا يتفوّق عليها إلا أختها الصغرى HyperLogLog المبنية عليها، لكنّ الحديث عنها في المرة القادمة.

لنعد صياغة المسألة. في المدخلات مجموعة بيانات أو مجموعة متعددة (multiset)، مثل مصفوفة من المعرّفات أو مولّد لها. وبعض القيم في هذه المصفوفة متكررة، ونريد أن نحسب عدد القيم المختلفة فيها. نسمّي هذا العدد العدد الكاردينالي (cardinality). ونتوقع أن يكون هذا العدد كبيراً جداً، وإلا أمكننا أن نستعمل الخوارزميات التقليدية.

فكرة خوارزمية LogLog

لنتخيل أنّ لدينا مجموعة من المتجهات الثنائية. والأمر بسيط: فالسلسلة 0001011001001100 مثلاً متجه ثنائي طوله 16. لنفرض أنّ لدينا متجهات ثنائية طولها 32، وعددها مليون متجه، وكلها مولّدة عشوائياً تماماً. فكم متجهاً سينتهي بالرقم صفر؟

لا يمكننا بالطبع أن نعرف ذلك بدقة، لكن إذا ولّدنا المتجهات عشوائياً فعلاً، فينبغي أن ينتهي نصفها تقريباً بالصفر، أي 500 ألف متجه. وكم متجهاً سينتهي بالسلسلة «00»؟ الربع. وبالسلسلة «000»؟ الثُّمن. وهكذا. ويمكننا أن نمثّل ذلك تقريباً كما يلي:

نمط المتجه        النسبة من كل المتجهات
...xxxxxx0        50%
...xxxxx00        25%
...xxxx000        12.5%
...xxx0000        6.25%
     ...          ...

إذا سألنا عن لاحقة (suffix) طولها d (واللاحقة سلسلة تنتهي بها سلسلة أخرى، وهي عكس البادئة)، فإننا نتوقع أن نجد v متجهاً تنتهي بهذه اللاحقة. ونحسب القيمة v بالعلاقة:

v=12d⋅N

حيث N عدد كل المتجهات في المجموعة. فاللاحقة التي طولها 3 (مثل …010) ينبغي أن تظهر في 1/2^3 N = 1/8 N من المتجهات، أي في 12.5% من كل المتجهات.

لنقم الآن بتجربة ذهنية صغيرة مدهشة. لتكن لدينا مجموعة متعددة من 1024 متجهاً مختلفاً. فكم متجهاً ينبغي أن ينتهي باللاحقة 0000000000؟ (عشرة أصفار) نعوّض في الصيغة فنحصل على

v=1210⋅1024=11024⋅1024=1

متجه واحد! ففي ألف متجه ثنائي مولّد عشوائياً ينبغي أن يوجد متجه واحد ينتهي بعشرة أصفار. فكيف نستعمل هذه المعلومة لتقدير عدد العناصر المختلفة؟ يمكننا أن نسير في الاتجاه المعاكس. فماذا لو مررنا على كل المتجهات الثنائية في المدخلات ووجدنا أنه يوجد في المجموعة متجه واحد فقط ينتهي بعشرة أصفار؟ عندئذٍ يمكننا أن نقدّر أنّ المجموعة كانت تحتوي على 1024 متجهاً!

التعميم وبناء الخوارزمية

الهدف أن نجد لاحقة لا يحتويها إلا متجه واحد، وأن تكون هذه اللاحقة أقصر ما يمكن. لكنّ هذا صعب جداً، لأننا لكي نجد مثل هذا المتجه فعلاً سيكون علينا أن نخزّن كل اللواحق، وهذا ما لا نريده لأنه يستهلك ذاكرة كبيرة جداً. لذلك نكتفي بالبحث عن أطول متتالية من الأصفار في نهاية المتجه.

نمرّ إذن على كل المتجهات، ونحسب لكل متجه عدد الأصفار في نهايته، ونحتفظ في متغير واحد بأكبر هذه القيم. وعندما ننتهي من المرور على كل المتجهات، نعرف طول أطول لاحقة مكوّنة من الأصفار وحدها. نرمز لهذا الطول بالحرف d. نعدّل الآن الصيغة السابقة بحيث نعزل المتغير N، أي ليصبح مخرج الخوارزمية لا مدخلها. ونعوّض عن v بالعدد واحد، لأننا نتوقع أن نجد متجهاً واحداً من هذا النوع، أي نتوقع أن يكون v=1.

v=N2dv⋅2d=N2d=N

فإذا وجدنا الطول d لأطول لاحقة صفرية، قدّرنا العدد الكاردينالي بالصيغة N=2d.

كيف نحصل على متجهات ثنائية عشوائية؟

تعمل الخوارزمية الآن مع المتجهات الثنائية العشوائية، لكن كيف نطبّق هذه الطريقة على بيانات حقيقية؟ كالعادة نستعمل هنا أيضاً دالة تجزئة مناسبة. فإذا كانت في المدخلات مجموعة بيانات، كالمعرّفات (سلاسل نصية)، فإننا نجزّئها أولاً. ومخرج دالة التجزئة ذات n بت هو n بت، تبدو من الناحية العملية كمتجهات ثنائية مولّدة عشوائياً.

ويمكننا الآن أن نكتب خوارزميتنا:

def trailing_zeroes(number):
    if number == 0: 
        return 0

    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def count_unique(values):
    max_zero_suffix_length = 0
    for value in values:
        zeroes_length = trailing_zeroes(hash(value))
        max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
    return 2 ** max_zero_suffix_length

تعيد الدالة trailing_zeroes عدد الأصفار في نهاية العدد. وكيف تفعل ذلك؟ إن لم يتضح ذلك من الشيفرة فالأفضل عدم السؤال. وما نسبة نجاح الدالة؟ لمجموعة تحتوي على مئة ألف عنصر مختلف أعادت الدالة التقدير 524,288.

حسناً…

هذا ليس جيداً تماماً، أليس كذلك؟ لكن لا بأس! سنحاول تحسين الخوارزمية تماماً كما فعلنا في خوارزمية Min Value السابقة. فنقسم بيانات المدخلات إلى عدة مجموعات منفصلة، ونحسب لكل مجموعة أطول لاحقة صفرية، ثم نحسب متوسط طول اللاحقة الصفرية ونستعمله لتقدير عدد القيم المختلفة.

يمكننا مثلاً أن نقرر أنّ آخر بتّين من كل متجه يحددان رقم المجموعة التي ينتمي إليها المتجه. فهذه المتجهات الستة

1101110111111011     1110110010100101
1011001111110010     1111101100000011
1010101000100000     0110010110011000

يمكن تقسيمها إلى أربع مجموعات بحسب نهايتها:

00                   01              
1010101000100000     1110110010100101
0110010110011000                     

10                   11
1011001111110010     1101110111111011
                     1111101100000011

ثم نحسب طول أطول لاحقة صفرية في كل متجه، متخطّين البتات التي استعملناها رقماً للمجموعة. ونميّز «اللواحق» الصفرية باللون الأخضر:

00                   01                     
1010101000100000     1110110010100101    
0110010110011000

10                   11
1011001111110010     1101110111111011
                     1111101100000011

00: 3                01: 0
10: 2                11: 6

في النهاية أطوال أطول اللواحق الصفرية في كل مجموعة. ويمكننا أن نحسب من هذه اللواحق الوسط الحسابي، فنحصل على 2.75. نعوّض بهذه القيمة في الصيغة فنحصل على

22.75≈6.727

فنحصل على متوسط عدد العناصر المختلفة في كل مجموعة. وهذا بالطبع لا يطابق الواقع إطلاقاً، لكن لا داعي للقلق، فخوارزمية LogLog تعطي نتائج سيئة جداً للمجموعات الصغيرة.

ولكي نقدّر العدد الكاردينالي للمجموعة كلها، علينا أن نضرب هذه القيمة في عدد المجموعات: 6.727 × 4 = 26.908. فحسبت الخوارزمية أنّ في المجموعة 27 قيمة مختلفة تقريباً. وكان فيها ست قيم، فالتقدير بعيد تماماً، لكنّ ذلك لا يهم الآن فعلاً.

تطبيق الخوارزمية

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(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)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets

يحدد الوسيط k عدد البتات التي تُؤخذ دليلاً للمجموعة. وهذا الوسيط يحدد دقة الخوارزمية: فكلما زادت k زادت الدقة. ويُحفظ في المتغير bucket_index رقم المجموعة. فكيف يعمل ذلك السحر في الطرف الأيمن من إشارة المساواة؟

في المتغير num_buckets عدد المجموعات، وهو دائماً قوة للعدد اثنين. فإذا كان مثلاً k = 3، كان num_buckets=8. والعدد 8 في النظام الثنائي هو 1000. فإذا طرحنا منه واحداً حصلنا على العدد 7، وهو 0111. فبعد طرح الواحد من num_buckets نحصل دائماً على عدد في نهايته k من الآحاد وقبلها أصفار فقط. ثم ننفّذ عملية AND على مستوى البتات (وهي العامل &). وللمتجه 1110110010100101 تكون هذه العملية كما يلي:

  1110110010100101
& 0000000000000111
------------------
  0000000000000101

والغرض من هذا السحر كله أن نحصل على عدد في بدايته أصفار فقط، وآخر k بت منه مطابقة لآخر k بت من قيمة التجزئة h.

ثم نحسب bucket_hash، وهي قيمة التجزئة الأصلية بعد حذف آخر k بت منها، وذلك بإزاحة قيمة التجزئة كلها k بت إلى اليمين. وتعمل الإزاحة ببساطة بنقل كل بتات العدد k بت إلى اليمين، وتُملأ خانات العدد من اليسار بالأصفار. (والإزاحة إلى اليمين ببت واحد تعمل كقسمة العدد على اثنين وإهمال الباقي.) فمن المتجه 1110110010100101 نحصل بعد الإزاحة بثلاثة بتات على 0001110110010100. ويُخزَّن هذا المتجه في المتغير bucket_hash.

ثم نحسب عدد الأصفار في نهاية هذا المتجه، فإذا كانت هذه القيمة أكبر من القيمة العظمى الحالية المخزّنة في المصفوفة max_zeroes عند الموضع bucket_index، استبدلناها بها.

وفي النهاية نحسب متوسط عدد الأصفار في كل المجموعات، ونحسب متوسط عدد العناصر المختلفة في كل مجموعة (2 ** average_max_zeros). وبما أنّ لدينا num_buckets مجموعة، نضرب هذه القيمة في عدد المجموعات، فنحصل على التقدير النهائي لعدد العناصر المختلفة. ولم يكن الأمر مؤلماً. وهذه نتائج عدة مجموعات بيانات تحتوي كل منها على 250,000 قيمة مختلفة، مع k=10:

331774.56203
323349.39265
307343.444439
309430.914045
294512.379123

ما زالت النتائج خاطئة! لكننا اقتربنا كثيراً، فلا داعي للقلق. نلاحظ أنّ كل النتائج أكبر من النتيجة الصحيحة. ففي أثناء الخوارزمية تتراكم أخطاء مختلفة، ولذلك يكون التقدير أكبر من النتيجة الصحيحة بوضوح. لكنّ هذه الأخطاء ثابتة إلى حد كبير، ويمكن تقدير مقدار الخطأ الحاصل. فإذا ضربنا التقدير في ثابت التصحيح 0.79402، حصلنا على نتائج أفضل بكثير:

263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445

وجرّبنا أيضاً مجموعة متعددة عددها الكاردينالي مليون، فكانت النتائج:

النتيجة               الخطأ
1017297.17411         1.01729717411
1022820.99717         1.02282099717
984108.725487         0.984108725487
1018675.32683         1.01867532683
1007020.2853          1.0070202853

ممتاز! فالخطأ أقل من 2.5%، وهذا أداء جيد. وهذه هي خوارزمية LogLog. ويكون التطبيق النهائي مع ثابت التصحيح كما يلي:

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(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)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets * 0.79402

أما كيف نعدّل هذه الخوارزمية لنحصل على خوارزمية HyperLogLog الشهيرة، وهي الأفضل على الإطلاق، فسنتحدث عنه في المرة القادمة. وننظر الآن في متطلبات الخوارزمية من الذاكرة.

متطلبات الذاكرة

الخوارزمية فعّالة جداً من حيث الذاكرة المشغولة. فكل ما نحتاج إلى حفظه هو المصفوفة التي تحتفظ بالقيم العظمى. ويتوقف طول هذه المصفوفة على القيمة k، أي على عدد بتات المتجه التي نأخذها دليلاً للمجموعة. فلقيمة معيّنة k يكون لدينا 2k مجموعة مختلفة، ولذلك يكون طول مصفوفة القيم العظمى 2k. وقد سمّينا هذه القيمة في التطبيق num_buckets.

وما الحجم الذي تحتاجه الخلية الواحدة من المصفوفة؟ سنخزّن فيها أطوال اللواحق الصفرية. ويمكن أن نقول مسبقاً إنّ قيمة التجزئة ذات 64 بتاً تكفي على الأرجح لكل المجموعات المتعددة التي يمكن تصوّرها في العالم، ولذلك يجب أن نستطيع أن نخزّن في هذه المصفوفة الأعداد من 0 (متجه كله آحاد) إلى 64 (متجه كله أصفار). وإذا فرضنا أيضاً أنّ k أكبر من الصفر دائماً، فيكفينا أن نخزّن الأعداد من 0 إلى 63. ولذلك تكفينا 6 بتات، لأنّ 26 = 64.

نعم، تكفينا «مصفوفة» حجم الخلية الواحدة فيها 6 بتات. ويمكن أن نضيف أنّ القيمة k=10 تكفي لتقدير العدد الكاردينالي تقديراً جيداً حتى رتبة مئات الملايين. والخوارزمية بهذا الإعداد تنشئ مصفوفة حجمها 210 = 1024، تشغل كل خلية فيها 6 بتات. فتشغل هذه المصفوفة إجمالاً 6144 بتاً، أي 768 بايتاً. أقل من كيلوبايت واحد.

وهذا كل شيء.

لا نحتاج إلى تخزين أي شيء آخر، فيمكننا أن نتخلّص من قيم التجزئة المحسوبة فوراً، ويكفينا أن نعرف عدد الأصفار في نهاية المتجه.

نلاحظ أننا لو استعملنا دالة تجزئة أكبر، تعيد مثلاً 128 بتاً، لما تغيّرت متطلبات الذاكرة كثيراً. فسنحتاج إلى تخزين الأعداد من 0 إلى 127، وتكفينا لذلك 7 بتات. فالوسيط k، أي عدد المجموعات، هو ما يحدد أساساً متطلبات الذاكرة.

تناسب خوارزمية LogLog خصوصاً الحالات التي نحتاج فيها إلى عدّ مجموعات متعددة ذات عدد كاردينالي كبير جداً. وكما رأينا في المثال البسيط السابق، لا تتعامل LogLog بصورة مثالية مع المجموعات المتعددة ذات العدد الكاردينالي الصغير. لكن يمكن معالجة ذلك أيضاً، مثلاً بأن نستعمل للتقدير خوارزمية أخرى إذا وجدنا أنّ العدد الكاردينالي للمجموعة المتعددة صغير، كخوارزمية Linear Counting التي وصفناها من قبل. وسنتحدث عن ذلك أيضاً في المرة القادمة.

المصادر:

المحتويات: خوارزمية Linear counting: كيف نقدّر عدد القيم المختلفة, خوارزمية Min Value: كيف نقدّر عدد القيم المختلفة, خوارزمية LogLog: كيف نقدّر عدد القيم المختلفة, خوارزمية HyperLogLog: كيف نقدّر عدد القيم المختلفة بدقة عالية