ब्लूम फ़िल्टर के लिए झूठी सकारात्मक की संख्या।
विवरण
ब्लूम फ़िल्टर 1970 में बर्टन ब्लूम द्वारा विकसित एक यादृच्छिक क्वेरी डेटा संरचना है। ब्लूम फ़िल्टर एक अनुरोध के लिए एक गलत प्रतिक्रिया देता है, तथाकथित गलत सकारात्मक ऑपरेशन। यानी यदि हम कुछ तत्व जोड़ते हैं, तो एक गैर-शून्य संभावना है कि ब्लूम फ़िल्टर उत्तर को वापस कर देगा कि तत्व वेक्टर में है, हालांकि यह वहां नहीं है।
मोटे तौर पर, ब्लूम फ़िल्टर 2 संभावित उत्तर देता है:
- वेक्टर में कोई तत्व नहीं
- तत्व संभवतः वेक्टर में है
ब्लूम ने ऐसे गलत उत्तरों की संभावना का विश्लेषण किया, लेकिन उनका विश्लेषण गलत है।
लेख में मैं ब्लूम फ़िल्टर के निर्माण का वर्णन नहीं करूंगा, आप इसके बारे में संबंधित लेख
ब्लूम फ़िल्टर या
विकी विकी
: ब्लूम फ़िल्टर पर पढ़ सकते हैं
परिचय
ब्लूम फ़िल्टर एक डेटा संरचना है, जो कुछ तत्वों के सेट S को बिट वेक्टर में मैप करता है
। एक तत्व
k- यादृच्छिक हैश फ़ंक्शन लिखने के लिए उपयोग किया जाता है, जैसे कि
। प्रारंभ में, वेक्टर को शून्य के लिए प्रारंभ किया जाता है। वेक्टर बी में सभी
k- बिट्स को एकता में सेट करके एक तत्व दर्ज किया गया है, अर्थात।
। किसी तत्व के अस्तित्व की जांच करना
फ़िल्टर में यह वेक्टर के प्रत्येक
k- बिट के मूल्यों का पता लगाने के लिए पर्याप्त है। यदि कम से कम एक शून्य है, तो इसका मतलब है कि वेक्टर में अभी तक ऐसा कोई तत्व नहीं है, और यदि सभी बिट्स एक में सेट हैं, तो यह इंगित करता है कि तत्व शायद पहले से मौजूद है। इस स्थिति को झूठी सकारात्मक कहा जाता है।
ब्लूम ने झूठे सकारात्मक को इस प्रकार गिना:
सदिश B के किसी भी बिट की संभावना शून्य है
n तत्वों को जोड़ने पर
k हैश फ़ंक्शन की सभी इकाइयों को सेट करने के बाद।
इसलिए, संभावना है कि एक विशेष बिट को एक पर सेट किया जाएगा
अब, लाने के लिए
झूठी सकारात्मक के लिए, वेक्टर के
कश्मीर बिट्स में से प्रत्येक
एक पर सेट होना चाहिए। इस की संभावना:
जिसके बराबर होने का दावा किया जाता है
यह प्रमाण, जो कई साल पहले दिखाई दिया था, गलत है। त्रुटि इस तथ्य में निहित है कि एक अंतर्निहित धारणा यह है कि घटना
और घटना
स्वतंत्र माने जाते हैं। पहली नज़र में, यह सच लगता है, क्योंकि
स्वतंत्र हैं। हालांकि, मामले पर विचार करके सबूत के लिए एक सरल प्रतिधारण प्राप्त किया जा सकता है
। इस मामले में, 16 संभावित स्थितियों का एक सरल ज्ञान
5/8 के रूप में एक झूठी-सकारात्मक प्रतिक्रिया की संभावना को प्रकट करता है, जबकि ब्लूम सूत्र
9/16 = 4.5 / 8 परिणाम देता है।
सटीक सूत्र
हम गेंदों और बास्केट की समस्या के रूप में झूठी सकारात्मक की संख्या निर्धारित करने की समस्या का अनुकरण करते हैं। हमारे पास
एम- टोकरी है। हम यादृच्छिक बास्केट में
घुटने की सफेद गेंद फेंकते हैं। हम एक टोकरी सफेद पर विचार कर सकते हैं यदि इसमें कम से कम एक सफेद गेंद हो। अगला हम बास्केट में
के- ब्लैक बॉल डालते हैं। बता दें कि
ए एक ब्लैक बॉल सफेद टोकरी में स्थित है। हम इस घटना की संभावना की गणना करते हैं।
।
ध्यान दें कि कई सफेद टोकरी को एक सबसेट के रूप में दर्शाया जा सकता है
। किसी के लिए
लक्षित
एक घटना के रूप में कि मैं सफेद बास्केट की एक भीड़ हूं। शक्ति I बराबर है
। हम सशर्त प्रायिकता सूत्र का उपयोग करते हैं:
अगर मैं तय कर रहा हूं, तो
जहाँ
अपने आप में समाहित है
- आकार के एक सेट से मैपिंग की संख्या मैं मानों के एक सेट में i और
- आकार घुटने के एक सेट से आकार एम के एक सेट के लिए कार्यों की संख्या
आकार के एक सेट से आकार के एक सेट के लिए मैपिंग की संख्या
I सूत्र द्वारा वर्णित है
जहाँ
आकार
घुटने से लेकर आकार
m के सेट तक के कार्यों की संख्या है
।
इन सूत्रों को मिलाएं:
अंतिम परिणाम
परिणामस्वरूप, यह पता चला है कि k- हैश फ़ंक्शन का उपयोग करते हुए n तत्वों को जोड़ने पर m बिट्स के ब्लूम फ़िल्टर की झूठी सकारात्मकता की संभावना बराबर है:यह सूत्र अब उतना सरल नहीं है, जितना मूल रूप से ब्लूम द्वारा गणना की गई थी। आगे के विवरण में जाने के बिना, मैं कहूंगा कि लेख के लेखक भी इस सूत्र की ऊपरी और निचली सीमाओं का वर्णन करते हैं और इस निष्कर्ष पर आते हैं कि ब्लूम द्वारा आरंभ किया गया प्रारंभिक सूत्र केवल निचली सीमा के रूप में उपयोग किया जा सकता है।
मूल लेख पाठ:
ब्लाउज फिल्टर के FALSE-POSITIVE दर पर