مرشح بلوم

ما هو مرشح بلوم؟

مرشح بلوم (Bloom Filter) هو بنية بيانات يمكن استخدامها لبيان ما إذا كان عنصر معين جزءاً من مجموعة أم لا. وعلى الرغم من أنه لا يمكن الجزم بأن عنصراً معيناً جزء من المجموعة، إلا أنه يمكن الجزم بعدم انتمائه إليها بشكل مؤكد.

ونظراً لاستخدامها الفعّال للمساحة التخزينية، تُعد مرشحات بلوم، التي طوّرها بيرتون هاوارد بلوم عام 1970، مرغوبة في تطبيقات متعددة. فهي، على سبيل المثال، أساسية للتحقق المبسّط من الدفعات (Simplified Payment Verification أو SPV) في العديد من عملات الكريبتو (وأبرزها بيتكوين).

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

مثال على مرشح بلوم

لنأخذ مثالاً توضيحياً. لنفترض أن جين، وهي عميلة، لديها معاملة مهمة لا تريد أن يعرف بها جون، وهو مشغّل عقدة كاملة. فتقوم بإنشاء مرشح بلوم قائم على شبكة 10×1، وهو ما سنستخدمه كمثال.

تُشغّل جين خوارزميتي تجزئة (hash) مختلفتين على بيانات المعاملة التي تهمها، فتُعيدان قيمتين بين 0 و9. ولنُطلق عليهما اسم 4 و7. يستلم جون المرشح منها.

وبالنظر إلى هذه الشبكة، لا يمكنك معرفة نوع المعلومات التي أدخلتها جين في المرشح. فإذا كانت لديك مجموعة بيانات، يمكنك تجزئتها ومطابقتها مع المرشح، وفي حال وجود تطابق، فهناك احتمال أن تكون هي البيانات التي طلبتها جين.

ولا يستطيع جون تحديد الجزء الدقيق من البيانات الذي تهتم به جين، إذ من المرجح أن تُخرج مدخلات عديدة القيمتين 4 و7. لذلك، يُعيد جون جميع النتائج المطابقة، وتتولى جين بدورها تصفيتها.