آخر تحديث: 2026-07-13

حجم مرشّح بلوم

مرشّح بلوم وسيلة مُوجَزة للإجابة عن سؤال واحد: «هل رأيتُ هذا العنصر على الأرجح من قبل؟». إنه لا يخزّن أي مفاتيح، بل مصفوفة بتات فحسب، ويبادل احتمالاً صغيراً قابلاً للضبط لإيجابية كاذبة بتوفير كبير في الذاكرة. يحدّد شكله رقمان — عدد العناصر المتوقّع تخزينها، ومدى ما تتحمّله من تطابقات زائفة — ومنهما يُشتقّ مباشرةً الحجم الأمثل لمصفوفة البتات وعدد دوال التجزئة.

الصيغة

من أجل $n$ عنصراً متوقّعاً ومعدّل إيجابيات كاذبة مستهدف $p$، يكون طول مصفوفة البتات التي تقلّل الذاكرة

ويكون عندئذٍ العدد الأمثل لدوال التجزئة

مقرّباً إلى أقرب عدد صحيح. هنا $m$ عدد البتات، و$k$ عدد دوال التجزئة المستقلّة المطبّقة على كل عنصر، و$\ln 2 \approx 0{,}693$. ولمّا كان $p$ احتمالاً أقلّ من 1 فإن لوغاريتمه الطبيعي سالب، فتُنتج الصيغتان قيماً موجبة.

مثال محلول. مرشّح لمليون عنصر ($n = 1{,}000{,}000$) بهدف 1% ($p = 0{,}01$):

فمليون عنصر عند 1% يكلّفان نحو 1.14 ميبي بايت من الذاكرة وسبع دوال تجزئة — أي نحو 9.6 بت لكل عنصر، وهو رقم يثبت لأي عدد من العناصر عند تلك الدقّة.

البتات لكل عنصر وسُلَّم الدقّة

لأن صيغة الحجم خطّية في $n$، فإن تكلفة التخزين لكل عنصر، $m / n = -\ln p / (\ln 2)^2$، تعتمد فقط على المعدّل المستهدف. وهذا يجعلها مقياساً نظيفاً لمقارنة ميزانيات الدقّة.

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

لماذا يهمّ عدد دوال التجزئة

عند تثبيت حجم المصفوفة، يترك عددٌ قليل جداً من دوال التجزئة البتات متناثرة يسهل مطابقتها مصادفةً، بينما يملأ عددٌ كبير جداً المصفوفة بكثافة حتى يكاد كل بتّ يُضبط. تضبط النقطة المثلى نصف البتات وتقع عند $k = (m/n)\ln 2$. ولأن $k$ يجب أن يكون صحيحاً، تقرّبه الحاسبة، ويُعاد حساب معدّل الإيجابيات الكاذبة الفعلي من تلك القيمة المقرّبة:

في المثال أعلاه يعطي $k = 7$ المقرّب نحو 1.004%، أي أعلى قليلاً من هدف 1% لأن $k$ المثالي كان 6.64 لا عدداً صحيحاً.

ما يستطيعه مرشّح بلوم وما لا يستطيعه

لا يُنتج مرشّح بلوم سلبيّة كاذبة أبداً: إن قال إن عنصراً غائب فهو غائب حقاً. الخطأ الوحيد إيجابية كاذبة، وهذه الحاسبة تحدّد معدّلها. تدعم المرشّحات القياسية الإدراج والاستعلام لا الحذف، لأن البتات مشتركة بين العناصر — فمسح بتات عنصر قد يُفسد غيره. وحين يلزم الحذف، يستبدل مرشّح بلوم العدّاد كل بتّ بعدّاد صغير مقابل عدّة أضعاف من الذاكرة، ويوفّر مرشّح الوقواق الحذف بحجم مقارب.

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

التقريب في الممارسة العملية

نادراً ما يكون عدد البتات $m$ الناتج عن الصيغة رقماً مستديراً. تخصّص التنفيذات الفعلية كلمات آلة أو صفحات ذاكرة كاملة، فتقرّب $m$ صعوداً، ممّا يدفع معدّل الإيجابيات الكاذبة المتحقّق أدنى قليلاً من الهدف — وهي مكافأة صغيرة. الحجم المعروض هنا هو الحدّ الأدنى النظري قبل ذلك التقريب.

حسابات ذات صلة

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