ब्लूम फ़िल्टर

फिर से नमस्कार! आज मैं ब्लूम फिल्टर के बारे में बात करूंगा - इसकी सादगी में शानदार एक डेटा संरचना। वास्तव में, यह फिल्टर सिर्फ दो ऑपरेशनों के साथ एक संभाव्यता सेट को लागू करता है: सेट में एक तत्व जोड़ना और यह जांचना कि क्या तत्व सेट से संबंधित है। सेट संभावित है क्योंकि प्रश्न पर अंतिम ऑपरेशन "यह तत्व सेट से संबंधित है?" एक उत्तर "हां / नहीं" के रूप में नहीं, बल्कि "संभव / नहीं" के रूप में देता है।

एक फ़िल्टर यह कैसे करता है?

जैसा कि मैंने कहा, यह विचार सरल है। निश्चित आकार m



के बिट्स की एक सरणी और k



अलग-अलग हैश फ़ंक्शंस जो 0



से m - 1



मान उत्पन्न करते m - 1



शुरू m - 1



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



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

कार्यान्वयन

जावास्क्रिप्ट पर कोड, सिर्फ इसलिए कि Habré पर यह कई के लिए स्पष्ट है। सबसे पहले, हमें किसी तरह बिटमैप का प्रतिनिधित्व करने की आवश्यकता है:

 function Bits() { var bits = []; function test(index) { return (bits[Math.floor(index / 32)] >>> (index % 32)) & 1; } function set(index) { bits[Math.floor(index / 32)] |= 1 << (index % 32); } return {test: test, set: set}; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

हमें हैश फ़ंक्शंस के एक मानकीकृत परिवार की भी आवश्यकता है, जिससे कि k



अलग-अलग बनाने में आसानी हो। कार्यान्वयन सरल है, लेकिन आश्चर्यजनक रूप से अच्छी तरह से काम करता है:

 function Hash() { var seed = Math.floor(Math.random() * 32) + 32; return function (string) { var result = 1; for (var i = 0; i < string.length; ++i) result = (seed * result + string.charCodeAt(i)) & 0xFFFFFFFF; return result; }; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ठीक है, वास्तव में, ब्लूम फ़िल्टर ही:

 function Bloom(size, functions) { var bits = Bits(); function add(string) { for (var i = 0; i < functions.length; ++i) bits.set(functions[i](string) % size); } function test(string) { for (var i = 0; i < functions.length; ++i) if (!bits.test(functions[i](string) % size)) return false; return true; } return {add: add, test: test}; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

उपयोग उदाहरण:

 var fruits = Bloom(64, [Hash(), Hash()]); fruits.add('apple'); fruits.add('orange'); alert(fruits.test('cabbage') ? ' .' : ' ,  100%.');
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

मापदंडों के साथ खेल के बाद, यह स्पष्ट हो जाता है कि उनके लिए कुछ इष्टतम मान होना चाहिए।

इष्टतम पैरामीटर मान

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



, जहां n



फिल्टर सेट में संग्रहीत तत्वों की अनुमानित संख्या है, p



एक झूठी सकारात्मक की वांछित संभावना है।



हैश फ़ंक्शन की संख्या बड़ी नहीं होनी चाहिए, लेकिन छोटी नहीं। इष्टतम राशि:





हम अर्जित ज्ञान को लागू करते हैं:

 function OptimalBloom(max_members, error_probability) { var size = -(max_members * Math.log(error_probability)) / (Math.LN2 * Math.LN2); var count = (size / max_members) * Math.LN2; size = Math.round(size); count = Math.round(count); var functions = []; for (var i = 0; i < count; ++i) functions[i] = Hash(); return Bloom(size, functions); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

उपयोग कहाँ करें?

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



इस मामले में, कुछ रैम खर्च करना और डिस्क उपयोग को बहुत कम करना फायदेमंद है। कहो, लोड को 10 गुना कम करने के लिए, आपको प्रत्येक कुंजी के लिए लगभग 5 बिट्स जानकारी संग्रहीत करने की आवश्यकता है। 100 बार कम करने के लिए, आपको प्रति कुंजी 10 बिट की आवश्यकता होती है। अपने निष्कर्ष निकालें।

विभिन्न विचार

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



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



यह भी स्पष्ट है कि फ़िल्टर मापदंडों को गतिशील रूप से बदलना संभव नहीं है। फ़िल्टर की पदानुक्रम शुरू करने से समस्या का हल हो जाता है, प्रत्येक बाद में अधिक सटीक होता है, यदि आवश्यक हो, तो पदानुक्रम गहरा बढ़ता है।



शायद बस इतना ही। अलविदा।