30. مرشحات بلوم (Bloom Filters) (مقدمة في الهياكل الاحتمالية)
في حين أن معظم هياكل البيانات تضمن الصحة، فإن مرشحات Bloom Filters تتاجر بالدقة المضمونة مقابل كفاءة مذهلة في المساحة، باستخدام الاحتمالية.
المفهوم
مرشح Bloom Filter هو هيكل بيانات احتمالي وموفر للمساحة يستخدم لاختبار ما إذا كان العنصر ليس بالتأكيد عضواً في مجموعة ما، أو قد يكون عضواً في المجموعة.
وهو يتكون من مصفوفة بت كبيرة والعديد من دوال التجزئة المستقلة.
كيف يعمل
- لـ إضافة عنصر، قم بتشغيله عبر جميع دوال التجزئة
k. قم بتعيين البتات في فهارسkالناتجة في المصفوفة إلى 1. - لـ التحقق مما إذا كان العنصر موجوداً، قم بتشغيله عبر نفس دوال التجزئة
k. إذا كانت جميع بتاتkتساوي 1، فـ قد يكون موجوداً. إذا كان أي بت يساوي 0، فـ من المؤكد أنه غير موجود.
الخطأ وحالة الاستخدام
- الجانب السلبي (الإيجابيات الخاطئة - False Positives): يمكن لمرشحات Bloom Filters أن تولد إيجابيات خاطئة (القول بأن العنصر موجود بينما هو ليس كذلك)، ولكنها لا تولد أبداً سلبيات خاطئة.
- حالات الاستخدام: منع متصفحات الويب من زيارة عناوين URL ضارة (عن طريق التحقق من قائمة سوداء) أو التحقق من استعلامات قاعدة البيانات لتجنب عمليات القراءة المكلفة من القرص إذا كان العنصر مفقوداً بوضوح.