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

यह क्या है

विकिपीडिया राज्यों:

यह एक संभावित डेटा संरचना है, जिसे 1970 में बर्टन ब्लूम द्वारा आविष्कार किया गया था, जो आपको कई तत्वों को कॉम्पैक्ट करने और यह सत्यापित करने की अनुमति देता है कि किसी दिए गए तत्व सेट के हैं। उसी समय, झूठी सकारात्मक प्रतिक्रिया प्राप्त करना संभव है (सेट में कोई तत्व नहीं है, लेकिन डेटा संरचना रिपोर्ट करती है कि यह मौजूद है), लेकिन गलत नकारात्मक नहीं।

एक सरल

यह एक विशाल नमूने में एक तत्व के अस्तित्व को सत्यापित करने का एक तरीका है।

यह कैसे काम करता है?

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

यह कहां लागू किया जा सकता है?

मैं किसी शब्द या वाक्यांश के शब्दकोष> 10,000,000 शब्दों के अस्तित्व की जांच के लिए एक फ़िल्टर लागू करता हूं। Google अपने सर्च इंजन में इसका इस्तेमाल करता है।
सामान्य तौर पर, ब्लूम फ़िल्टर का सकारात्मक पहलू इसकी गति है, जब इन्सर्ट / चेक ऑपरेशन का अनुपात 0.001 से अधिक है और चेक 10000 से अधिक हैं। लेकिन यह केवल तभी है जब पीएचपी में मानक in_array के साथ तुलना की जाती है।
लाभ स्पष्ट हैं: गति, कम डिस्क लोड, कम मेमोरी खपत।
विपक्ष: मूल्यों की लंबी लोडिंग, हटाने की कोई संभावना नहीं है (एक समाधान है)

दूसरी बाइक क्यों? मुझे यकीन है कि पहले ही php पर ब्लूम फ़िल्टर किया जा चुका है।

हाँ, उन्होंने किया। मैंने बेंचमार्क का संचालन किया और मेरा कार्यान्वयन उन सभी से आगे था जो मुझे गति और मेमोरी खपत में मिल सकते थे। मैं आमतौर पर हैश एल्गोरिदम की विशिष्टता के बारे में कुछ नहीं कहूंगा।

नमक क्या है?

वास्तव में, दो समस्याएं हैं।
1. थोड़ा स्ट्रिंग कैसे स्टोर करें
2. एक अद्वितीय हैश की आवश्यकता है।

1. यहाँ समस्या यह है कि डिलीट ऑप्शन के लिए बिट स्ट्रिंग को कैसे स्टोर किया जाए। उस स्थिति में, एक काउंटर का उपयोग किया जाता है और 1 नहीं, लेकिन ऑब्जेक्ट जोड़ते समय एक वेतन वृद्धि निर्धारित की जाती है। मैंने वर्णमाला का उपयोग करने का निर्णय लिया। लेकिन किसी चीज़ को हटाना सबसे अच्छा नहीं है, जिन तत्वों के लिए फ़िल्टर " प्रतिक्रिया करता है " मौजूद हो सकता है उन्हें हटा दिया जाता है, और यदि यह एक झूठी सकारात्मक थी, तो हम नोक्सेंटेंट ऑब्जेक्ट को हटा देंगे।
2. मैं हैश का विशेषज्ञ नहीं हूं और 2 संकेतकों द्वारा एक हैश फ़ंक्शन का चयन किया गया है।
गति शायद सबसे महत्वपूर्ण संकेतक है। अद्वितीयता , 1000 अद्वितीय हैश बनाते समय, उन्हें एक ही पंक्ति में 1000 अलग-अलग मान वापस करने चाहिए। दुर्भाग्य से, मैंने केवल 64% विशिष्टता हासिल की। प्रतियोगी 40% से ऊपर नहीं उठे।
और यह सिर्फ है:

abs( crc32( md5($this->seed[0] . $string) ) ) % $size; 

अद्वितीयता $ स्ट्रिंग का उपयोग करके बनाया गया है-> बीज [को ०]।

कोशिश कहाँ करें?

मैं तुमसे गितुब की विनती करता हूँ।
और कोशिश करें:

 include 'bloom.class.php'; $parameters = array( 'entries_max' => 2 //     2 ,     0.1% ); $bloom = new Bloom($parameters); // ,     $bloom->set('Some string'); //   echo $bloom->has('Some string'); //true // ,   Bloom     counter $bloom->delete('Some string'); 

उपलब्ध विकल्प:

 /* // entries_max (int)  .  : 100. error_chance (float) (0;1)  .  : 0.001. counter (boolean)     ,     .  : false. //     set_size (int)   .  : . hash_count (int)   .  : . //  ,   ['hash'] strtolower (boolean)       .  : true; */ 

उदाहरण में शामिल हैं, इकाई परीक्षण, और बेंचमार्क (दो तरीकों से in_array के साथ और तीन अन्य पुस्तकालयों के साथ तुलना)। आप में से कई लोग खुद इसे लिखने में सक्षम हैं, लेकिन शायद कोई भी साइकिल चलाना नहीं चाहेगा।
बोनस: बिना काउंटर के और साथ में in_array के खिलाफ 25,000 चेक के साथ 50,000 नमूनों के लिए बेंचमार्क।