بلوم تصفية في جافا مع الجوافة

يوم جيد للجميع.

أطلقنا دورة جديدة - "الخوارزميات للمطورين" ، صُممت لأولئك لتعزيز معرفتهم بالهياكل والخوارزميات المختلفة لمعالجة البيانات ، وحل مشاكل الجبر ومشاكل البرمجة الديناميكية لمختلف اللغات. لذا ، فإننا نشارك اليوم ملاحظة صغيرة حول تشغيل مرشح Bloom في Java.

مقدمة

في هذه المقالة ، سننظر في بنية مرشح Bloom من مكتبة Guava. يعتبر مرشح Bloom عبارة عن بنية بيانات احتمالية مع استخدام فعال للذاكرة يمكننا استخدامه للإجابة على السؤال "هل هذا العنصر في المجموعة؟".

لا توجد سلبيات خاطئة في مرشح Bloom ، لذلك إذا تم إرجاع false ، فيمكنك التأكد بنسبة 100٪ من عدم وجود هذا العنصر في المجموعة.

ومع ذلك ، يمكن لعامل التصفية Bloom أن يعيد إيجابيات خاطئة ، لذلك عندما يتم إرجاع true ، يكون الاحتمال كبيرًا أن العنصر موجود بالفعل في المجموعة ، لكن الاحتمال ليس 100٪.

لمعرفة المزيد حول تشغيل مرشح Bloom ، راجع هذا الدليل.



إدمان مخضرم

سوف نستخدم تطبيق Guava لمرشح Bloom ، لذلك أضف تبعية Guava
يمكن العثور على أحدث إصدار في Maven Central .

<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22.0</version> </dependency> 

لماذا استخدام مرشح ازهر؟

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

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

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

إنشاء مرشح بلوم

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

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

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 500, 0.01); 

أضف الآن بعض الأرقام إلى الفلتر:

 filter.put(1); filter.put(2); filter.put(3); 

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

 assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(100)).isFalse(); 

كما يوحي الاسم ، لا يمكننا أن نكون متأكدين بنسبة 100٪ من أن هذا العنصر موجود بالفعل في عامل التصفية إذا تم إرجاع الطريقة إلى حقيقة.

في حالتنا ، عندما mightContain() ، 99٪ أن العنصر موجود في المرشح ، و 1٪ ، أن النتيجة إيجابية خاطئة. في حالة إرجاع عامل التصفية خاطئ ، يمكنك التأكد بنسبة 100 ٪ من أن العنصر مفقود.

مرشح بلوم مشبع

عند تصميم مرشح Bloom ، من المهم توفير قيمة دقيقة بدرجة كافية لعدد العناصر المتوقع. خلاف ذلك ، سيعود مرشح لدينا ايجابيات كاذبة في كثير من الأحيان أكثر مما نود. النظر في مثال.

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

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 5, 0.01); IntStream.range(0, 100_000).forEach(filter::put); 

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

لاحظ أن الأسلوب mightContatin() يعود صحيحًا حتى بالنسبة للقيمة التي لم mightContatin() قبل في الفلتر.

الخاتمة

في هذا البرنامج التعليمي السريع ، نظرنا في الطبيعة الاحتمالية لهيكل بيانات مرشح Bloom - باستخدام تطبيق Guava.

يمكن العثور على تنفيذ كل هذه الأمثلة ومقتطفات الكود في مشروع جيثب .

هذا مشروع مخضرم ، لذلك يجب أن لا يكون الاستيراد والإطلاق أمرًا صعبًا.

النهاية

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