बड़ी फ़ाइल में डुप्लिकेट स्ट्रिंग खोजें

Question

एक फ़ाइल में बड़ी संख्या में (उदाहरण के लिए 10 बिलियन) स्ट्रिंग हैं और आपको डुप्लिकेट स्ट्रिंग्स खोजने की आवश्यकता है। आपके पास एन सिस्टम उपलब्ध हैं। आपको डुप्लिकेट

Answer 1

फ़ाइल को एन टुकड़ों में विभाजित कैसे मिलेगा। प्रत्येक मशीन पर, जितना संभव हो उतना टुकड़ा लोड करें, और स्ट्रिंग को सॉर्ट करें। उस मशीन पर बड़े पैमाने पर भंडारण के लिए इन हिस्सों को लिखें। प्रत्येक मशीन पर, हिस्सों को एक ही स्ट्रीम में मर्ज करें, और उसके बाद स्ट्रीम को प्रत्येक मशीन से उस स्ट्रीम में मर्ज करें जिसमें सॉर्ट किए गए क्रम में सभी स्ट्रिंग शामिल हों। पिछले के साथ प्रत्येक स्ट्रिंग की तुलना करें। यदि वे वही हैं, तो यह एक डुप्लिकेट है।

Answer 2

एरिक्सन का जवाब शायद इस प्रश्न को सेट करने वाले किसी भी व्यक्ति द्वारा अपेक्षित है।

आप एक hashtable में एक बाल्टी के रूप में एन मशीनों में से प्रत्येक के इस्तेमाल कर सकते हैं: प्रत्येक स्ट्रिंग के लिए

• , (जैसे कि स्ट्रिंग संख्या मैं अनुक्रम में) एक हैश समारोह उस पर गणना, ज।
• स्टोरेज के लिए मशीन नंबर एन के लिए i और h के मानों को भेजें, जहां n = h% N.
• प्रत्येक मशीन से, सभी हैश मानों की एक सूची पुनर्प्राप्त करें जिसके लिए एक से अधिक अनुक्रमणिका प्राप्त हुईं, साथ में इंडेक्स की सूची के साथ।
• समान हैश मानों के साथ तारों के सेट की जांच करें, यह देखने के लिए कि वे वास्तव में बराबर हैं या नहीं।

ईमानदार होने के लिए, हालांकि, 10 अरब तारों के लिए आप संभवतः 1 पीसी पर ऐसा कर सकते हैं। सटीक हैशटेबल कार्यान्वयन के आधार पर हैशटेबल 32 बिट हैश के साथ 80-120 जीबी की तरह कुछ पर कब्जा कर सकता है। यदि आप एक कुशल समाधान की तलाश में हैं, तो आपको "मशीन" से थोड़ा सा विशिष्ट होना चाहिए, क्योंकि यह निर्भर करता है कि प्रत्येक के पास कितना संग्रहण है, और नेटवर्क संचार की सापेक्ष लागत।