जावा में अमरूद के साथ ब्लूम फ़िल्टर

सभी को शुभ दिन।

हमने एक नया पाठ्यक्रम शुरू किया - "डेवलपर्स के लिए एल्गोरिदम" , जो डेटा प्रोसेसिंग के लिए विभिन्न संरचनाओं और एल्गोरिदम के अपने ज्ञान को बढ़ाने के लिए डिज़ाइन किया गया, विभिन्न भाषाओं के लिए बीजीय समस्याओं और गतिशील प्रोग्रामिंग समस्याओं को हल करना। इसलिए आज हम जावा में ब्लूम फिल्टर के संचालन के बारे में एक छोटा सा नोट साझा कर रहे हैं।

परिचय

इस लेख में हम अमरूद पुस्तकालय से ब्लूम फिल्टर की संरचना को देखेंगे। ब्लूम फ़िल्टर कुशल मेमोरी उपयोग के साथ एक संभाव्य डेटा संरचना है जिसका उपयोग हम इस प्रश्न का उत्तर देने के लिए कर सकते हैं कि "क्या यह तत्व सेट में है?"।

ब्लूम फ़िल्टर में कोई गलत नकारात्मक नहीं हैं , इसलिए यदि यह गलत है, तो आप 100% सुनिश्चित हो सकते हैं कि यह तत्व सेट में नहीं है।

हालांकि, ब्लूम फ़िल्टर झूठी सकारात्मक लौटा सकता है , इसलिए जब सच लौटाया जाता है, तो संभावना अधिक होती है कि तत्व वास्तव में सेट में है, लेकिन संभावना 100% नहीं है।

ब्लूम फ़िल्टर के संचालन के बारे में अधिक जानने के लिए, इस मार्गदर्शिका को देखें।



मावेन की लत

हम ब्लूम फ़िल्टर के अमरूद कार्यान्वयन का उपयोग करेंगे, इसलिए हम अमरूद निर्भरता को जोड़ते हैं
नवीनतम संस्करण मावेन सेंट्रल में पाया जा सकता है।

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

एक ब्लूम फ़िल्टर का उपयोग क्यों करें?

ब्लूम फ़िल्टर को किफायती और तेज़ बनाया गया है। इसका उपयोग करते समय, हम झूठे सकारात्मक उत्तरों की संभावना को स्पष्ट कर सकते हैं जिन्हें हम स्वीकार करने के लिए तैयार हैं , और, कॉन्फ़िगरेशन के अनुसार, ब्लूम फ़िल्टर जितना संभव हो उतना कम मेमोरी लेगा।

अपनी अर्थव्यवस्था के कारण, ब्लूम फ़िल्टर बड़ी संख्या में तत्वों के साथ भी आसानी से मेमोरी में फिट बैठता है। कैसेंड्रा और ओरेकल सहित कुछ डेटाबेस, डिस्क या कैश तक पहुंचने से पहले प्रारंभिक जांच के लिए इस फिल्टर का उपयोग करते हैं, उदाहरण के लिए, जब एक विशिष्ट आईडी के लिए अनुरोध प्राप्त होता है।

यदि फ़िल्टर कहता है कि कोई आईडी नहीं है, तो डेटाबेस अनुरोध को संसाधित करना बंद कर सकता है और क्लाइंट को वापस कर सकता है। अन्यथा, क्वेरी डिस्क पर जाती है और पाया गया आइटम वापस करती है।

एक ब्लूम फ़िल्टर बनाना

मान लें कि हम 500 से अधिक पूर्णांकों के लिए ब्लूम फ़िल्टर बनाना चाहते हैं, और हम झूठी सकारात्मकता की एक प्रतिशत (0.01) संभावना से तीन गुना अधिक हैं।

ऐसा करने के लिए, हम अमरूद लाइब्रेरी से BloomFilter क्लास का उपयोग कर सकते हैं। फ़िल्टर में बताए गए तत्वों की संख्या और झूठी सकारात्मकता की वांछित संभावना को स्थानांतरित करना आवश्यक है:

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

अब फ़िल्टर में कुछ संख्याएँ जोड़ें:

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

हमने केवल तीन तत्वों को जोड़ा और आवेषण की अधिकतम संख्या निर्धारित की - 500, इसलिए हमारे ब्लूम फ़िल्टर को काफी सटीक परिणाम देना चाहिए। इसे mightContain() साथ mightContain() विधि:

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

जैसा कि नाम से ही स्पष्ट है, हम यह सुनिश्चित नहीं कर सकते हैं कि यदि यह विधि सही है तो यह तत्व वास्तव में फ़िल्टर में है।

हमारे मामले में, जब mightContain() सही हो जाता है, तो 99% है कि तत्व फ़िल्टर में है, और 1% है, कि परिणाम गलत सकारात्मक है। यदि फ़िल्टर गलत है, तो आप 100% सुनिश्चित कर सकते हैं कि तत्व गायब है।

असंतृप्त ब्लूम फ़िल्टर

ब्लूम फ़िल्टर डिजाइन करते समय, तत्वों की अपेक्षित संख्या के लिए पर्याप्त रूप से सटीक मूल्य प्रदान करना महत्वपूर्ण है। अन्यथा, हमारा फ़िल्टर झूठी सकारात्मकता को बहुत अधिक बार लौटाएगा जितना हम चाहेंगे। एक उदाहरण पर विचार करें।

मान लीजिए कि हम एक प्रतिशत के बराबर झूठी सकारात्मक की वांछित संभावना और पांच के बराबर तत्वों की अपेक्षित संख्या के साथ एक फ़िल्टर बनाते हैं, लेकिन फिर हम 100,000 तत्वों को सम्मिलित करते हैं:

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

इतने कम तत्वों की अपेक्षा, फ़िल्टर बहुत कम मेमोरी लेगा।
हालांकि, अधिक बड़ी संख्या में तत्वों को जोड़ने के बाद, फ़िल्टर ओवरसैट हो जाता है और वांछित एक प्रतिशत की तुलना में गलत-सकारात्मक परिणाम उत्पन्न करने की अधिक संभावना होती है।

ध्यान दें कि mightContatin() विधि उस मान के लिए भी सही है जो हमने पहले फ़िल्टर में नहीं डाला था।

निष्कर्ष

इस त्वरित ट्यूटोरियल में, हमने अमरूद के उपयोग से ब्लूम फ़िल्टर डेटा संरचना की संभाव्य प्रकृति को देखा।

इन सभी उदाहरणों और कोड स्निपेट के कार्यान्वयन को गिटहब परियोजना में पाया जा सकता है।

यह मावेन परियोजना है, इसलिए आयात और लॉन्च मुश्किल नहीं होना चाहिए।

अंत

हम टिप्पणियों और प्रश्नों की प्रतीक्षा कर रहे हैं, जो हमेशा की तरह, यहां छोड़ दिया जा सकता है और खुले घर के दिन के लिए पाठ्यक्रम के शिक्षक मिखाइल गोर्शकोव जा सकते हैं ।