ब्लूम फिल्टर (Bloom Filter) को एक डेटा स्ट्रक्चर के रूप में परिभाषित किया जाता है जिसे एक सेट में एलिमेंट की उपस्थिति (Presence) की पहचान करने के लिए तेज़ और मेमोरी-कुशल तरीके से डिज़ाइन किया गया है।
प्रोबेबिलिस्टिक डेटा स्ट्रक्चर (Probabilistic Data Structure) नामक एक विशिष्ट डेटा स्ट्रक्चर को ब्लूम फिल्टर के रूप में लागू किया जाता है। यह डेटा स्ट्रक्चर हमें यह पहचानने में मदद करता है कि कोई एलिमेंट किसी सेट में मौजूद है या अनुपस्थित।
बिट वेक्टर (Bit Vector) को बेस डेटा स्ट्रक्चर के रूप में लागू किया जाता है। यहाँ एक छोटा सा उदाहरण है जिसका उपयोग हम समझाने के लिए करेंगे
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
उस टेबल में प्रत्येक खाली सेल एक बिट को निर्दिष्ट करता है और उसके नीचे की संख्या उसका इंडेक्स या पोजीशन है। ब्लूम फिल्टर में एलिमेंट जोड़ने के लिए, हम इसे कुछ बार हैश करते हैं और उन हैश के इंडेक्स या पोजीशन पर बिट वेक्टर में बिट्स को 1 पर सेट करते हैं।
ब्लूम फिल्टर का विस्तृत कार्यान्वयन (Elaborate implementation of Bloom Filter)
ब्लूम फिल्टर दो क्रियाओं का समर्थन करते हैं, पहला ऑब्जेक्ट जोड़ना और ऑब्जेक्ट का ट्रैक रखना और अगला यह सत्यापित करना कि कोई ऑब्जेक्ट पहले देखा गया है या नहीं।
ऑब्जेक्ट्स को ब्लूम फिल्टर में जोड़ना (Adding objects to the Bloom filter)
- जोड़ने के लिए ऑब्जेक्ट के लिए हैश मानों की गणना करें;
- ब्लूम फिल्टर स्टेट में कुछ बिट्स सेट करने के लिए इन हैश-मानों का उपयोग करें (हैश मान सेट करने के लिए बिट की पोजीशन है)।
सत्यापित करना कि ब्लूम फिल्टर में ऑब्जेक्ट है या नहीं (Verifying whether the Bloom filter contains an object)
- जोड़ने के लिए ऑब्जेक्ट के लिए हैश मानों की गणना करें;
- अगला सत्यापित करें कि इन हैश मानों द्वारा इंडेक्स किए गए बिट्स ब्लूम फिल्टर स्टेट में सेट हैं या नहीं।
हमें ध्यान रखना होगा कि किसी ऑब्जेक्ट के लिए हैश मान सीधे ब्लूम फिल्टर स्टेट में नहीं जोड़ा जाता; प्रत्येक हैश फंक्शन केवल यह निर्धारित करता है कि कौन सा बिट सेट करना है या सत्यापित करना है। उदाहरण के लिए: यदि केवल एक हैश फंक्शन उपयोग किया जाता है, तो केवल एक बिट सत्यापित या जांचा जाता है।
