مبدأ مرشح Bloom بسيط للغاية: إنه عبارة عن سلسلة في مفتاح عدد صحيح ، ثم حدد تسلسلًا طويلًا جدًا ، والذي يبدأ بـ 0 ، ويتغير 0 في هذا الموضع إلى 1 في المفتاح ؛ في المرة القادمة التي تأتي فيها سلسلة ، مفتاح القيمة بعد التجزئة ، وإذا كانت القيمة على هذا البت هي أيضًا 1 ، فهذا يعني وجود السلسلة.
إذا اتبعت الطريقة المذكورة أعلاه ، فلن يكون الأمر مختلفًا عن خوارزمية التجزئة ، ولا تزال هناك نسخ من خوارزمية التجزئة.
مرشح Bloom Hash سلسلة في مفاتيح متعددة ، لذلك من الأفضل أن أتبع الكتاب.
قم أولاً بإنشاء ثابت ثنائي 1.6 مليار ، ثم حدد كل البتات الثنائية 1.6 مليار إلى الصفر. لكل سلسلة ، يتم استخدام 8 مولدات عشوائية مختلفة (F1 ، F2 ، ... ، F8) لإنشاء 8 بصمات معلومات (F1 ، F2 ، ... ، F8). بعد ذلك ، يتم استخدام مولد الأرقام العشوائية G لتعيين هذه البصمات الثمانية للمعلومات إلى 8 أرقام طبيعية G1 ، G2 ، ... ، G8 في 1 إلى 1.6 مليار. الآن قم بتغيير جميع البتات الثنائية في هذه المواضع الثمانية إلى 1. وبهذه الطريقة تم بناء مرشح بلوم.
إذن كيف تكتشف ما إذا كانت سلسلة موجودة بالفعل؟
استخدم الآن 8 مولدات الأرقام العشوائية (F1 ، F2 ، ... ، F8) لإنشاء 8 معلومات بصمات الأصابع S1 ، S2 ، ... ، S8 لهذه السلسلة ، ثم تتوافق هذه بصمات المعلومات الثمانية هذه إلى البت الثماني الثنائي من مرشح الإزهار ، وهي T1 ، T2 ، ... ، T8. في حالة وجود السلسلة ، من الواضح أن البتات الثنائية المقابلة لـ T1 ، T2 ، ... ، يجب أن تكون T8 1. هذه هي كيفية تحديد ما إذا كانت سلسلة موجودة بالفعل.
في الواقع ، مرشح بلوم هو امتداد لخوارزمية التجزئة. نظرًا لأنها عبارة عن تجزئة ، فستكون هناك بالتأكيد أوجه قصور. وبعبارة أخرى ، سيكون هناك بالتأكيد سوء الحكم. لم تظهر سلسلة ، لكن حكم مرشح بلوم قد ظهر. على الرغم من أن الاحتمال صغير جدًا ، إلا أنه موجود.
فكيف تقلل من هذا الاحتمال؟ بادئ ذي بدء ، يمكن تخيل أنه إذا تم تمديد 8 بصمات بصمات المعلومات إلى 16 خطأ ، فسيتم تقليل الاحتمال بالتأكيد ، ولكن ينبغي اعتباره أيضًا أنه وبهذه الطريقة ، يتم تقليل عدد الأوتار التي يمكن لتصفية الإزهار أيضًا تخزينها بمقدار واحد مرات ؛ بالإضافة إلى ذلك ، حدد وظيفة تجزئة جيدة ، وهناك العديد من أنواع أساليب التجزئة للسلاسل ، بما في ذلك وظائف التجزئة الجيدة للغاية.
يستخدم مرشح البرونز بشكل أساسي لتصفية عناوين URL الضارة. يتم بناء جميع عناوين URL الضارة على مرشح برونزي ، ثم يتم الوصول إلى المستخدم بواسطة عنوان URL. إذا كان في عنوان URL ضار ، سيتم إخطار المستخدم. وبهذه الطريقة ، يمكننا أيضًا تعيين قائمة بيضاء لبعض عناوين URL التي غالباً ما يكون لها أخطاء في الحكم ، ثم تطابق عناوين URL التي يتم الحكم عليها على وجودها وعنوان URL في القائمة البيضاء. إذا كانوا في القائمة البيضاء ، فسيتم إطلاق سراحهم. بالطبع ، لا يمكن أن تكون هذه القائمة البيضاء كبيرة جدًا ، كما أنها ليست كبيرة جدًا ، واحتمال وجود خطأ في مرشح الإزهار صغير جدًا. يمكن للقراء المهتمين التحقق من معدل الخطأ في مرشح بلوم.
ما يلي هو الكود المصدري لإصدار Java من Floom Filter:
استيراد java.util.bitset ؛ /** * * Author Xkey */Public Class Bloomfilter {Private Static Final Default_size = 2 << 24 ؛ // Bit Length of Bloom Fluter Private Static Final int [] يمكن أن يتم تحديد سعر الفتنة بشكل جيد للغاية). static static simplehash [] func = new simplehash [seeds.length] ؛ public static void addvalue (قيمة السلسلة) {لـ (simplehash f: func) // hash قيمة السلسلة إلى 8 أعداد صحيحة أو أكثر ، ثم تتغير إلى 1 على أجزاء من هذه الأعداد الصحيحة bits.set (f.hash (value) ، true) ؛ } void static public add (قيمة السلسلة) {if (value! = null) addValue (value) ؛ } يحتوي Boolean الثابت العام على (قيمة السلسلة) {if (value == null) return false ؛ Boolean Ret = True ؛ لـ (Simplehash F: FUNC) // في الواقع ، ليست هناك حاجة لتشغيل كل منهم هنا. فقط ret == false مرة واحدة ، فلن يتم تضمين السلسلة. ret = ret && bits.get (f.hash (value)) ؛ العودة ret. } public static void main (string [] args) {string value = "www.vevb.com" ؛ لـ (int i = 0 ؛ i <seeds.length ؛ i ++) {func [i] = new simplehash (default_size ، البذور [i]) ؛ } إضافة (قيمة) ؛ System.out.println (يحتوي على (قيمة)) ؛ }} class simplehash {// هذا الشيء يعادل الهيكل في c ++ private cap ؛ بذرة int الخاصة public simplehash (int cap ، int seed) {this.cap = cap ؛ هذا. } public int hash (قيمة السلسلة) {// stand hash ، من المهم للغاية تحديد وظيفة تجزئة جيدة = 0 ؛ int len = value.length () ؛ لـ (int i = 0 ؛ i <len ؛ i ++) {result = seed * result+value.charat (i) ؛ } return (cap - 1) & result ؛ }} ملخص: Floom Filter هو ابتكار في خوارزميات التجزئة ، ويتطلب مساحة ضئيلة للغاية وله معدل خطأ منخفض. باختصار ، هذه الفكرة المبتكرة تستحق التعلم وهي استخدام نوع البيانات مثل بت.
طريقة تنفيذ Java في مرشح Bloom هي كل المحتوى الذي شاركته معك. آمل أن تتمكن من إعطائك مرجعًا وآمل أن تتمكن من دعم wulin.com أكثر.