R में LSre बाल्टियाँ बनाने का टेक्रस्यूज़ मूल मिन्हतेस से बड़ा क्यों होता है?

Question

जहां तक ​​मैं समझता हूं कि एलएसएच पद्धति का एक मुख्य कार्य अंतर्निहित हैश (अक्सर मिनहाश) से परे भी डेटा में कमी है। मैं textreuseआर में पैकेज का उपयोग कर रहा हूं , और यह उत्पन्न होने वाले डेटा के आकार से हैरान हूं। textreuseएक सहकर्मी की समीक्षा की गई ROpenSci पैकेज है, इसलिए मुझे लगता है कि यह अपना काम सही तरीके से करता है, लेकिन मेरा सवाल कायम है।

मान लीजिए कि मैं अपने माइनश और एलएसएच कार्यों के लिए क्रमश: 256 क्रमपरिवर्तन और 64 बैंड का उपयोग करता हूं - यथार्थवादी मूल्य जो अक्सर सापेक्ष निश्चितता (~ 98%) की समानता के साथ 50% से कम होने का पता लगाने के लिए उपयोग किया जाता है ।

यदि मेरे पास TextReuseTextDocument(256 परमिट) का उपयोग करके एक यादृच्छिक पाठ फ़ाइल है और इसे trtdमुझे असाइन करना है , तो मेरे पास होगा:

object.size(trtd$minhashes)
> 1072 bytes

अब इस ऑब्जेक्ट (64 बैंड) के लिए एलएसएच बकेट्स बनाते हैं और इसे असाइन करते हैं l, मेरे पास होगा:

object.size(l$buckets)
> 6704 bytes

तो, एलएसएच बाल्टियों में बनाए गए हैश की मूल मिनीशेस की तुलना में छह गुना बड़ा है। मैं समझता हूं कि ऐसा होता है क्योंकि बाल्टी हैश बनाने के लिए textreuse एक md5 डाइजेस्ट का उपयोग करता है ।

लेकिन क्या यह बहुत बेकार / ओवरकिल नहीं है, और क्या मैं इसे सुधार नहीं सकता हूं? क्या यह सामान्य है कि हमारी डेटा कम करने की तकनीक इस सीमा तक समाप्त हो रही है? और क्या यह मूल हैश के आधार पर दस्तावेजों से मेल खाने के लिए अधिक प्रभावशाली नहीं है (परमिट = 256 और बैंड = 256 के समान) और फिर झूठी सकारात्मकता को मातम करने के लिए एक सीमा का उपयोग करें?

ध्यान दें कि मैंने विशिष्ट ग्रंथों की समीक्षा की है जैसे कि माइनिंग डेटासैट का खनन , लेकिन यह प्रश्न इस विशेष कार्यान्वयन के बारे में है। यह भी ध्यान दें कि प्रश्न केवल जिज्ञासा से बाहर नहीं है, बल्कि आवश्यकता से बाहर है। जब आपके पास लाखों या अरबों हैश होते हैं, तो ये अंतर महत्वपूर्ण हो जाते हैं।

Answer 1

पैकेज लेखक यहाँ। हां, जरूरत से ज्यादा हैश / बैंड का इस्तेमाल करना बेकार होगा। (हालांकि हम यहां किलोबाइट के बारे में बात कर रहे हैं, जो मूल दस्तावेजों की तुलना में बहुत छोटा हो सकता है।)

सवाल यह है कि आपको क्या चाहिए? यदि आपको केवल ऐसे मैच ढूंढने की आवश्यकता है जो समान के करीब हों (यानी, जैक्सकार्ड स्कोर 1.0 के करीब), तो आपको विशेष रूप से संवेदनशील खोज की आवश्यकता नहीं है। यदि, हालांकि, आपको संभावित मिलानों का पता लगाने की आवश्यकता है जो केवल एक आंशिक ओवरलैप साझा करते हैं (यानी, एक जैकार्ड स्कोर जो 0 के करीब है), तो आपको अधिक हैश / बैंड की आवश्यकता होगी।

चूंकि आपने MMD पढ़ा है, आप वहां समीकरण देख सकते हैं। लेकिन यहां प्रलेखित पैकेज में दो कार्य हैं , जो आपको गणना करने में मदद कर सकते हैं कि आपको कितने हैश / बैंड की आवश्यकता है। lsh_threshold()पता लगाया जाएगा कि थ्रेशोल्ड जैकार्ड स्कोर की गणना करेगा; जबकि lsh_probability()आपको बताएंगे कि यह कैसे संभव है कि किसी दिए गए जैकार्ड स्कोर के साथ दस्तावेजों की एक जोड़ी का पता लगाया जाएगा। जब तक आपको अपने खोज समस्या के लिए इष्टतम हैश / बैंड की संख्या नहीं मिलती है, तब तक उन दो कार्यों के साथ खेलें।