خوارزمية Linear counting: كيف نقدّر عدد القيم المختلفة
كيف نحسب عدد القيم المختلفة في مجموعة بيانات إذا كانت هذه البيانات كثيرة جداً؟ قد تكون لدينا مثلاً خدمة تقيس عدد المستخدمين المختلفين على موقع كبير، أو حتى على النطاق com كله أو ما شابه.
الطريقة الساذجة
لا مشكلة في الأمر، أليس كذلك؟ نمرّ ببساطة على البيانات ونخزّن كل قيمة مرة واحدة في بنية بيانات مناسبة. ويمكننا أن نكتب ذلك في Python تقريباً كما يلي (الشيفرة مطوّلة دون داعٍ، وهذا مقصود):
nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]
def count_unique(values):
found = set()
for item in values:
if item not in found:
found.add(item)
return len(found)
print count_unique(nonunique_values) # 5
إنها تعمل. حسناً، لكن ماذا لو كانت البيانات معرّفات فريدة من النوع v4 طول كل منها 36 محرفاً، وكان عدد هذه المعرّفات الفريدة عشرة ملايين مثلاً؟ سيظل البرنامج يحسب القيمة الصحيحة، لكن كم من الذاكرة سيستهلك؟ لنحاول أن نحسب ذلك. للتبسيط نفرض أننا نخزّن المعرّف uuid فعلاً سلسلةً نصية من 36 محرفاً. فيشغل المعرّف الواحد 36 بايتاً، وتشغل عشرة ملايين معرّف 360 MB.
لنعترف بأنّ هذا ليس قليلاً. ولو كان عدد المعرّفات الفريدة مئة مليون، لوصلنا إلى رتبة الغيغابايتات من الذاكرة المشغولة. ونحن ما زلنا نحسب ما تشغله البيانات وحدها. فإذا أضفنا الحمل الإضافي على الذاكرة (overhead) الذي تحتاجه Python أو JavaScript مثلاً، فقد نصل إلى رتبة الغيغابايتات حتى مع عشرة ملايين معرّف:
هذا ما لا نريده. فما المخرج؟
يمكننا أن نحاول تخزين المعرّفات نفسها بكفاءة أكبر، ويمكننا أن نستعمل لغة C بدلاً من Python فنقلّل متطلبات الذاكرة تقليلاً كبيراً، لكنّ الحل لن يكون مثالياً، وسيظل البرنامج يشغل مساحة هائلة. فيبقى أن نسأل أنفسنا: هل نحتاج فعلاً إلى أن نعرف بدقة تامة أنّ عدد القيم المختلفة هو 9,563,618؟ هل سيحدث شيء لو عملنا بالعدد 9,547,666؟ إن كان الجواب أنّ ذلك مهم وأننا نريد العدد الدقيق، فلا بأس. وإلا فلنعرض طرقاً لتقدير عدد القيم المختلفة في مجموعة البيانات بأكبر دقة وأعلى سرعة وأقل متطلبات من الذاكرة.
دوال التجزئة طوق النجاة
لننظر في دالة تجزئة (hash) تأخذ في مدخلاتها سلسلة نصية وتعيد في مخرجاتها عدداً من n بت. وإذا كنا معتادين على دوال تجزئة «تعيد سلسلة نصية»، فيمكننا ببساطة أن نتخيل أنها تحوّل تلك السلسلة بعد ذلك إلى عدد، ولا صعوبة في ذلك. ويحدد عدد البتات مدى كبر العدد. فالدالة ذات 8 بتات تعيد عدداً يشغل ثمانية بتات، ويمكن أن نخزّن في ثمانية بتات 28 قيمة مختلفة، وهي عادةً الأعداد الصحيحة من 0 إلى 255. وسنعمل فيما يلي بدالة تجزئة ذات 24 بتاً. تعيد هذه الدالة 224 قيمة مختلفة، أي 16,777,216 قيمة.
بدلاً من أن نخزّن القيم نفسها، سنخزّن قيم تجزئتها ذات 24 بتاً. ولتخزين عشرة ملايين قيمة تجزئة ذات 24 بتاً نحتاج إلى 30 MB. وهذا أفضل برتبة كاملة من 360 MB في الحالة السابقة. ويمكن أن تكون الشيفرة كما يلي:
def nhash(item, n):
return hash(item) % (2 ** n)
nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]
def count_unique_using_nhash(values):
found = set()
for item in values:
checksum = nhash(item, 24)
if checksum not in found:
found.add(checksum)
return len(found)
print count_unique_using_nhash(nonunique_values) # 5
الدالة hash دالة مدمجة في Python تعيد عدداً صحيحاً، والدالة nhash تعرض تطبيقاً ساذجاً لدالة تجزئة من n بت. ولا يهم أن نفهم كيف تعمل، لأنها في الحقيقة لا تعمل بصورة صحيحة، فناتجها لا يشغل 24 بتاً، لكنّ ذلك لا يهم الآن، فالمقصود هو المبدأ.
ثم تأتي الدالة count_unique_using_nhash التي تحسب القيم المختلفة. فهي تمرّ على كل القيم، وتحسب قيمة التجزئة لكل منها، وتخزّنها في المتغير found إن لم تكن فيه من قبل.
ومشكلة هذه الطريقة أنّ دالة التجزئة قد تعيد المجموع الاختباري (checksum) نفسه لسلاسل مختلفة، أي قد يحدث التصادم (collision). وكلما كثرت التصادمات، قلّت دقة النتيجة التي نحصل عليها. فالدالة count_unique_using_nhash تعيد دائماً تقريباً عدداً من القيم المختلفة أقل من عددها الفعلي.
وأي دالة تجزئة نختار؟ لا يهم ذلك كثيراً، لكن يُنصح عموماً بإحدى صيغ MurmurHash.
خرائط البتات
من درس أساسيات البرمجة بلغة C يعرف خرائط البتات (bitmap). فكيف يمكن الاستفادة منها؟
نوضّح الفكرة أولاً بمصفوفة (array). فنحن لا نحتاج إلى الاحتفاظ بالمجاميع الاختبارية المحسوبة، بل يمكننا أن ننشئ مصفوفة طولها 224 ونجعل كل عناصرها أصفاراً في البداية. وعندما نصادف مجموعاً اختبارياً (وهو عدد!)، نكتب في هذه المصفوفة عند الموضع checksum الرقم 1، فنسجّل بذلك أننا وجدنا هذا المجموع الاختباري. ويكون عدد العناصر المختلفة عندئذٍ مساوياً تقريباً لعدد الآحاد في هذه المصفوفة. ويمكن أن تكون الشيفرة كما يلي:
def count_unique_using_array(values):
# قائمة طولها 2^24 كل عناصرها أصفار في البداية
array = [0] * (2 ** 24)
for item in values:
array[nhash(item, 24)] = 1
return sum(array)
print count_unique_using_array(nonunique_values)
لكنّ استعمال المصفوفة في هذه الحالة مكلف جداً من حيث الذاكرة، لأننا نحتاج إلى أن نخزّن في كل خلية إما 1 وإما 0. ويمكننا بدلاً من ذلك أن نستعمل مصفوفة بتات (bit array). وللتوضيح: يمكن تخزين العدد الصحيح (integer) مثلاً في 32 بتاً. فإذا حوّلنا العدد 354 إلى النظام الثنائي حصلنا على 101100010. ويُخزَّن العدد 354 في الحاسوب عدداً صحيحاً من 32 بتاً (مع إهمال التفاصيل) كما يلي:
00000000 00000000 00000001 01100010
هذه صيغة لطيفة يمكننا الاستفادة منها، أليس كذلك؟ فنحن نريد في دالتنا أن نخزّن أصفاراً وآحاداً فقط، وقد اكتشفنا للتو أنّ العدد العادي ليس في الحقيقة إلا كومة من الأصفار والآحاد (ككل شيء في الحاسوب تقريباً…). باختصار، يمكننا بالعمليات على مستوى البتات أن نخزّن الواحد بحيث يشغل فعلاً بتاً واحداً.
لنعد إلى دالتنا التي تستعمل المصفوفة. لو أعدنا كتابتها بمصفوفات البتات، لكفتنا لدالة التجزئة ذات 24 بتاً مصفوفة بتات حجمها 224 بت، أي 2 MiB. وهذا تحسين كبير!
ولو استعملنا دالة تجزئة ذات 32 بتاً، لها 232 قيمة مخرجات مختلفة، أي 4,294,967,296 قيمة، لاحتجنا إلى مصفوفة بتات حجمها نصف غيغابايت. وهذا ليس سيئاً إذا علمنا أننا نستطيع به أن نعدّ القيم المختلفة حتى رتبة المليارات.
خوارزمية Linear Counting
ذكرنا أننا عند استعمال دالة التجزئة لا نحصل إلا على تقدير لعدد القيم المختلفة. وتقلّ دقة هذا التقدير كلما اقترب عدد القيم المختلفة من عدد قيم المخرجات المختلفة لدالة التجزئة. ومن المنطقي أنه إذا كانت لدينا مجموعة بيانات فيها خمسة مليارات قيمة مختلفة، فلن نستطيع عدّها بدالة تجزئة ذات 24 بتاً.
لكن يمكن تحسين دقة التقدير الذي نحسبه بدوال التجزئة. وتُستعمل لذلك فكرة بسيطة: كلما زاد عدد القيم المختلفة في مجموعة البيانات، زاد احتمال حدوث التصادمات مع الوقت. (التصادم = مدخلان مختلفان لهما المخرج نفسه من دالة التجزئة، أي المجموع الاختباري نفسه.) سنحسب الآن قليلاً، ولذلك نعرّف بعض المتغيرات:
- نعمل بدالة تجزئة
hمنnبت. - عدد كل المخرجات الممكنة للدالة
hإذن يساوي2n. نرمز لهذا العدد بالحرفm، أي:m=2n. - مصفوفة البتات التي نخزّن فيها المجاميع الاختبارية التي وجدناها نرمز لها بالحرف الكبير
A. وطول المصفوفةAهوm. - إذا مررنا بخوارزميتنا على مجموعة البيانات كلها، فستكون بعض قيم مصفوفة البتات أصفاراً وبعضها آحاداً. وأكثر ما يهمنا النسبة «عدد الأصفار مقسوماً على طول المصفوفة»، وهي تعطينا نسبة الأصفار في مصفوفة البتات. وتساوي هذه النسبة في البداية 1، لأنّ المصفوفة كلها أصفار في البداية. ولو كان التوزيع مناصفة، لكانت النسبة تساوي نصفاً، وهكذا. نرمز لهذه القيمة بالحرف
Zونحسبها بالعلاقةZ = number_of_zeros / m.
ونلاحظ الآن أنه كلما زادت قيمة Z زادت ثقتنا بأنّ تقديرنا لعدد القيم المختلفة دقيق. فإذا مررنا مثلاً على مجموعة بيانات خالية، بقيت مصفوفة البتات أصفاراً كلها، وكانت قيمة Z مساوية 1، فنكون على يقين تام بأنّ عدد العناصر المختلفة في مجموعة بياناتنا يساوي عدد الآحاد في مصفوفة البتات، أي صفراً.
وإذا كانت قيمة Z تساوي 0.99، فهذا يعني أنّ واحداً من مئة من مصفوفة البتات ممتلئ بالآحاد، و 99% من المصفوفة أصفار. وهذا ما زال جيداً، فالأرجح أنه لم يحدث أثناء الحساب كثير من التصادمات، وقد لا نحتاج إلى أي تصحيح أو نحتاج إلى تصحيح طفيف. أما إذا كانت قيمة Z تساوي 0.05، فلم يبقَ إلا 5% من المصفوفة أصفاراً، والأرجح أننا صادفنا أثناء الحساب تصادمات كثيرة جداً، فنحتاج إلى تصحيح كبير.
فكيف نحسب هذا التصحيح؟ نستعين باللوغاريتم، وهو دالة لها الشكل الآتي:
يهمنا الجزء الأحمر على الفترة (0, 1]. فإذا وضعنا قيمة Z على المحور x، فكلما زادت Z اقتربت قيمة y من الصفر. وعلى العكس، كلما صغرت Z صغرت قيمة y. ونحسب التقدير النهائي بضرب هذا العدد في -m. نلاحظ أننا نحصل لقيمة Z صغيرة بما يكفي على عدد أصغر من -1، فإذا ضربناه في -m حصلنا على تقدير أكبر من m، أي قدّرنا أنّ عدد القيم المختلفة أكبر من عدد كل المجاميع الاختبارية الممكنة التي يمكن أن تخرج من دالة التجزئة h.
والصيغة الكاملة لحساب العدد p للقيم المختلفة هي:
ويمكن أن يكون التطبيق (دون مصفوفات البتات، بمصفوفات عادية فقط) كما يلي:
from uuid import uuid4
from math import log
number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values
def nhash(item, n):
return hash(item) % (2 ** n)
def count_unique_using_array(values, n):
array = [0] * (2 ** n)
for item in values:
array[nhash(item, n)] = 1
return sum(array)
def linear_counting(values, n):
estimate = count_unique_using_array(values, n)
m = 2 ** n
number_of_zeros = m - estimate
Z = float(number_of_zeros) / m
# log هنا هو اللوغاريتم الطبيعي للأساس e
p = (-m) * log(Z)
p = int(round(p))
print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
(estimate, m, number_of_zeros, Z, p)
return p
print "Cardinality: %s" % linear_counting(nonunique_values, 16)
نحسب في الدالة linear_counting أولاً التقدير الأول بالخوارزمية السابقة التي تستعمل دالة تجزئة من n بت. ثم نحسب نسبة الأصفار في المصفوفة ونجري التصحيح وفق الصيغة. واللوغاريتم في الشيفرة هو اللوغاريتم الطبيعي. ويحتوي المتغير nonunique_values على number_of_unique_values سلسلة نصية مختلفة، أي توجد في القائمة nonunique_values في هذا المثال عشرة آلاف قيمة مختلفة. والشيفرة الغريبة في السطر السادس تجعل في المصفوفة قيماً متكررة: فنحن ببساطة نُلحق بنهاية القائمة القائمة نفسها، فتظهر كل قيمة في المصفوفة مرتين. ثم نبدأ الحساب. وينبغي في الحالة المثالية أن تعيد الدالة أنّ القائمة تحتوي على عشرة آلاف قيمة مختلفة. المخرجات:
Debug info: estimate=9289, m=65536, number_of_zeros=56247,
Z=0.858261108398, p=10017
Cardinality: 10017
لأنّ القائمة nonunique_values تُولَّد في كل مرة من جديد، فستختلف النتائج من استدعاء إلى آخر. استعملنا دالة تجزئة ذات 16 بتاً. ونرى أنّ التقدير الأول من الدالة count_unique_using_array كان أنّ القائمة تحتوي على 9289 قيمة مختلفة. وحسّنّا هذا التقدير بالتصحيح إلى 10,017، وهذا جيد إلى حد معقول: فتقديرنا أكبر بنسبة 0.17% فقط، بينما كان قبل ذلك أصغر بنسبة 7.11%، وهذا كثير.
ولو أخذنا دالة تجزئة «أكبر»، ذات 24 بتاً مثلاً، لحصلنا على نتيجة أدق:
Debug info: estimate=9997, m=16777216, number_of_zeros=16767219,
Z=0.999404132366, p=10000
Cardinality: 10000
كان التقدير الأصلي نفسه جيداً، ووصل التحسين إلى عشرة آلاف تماماً. وللتوضيح يمكننا أن نجرّب مليون معرّف فريد، أي number_of_unique_values = 1000000. وبدالة التجزئة ذات 24 بتاً نصل إلى النتائج الآتية:
Debug info: estimate=971033, m=16777216, number_of_zeros=15806183,
Z=0.94212192297, p=1000267
Cardinality: 1000267
نتيجة لا بأس بها. ولو طبّقنا ذلك بمصفوفة بتات، لما استهلكت المصفوفة إلا الميغابايتين المذكورين (إضافة إلى ما تستهلكه اللغة). وهذا جيد إلى حد بعيد. لكن يمكننا أن نفعل أفضل من ذلك! بل أفضل بكثير، وهذا موضوع المرة القادمة.
وفي الأثناء يمكن قراءة المقالة A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]، أو الانتقال إلى الجزء التالي من السلسلة: خوارزمية min-value.
المحتويات: خوارزمية Linear counting: كيف نقدّر عدد القيم المختلفة, خوارزمية Min Value: كيف نقدّر عدد القيم المختلفة, خوارزمية LogLog: كيف نقدّر عدد القيم المختلفة, خوارزمية HyperLogLog: كيف نقدّر عدد القيم المختلفة بدقة عالية