ما هي ميزة استخدام مرشحات بلوم؟

Question

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

Answer 1

من ويكيبيديا:

تتمتع مرشحات Bloom بميزة فضاء قوية على هياكل البيانات الأخرى لتمثيل مجموعات ، مثل أشجار البحث الثنائية ذاتية التوازن ، أو محاولات التجزئة ، أو المصفوفات البسيطة أو القوائم المرتبطة بالإدخالات. يتطلب معظم هذه الأشياء تخزين عناصر البيانات على الأقل نفسها ، والتي يمكن أن تتطلب أي مكان من عدد صغير من البتات ، من أجل الأعداد الصحيحة الصغيرة ، إلى عدد تعسفي من البتات ، مثل الأوتار (المحاولات هي استثناء ، حيث يمكنهم مشاركة التخزين بين عناصر مع بادئات متساوية). الهياكل المرتبطة تتحمل مساحة خطية إضافية للمؤشرات. من ناحية أخرى ، لا يتطلب مرشح Bloom مع خطأ 1 ٪ والقيمة المثلى لـ K ، من ناحية أخرى ، حوالي 9.6 بت لكل عنصر - بغض النظر عن حجم العناصر. تأتي هذه الميزة جزئيًا من الانضغاط ، الموروثة من المصفوفات ، وجزئيًا من طبيعتها الاحتمالية. إذا كان معدل إيجابي كاذب 1 ٪ يبدو مرتفعًا جدًا ، في كل مرة نضيف فيها حوالي 4.8 بت لكل عنصر ، نقليه بمقدار عشر مرات.

واضح جدا بالنسبة لي.

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

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

لذلك قد يكون نمط الاستخدام مثال:

لديك الكثير من البيانات ، على القرص - أنت تقرر الخطأ الذي تريده (على سبيل المثال 1 ٪) ، والتي تحدد قيمة م. ثم الأمثل ك تم تحديده (من الصيغة الواردة في المقالة). يمكنك ملء المرشح الخاص بك من هذه البيانات المرتبطة بالقرص مرة واحدة.

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

خلاف ذلك ، إذا قال المرشح "نعم ، إنه موجود هناك" ، فهناك فرصة بنسبة 1 ٪ أن يكون ذلك خطأ ، لذلك تقوم بالعمل اللازم لمعرفة ذلك. 99 ٪ من الوقت ، هو حقا إرادة كن هناك ، لذلك لم يكن العمل لا شيء.

Answer 2

لقد أوضح أليكس ذلك جيدًا. بالنسبة لأولئك الذين ما زالوا لم يحصلوا على فهم كبير ، نأمل أن يساعدك هذا المثال على فهم:

دعنا نقول إنني أعمل في Google ، في فريق Chrome ، وأريد إضافة ميزة إلى المتصفح الذي يخطر المستخدم إذا كان عنوان URL الذي أدخله هو عنوان URL ضار. لذلك لدي مجموعة بيانات تبلغ حوالي مليون عناوين URL الضارة ، بحجم هذا الملف حوالي 25 ميجابايت. نظرًا لأن الحجم كبير جدًا ، (كبير مقارنة بحجم المتصفح نفسه) ، أقوم بتخزين هذه البيانات على خادم بعيد.

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

الحالة 2: أستخدم مرشح بلوم. يتم تشغيل القائمة الكاملة التي تضم مليون عنوان URL عبر مرشح Bloom باستخدام وظائف تجزئة متعددة ويتم تمييز المواضع المعنية على أنها 1 ، في مجموعة ضخمة من 0s. لنفترض أننا نريد معدل إيجابي كاذب قدره 1 ٪ ، باستخدام حاسبة مرشح بلوم (http://hur.st/bloomfilter؟n=1000000&p=0.01) ، نحصل على حجم مرشح بلوم المطلوب كـ 1.13 ميغابايت فقط. من المتوقع أن يكون هذا الحجم الصغير ، على الرغم من أن حجم الصفيف ضخم ، إلا أننا نقوم بتخزين 1S أو 0 فقط وليس عناوين URL كما في حالة جدول التجزئة. يمكن التعامل مع هذه الصفيف كصفيف بت. هذا هو ، نظرًا لأن لدينا قيمتان فقط 1 و 0 ، يمكننا تعيين أجزاء فردية بدلاً من البايتات. هذا من شأنه أن يقلل من المساحة التي يتم الاستيلاء عليها من قبل 8 مرات. يمكن تخزين مرشح بلوم 1.13 ميجابايت ، بسبب حجمه الصغير ، في متصفح الويب نفسه !! وبالتالي عندما يأتي المستخدم ويدخل عنوان URL ، فإننا ببساطة نطبق وظائف التجزئة المطلوبة (في المتصفح نفسه) ، والتحقق من جميع المواضع في مرشح Bloom (الذي يتم تخزينه في المتصفح). تخبرنا قيمة 0 في أي من المواقف أن عنوان URL هذا بالتأكيد ليس في قائمة عناوين URL الضارة ويمكن للمستخدم المضي قدمًا بحرية. وبالتالي لم نقم بإجراء مكالمة إلى الخادم وبالتالي حفظ الوقت. تخبرنا قيمة 1 أن عنوان URL قد يكون في قائمة عناوين URL الضارة. في هذه الحالات ، نقوم بإجراء مكالمة إلى الخادم البعيد ، ويمكننا استخدام بعض وظيفة التجزئة الأخرى مع بعض جدول التجزئة كما في الحالة الأولى لاسترداد والتحقق مما إذا كان عنوان URL موجودًا بالفعل. منذ معظم الأوقات ، من غير المرجح أن يكون عنوان URL ضارًا ، فإن مرشح الإزهار الصغير في المتصفح يحدد أنه يوفر الوقت من خلال تجنب المكالمات إلى الخادم البعيد. فقط في بعض الحالات ، إذا أخبرنا مرشح Bloom أن عنوان URL قد يكون ضارًا ، فقط في تلك الحالات ، نقوم بإجراء مكالمة إلى الخادم. هذا "قد" هو 99 ٪ على حق.

لذلك باستخدام مرشح بلوم صغير في المتصفح ، قمنا بحفظ الكثير من الوقت لأننا لا نحتاج إلى إجراء مكالمات الخادم لكل عنوان URL الذي تم إدخاله.

يمكننا أن نرى أن جدول التجزئة مع وظيفة تجزئة واحدة تستخدم لغرض مختلف تمامًا عن مرشح الإزهار. نأمل أن يزيل هذا شكوكك :)

تعديل:

لقد قمت بتنفيذ مرشح بلوم لمهمة اختبار عنوان URL الضار في بيثون. يمكن العثور على الرمز هنا - https://github.com/tarunsharma1/bloom-filterالكود بسيط للغاية لفهمه ويتم توفير وصف مفصل في ملف ReadMe.

Answer 3

سأبدأ بتفسير ما هو مرشح بلوم ، وما يمكن وما لا يمكنه فعله ، ولماذا نحتاجه ، وإظهار وصف بديهي كيف يعمل ، ثم إعطاء بعض الأمثلة عندما تكون مفيدة.

لذلك أ مرشح الإزهار القياسي هو بنية البيانات الاحتمالية الذي - التي يستطيع^*:

---

• أضف عنصرًا إلى مجموعة
• تحقق مما إذا كان هناك عنصر في المجموعة عن طريق إخبار definitely not in the set أو possibly in the set

هذه possibly in the set هو بالضبط لماذا يسمى الاحتمالية. استخدام الكلمات الذكية يعني ذلك إيجابية كاذبة ممكنة (يمكن أن تكون هناك حالات يعتقد فيها زوراً أن العنصر إيجابي) ولكن السلبية الخاطئة مستحيلة.

لكن ذلك لا يمكن ^*:

• قم بإزالة عنصر من المجموعة
• أعطيك قائمة بجميع العناصر الموجودة حاليًا في مجموعتك

^*_{هذه المجموعة من Can/لا يمكن أن تكون لفلتر بلوم أساسي. لأنه بنية بيانات مفيدة تم إنشاؤها منذ وقت طويل ، وجد الناس كيفية ذلك زيادة مع الآخر مفيد الميزات.}

---

لكن انتظر دقيقة واحدة: نحن نعرف بالفعل بنية بيانات يمكنها الإجابة على كل هذا دون "ممكن" غامض وأيضًا بدون كل القيود (لا يمكن إزالتها ، لا يمكن إظهار الجميع). ويسمى أ تعيين. وهنا تأتي ميزة رئيسية لفلتر الإزهار: إنه كذلك مساحة فعالة ومساحة ثابتة.

هذا يعني أنه لا يهم عدد العناصر التي نخزنها هناك ، ستكون المساحة هي نفسها. نعم مرشح بلوم مع 10^6 ستأخذ العناصر (مرشح أزهار عديمة الفائدة) نفس مساحة الفضاء الذي يزداد عليه مرشح الإزهار 10^20 العناصر ونفس مساحة مرشح بلوم 0 عناصر. إذن ما مقدار المساحة التي ستستغرقها؟ الأمر متروك لك لتقرر (ولكن هناك تجارة: كلما زادت العناصر التي لديك أكثر عدم التأكد من أنك معك possible in the set إجابه.

شيء رائع آخر هو أنه ثابت الفضاء. عند حفظ البيانات في مجموعة ، يجب عليك حفظ هذه البيانات بالفعل. لذلك إذا قمت بتخزين this long string in the set يجب عليك على الأقل استخدام 27 بايت من المساحة. ولكن لخطأ 1 ٪ والقيمة المثلى من k ^**, ، ستحتاج إلى حوالي 9.6 بت (<2 بايت) لكل عنصر (سواء كان ذلك مختصراً أو جدارًا ضخمًا من النص).

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

^**_{K هي قيمة وظائف التجزئة المستخدمة في مرشح Bloom}

---

لن أصف كيف مرشحات بلوم (مقالة ويكيبيديا تقوم بعمل جيد للغاية في شرح كل شيء). هنا سأخبر الأساسيات لفترة وجيزة.

• يمكنك بدء مجموعة بت فارغة من الطول m
• اخترت k وظائف التجزئة المختلفة (كلما كانت أفضل) أفضل)
• إذا كنت ترغب في إضافة عنصر ، فأنت تحسب كل k تجزئة هذه القيمة وتعيين البتات المقابلة إلى 1
• إذا كنت ترغب في التحقق مما إذا كان هناك عنصر ، فأنت أيضًا حساب الكل k تجزئة وإذا لم يتم تعيين واحد منهم على الأقل ، فمن المؤكد أنه ليس في المجموعة. وإلا يمكن أن يكون في المجموعة.

حتى هذا الوصف يكفي لفهم سبب عدم تمكننا من التأكد (يمكنك الحصول على جميع البتات من مختلف القيم الأخرى). هنا تصور جميل جدا لكيفية عمله.

---

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

فيما يلي قائمة بالأوصاف الملموسة:

• مثال قياسي على مواقع ويب خبيثة ومتصفح موصوف في أي تقريبا مكان حيث يتحدث الناس عن مرشحات بلوم
• هل كلمة مرور ضعيفة: بدلاً من وجود مجموعة ضخمة من جميع كلمات المرور الضعيفة الممكنة ، يمكنك فقط التحقق مما إذا كانت كلمة المرور ليست ضعيفة بالتأكيد مع مرشح أزهار أصغر
• إذا كان لديك قائمة بالمقالات وقائمة المستخدمين ، فيمكنك استخدام Floom Filter لإظهار مقالات المستخدمين التي لم يقرؤوها. الشيء المثير للاهتمام هو أنه يمكنك الحصول على مرشح واحد فقط (يمكنك التحقق مما إذا كان هناك مزيج من user_id + article_id موجود)
• بيتكوين يستخدم مرشح بلوم لمزامنة المحفظة
• تستخدم خوادم الويب الخاصة بـ Akamai مرشحات Bloom لمنع تخزين "الواحد الواحد" في ذاكرة التخزين المؤقت للقرص. من الضباط واحد هي كائنات ويب يطلبها المستخدمون مرة واحدة فقط ، وهو أمر وجد Akamai تطبيقه على ما يقرب من ثلاثة أرباع البنية التحتية للتخزين المؤقت. استخدام مرشح بلوم لاكتشاف الطلب الثاني لكائن ويب وتخزين مؤقت للتخزين المؤقت هذا الكائن فقط بناءً على طلبه الثاني يمنع عجائب الضربة الواحدة من إدخال ذاكرة التخزين المؤقت للقرص ، وتقليل عبء عمل القرص بشكل كبير وزيادة معدلات ذاكرة التخزين المؤقت للقرص (مأخوذة من أمثلة في مرشح بلوم مقال في ويكي)

Answer 4

مرشحات بلوم مفيدة للغاية في المعلوماتية الحيوية. يمكن أن تكون أكثر كفاءة في المساحة مقارنة باستخدام علامة تجزئة منتظمة ، خاصة عندما يكون حجم الأوتار التي تعمل معها مئات الملايين من الحروف ذات الأبجدية الصغيرة جدًا أي {a ، g ، t ، c}. عادة ما يتم استخدامها لتقييم ما إذا كان k-mer معين موجود أو غياب في الجينوم. هناك مثال على واحد يستخدم لشيء ذي صلة هنا.

تعديل:

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

قارن هذا بالجينوم البشري ، حيث تزيد زيادة حجم العنصر من حجم جدول التجزئة بشكل كبير (حجم الجدول هو 4*4^ك). هذا يفترض أنك تشفر العناصر باستخدام 2 بت / حرف.

Answer 5

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