पायथन: केवल अस्तित्व जांच के साथ सेट करें?

Question

मेरे पास बहुत सारे लंबे तारों का एक सेट है जो मैं अस्तित्व के लिए लुकअप करना चाहता हूं। मुझे बचाने के लिए कभी भी पूरी स्ट्रिंग की आवश्यकता नहीं है। जहां तक ​​मैं कह सकता हूं, set() वास्तव में उस स्ट्रिंग को संग्रहीत करता है जो मेरी बहुत सारी मेमोरी खा रहा है।

क्या ऐसी डेटा संरचना मौजूद है?

done = hash_only_set() 
while len(queue) > 0 : 
    item = queue.pop() 
    if item not in done : 
     process(item) 
     done.add(item) 

(मेरी कतार लगातार अन्य धागे से भरी जा रही है इसलिए मेरे पास शुरुआत में इसे समर्पित करने का कोई तरीका नहीं है)।

Answer 1

यह निश्चित रूप से केवल हैश का एक सेट रखने के लिए संभव है:

done = set() 
while len(queue) > 0 : 
    item = queue.pop() 
    h = hash(item) 
    if h not in done : 
     process(item) 
     done.add(h) 

सूचना क्योंकि हैश टकराव की, इस बात की संभावना आप समझते हैं कि एक आइटम किया भले ही यह नहीं है कि।

यदि आप इस जोखिम को स्वीकार नहीं कर सकते हैं, तो आपको वास्तव में यह बताने में सक्षम होने के लिए पूर्ण तारों को सहेजने की आवश्यकता है कि आपने इसे पहले देखा है या नहीं। वैकल्पिक रूप से: शायद प्रसंस्करण खुद ही बताने में सक्षम होगा?

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

Answer 2

आप विशेष रूप से इस उद्देश्य के लिए Bloom Filter नामक डेटा संरचना का उपयोग कर सकते हैं। एक पायथन कार्यान्वयन here पाया जा सकता है।

संपादित: महत्वपूर्ण नोट:

1. गलत सकारात्मक इस डेटा संरचना में संभव हो रहे हैं, यानी एक स्ट्रिंग के अस्तित्व के लिए एक चेक एक सकारात्मक परिणाम लौट सकता है, भले ही यह था संग्रहीत नहीं ।
2. झूठी नकारात्मक (संग्रहीत एक स्ट्रिंग के लिए नकारात्मक परिणाम प्राप्त करना) संभव नहीं है।

यह कहा गया है कि इस घटना की संभावनाओं को न्यूनतम रूप से लाया जा सकता है यदि सही तरीके से उपयोग किया जाता है और इसलिए मैं इस डेटा संरचना को बहुत उपयोगी मानता हूं।

Answer 3

आपको लुकअप कैसे करना है, इसके बारे में सोचना होगा, क्योंकि सेट की आवश्यकता के दो तरीके हैं, __hash__ और __eq__।

हैश एक "ढीला हिस्सा" है जिसे आप दूर ले सकते हैं, लेकिन __eq__ एक ढीला हिस्सा नहीं है जिसे आप बचा सकते हैं; तुलना के लिए आपके पास दो तार हैं।

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

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

EDIT2:

class BloomFilter (object): 
    """ 
    Let's make a bloom filter 
    http://en.wikipedia.org/wiki/Bloom_filter 

    __contains__ has false positives, but never false negatives 
    """ 
    def __init__(self, hashes=(hash,)): 
     self.hashes = hashes 
     self.data = set() 
    def __contains__(self, obj): 
     return all((h(obj) in self.data) for h in self.hashes) 
    def add(self, obj): 
     self.data.update(h(obj) for h in self.hashes) 

Answer 4

आप 100% निश्चितता के लिए पूरी स्ट्रिंग पता करने की जरूरत: यह मेरा 3 मिनट खिलने फिल्टर है। यदि आपके पास समान उपसर्गों के साथ बहुत सारे तार हैं तो आप तारों को स्टोर करने के लिए एक त्रिभुज का उपयोग करके स्थान बचा सकते हैं। यदि आपके तार लंबे हैं तो आप हैश टकराव की संभावना को अप्रासंगिक मानने के लिए SHA-1 जैसे बड़े हैश फ़ंक्शन का उपयोग कर अंतरिक्ष को भी बचा सकते हैं।

यदि आप process() फ़ंक्शन idempotent बना सकते हैं - यानी इसे किसी आइटम पर दो बार बुलाया जाना केवल एक प्रदर्शन समस्या है, तो समस्या बहुत आसान हो जाती है और आप हानिकारक डेटास्ट्रक्चर, जैसे ब्लूम फ़िल्टर का उपयोग कर सकते हैं।

Answer 5

यदि आप एक सुरक्षित (जैसे SHA-256, hashlib मॉड्यूल में पाए जाते हैं) हैश स्ट्रिंग हैश के लिए फ़ंक्शन है, तो यह बहुत ही असंभव है कि आपको डुप्लिकेट मिलेगा (और यदि आपको कुछ मिलता है तो आप शायद एक पुरस्कार जीत सकते हैं सबसे क्रिप्टोग्राफिक हैश फ़ंक्शन)।

बिल्टिन __hash__() विधि गारंटी नहीं देता है कि आपके पास डुप्लीकेट नहीं होंगे (और चूंकि यह केवल 32 बिट्स का उपयोग करता है, इसलिए आपको कुछ मिल जाएगा)।

Answer 6

जैसा कि यहां दिया गया जवाब है (यदि इनमें से अधिकतर हैंश टकराव के चेहरे में टूट जाते हैं) स्वीकार्य नहीं हैं तो आपको तारों के लापरवाह प्रतिनिधित्व का उपयोग करने की आवश्यकता होगी।

पायथन का zlib मॉड्यूल अंतर्निहित स्ट्रिंग संपीड़न क्षमताओं को प्रदान करता है और स्ट्रिंग को प्री-प्रोसेस करने के लिए इस्तेमाल किया जा सकता है इससे पहले कि आप उन्हें अपने सेट में रखें। ध्यान दें कि तारों को काफी लंबा होना चाहिए (जो आप संकेत देते हैं कि वे हैं) और अधिक मेमोरी स्पेस को बचाने के लिए न्यूनतम एन्ट्रॉपी है। अन्य संपीड़न विकल्प बेहतर स्थान बचत प्रदान कर सकते हैं और कुछ पायथन आधारित कार्यान्वयन here