जब शब्द 200 मिलियन से अधिक होते हैं तो जावा का उपयोग करके डुप्लिकेट शब्दों को कैसे हटाया जाए?

Question

मेरे पास एक फ़ाइल है (आकार = ~ 1.9 जीबी) जिसमें ~ 220,000,000 (~ 220 मिलियन) शब्द/तार शामिल हैं। उनके पास नकल है, हर 100 शब्दों में लगभग 1 डुप्लिकेट शब्द।

मेरे दूसरे कार्यक्रम में, मैं फ़ाइल को पढ़ना चाहता हूं। मैं BufferedReader का उपयोग कर लाइनों द्वारा फ़ाइल को पढ़ने में सफल हूं।

अब डुप्लिकेट को निकालने के लिए, हम सेट का उपयोग कर सकते है (और यह कार्यान्वयन है), लेकिन के रूप में 3 विभिन्न परिदृश्यों में निम्न वर्णित सेट, समस्या है:

डिफ़ॉल्ट JVM आकार के साथ
1. , सेट अप 0.7- को शामिल कर सकते हैं 0.8 मिलियन शब्द, और फिर OutOfMemoryError।
2. 512 एम जेवीएम आकार के साथ, सेट में 5-6 मिलियन शब्द, और फिर ओओएम त्रुटि हो सकती है।
3. 1024 एम जेवीएम आकार के साथ, सेट में 12-13 मिलियन शब्द, और फिर ओओएम त्रुटि हो सकती है। सेट में 10 मिलियन रिकॉर्ड के अतिरिक्त होने के बाद, ऑपरेशन बेहद धीमी हो जाती है। उदाहरण के लिए, अगले ~ 4000 रिकॉर्ड के अलावा, इसमें 60 सेकंड लग गए।

मेरे पास प्रतिबंध हैं कि मैं JVM आकार को आगे नहीं बढ़ा सकता, और मैं फ़ाइल से डुप्लिकेट शब्दों को हटाना चाहता हूं।

अगर आपको ऐसी विशाल फ़ाइल से जावा का उपयोग करके डुप्लिकेट शब्दों को हटाने के लिए किसी अन्य तरीके/दृष्टिकोण के बारे में कोई जानकारी है, तो कृपया मुझे बताएं। बहुत धन्यवाद :)

प्रश्न के लिए जानकारी का जोड़: मेरे शब्द मूल रूप से अल्फा-न्यूमेरिक हैं और वे आईडी हैं जो हमारे सिस्टम में अद्वितीय हैं। इसलिए वे सादे अंग्रेजी शब्द नहीं हैं।

Answer 1

merge sort का उपयोग करें और दूसरे पास में डुप्लिकेट हटा दें। विलय करते समय आप डुप्लिकेट को भी हटा सकते हैं (केवल रैम में आउटपुट में जोड़ा गया नवीनतम शब्द रखें और उम्मीदवारों की तुलना करें)।

Answer 2

विशाल फ़ाइल को शब्द के पहले अक्षर के आधार पर 26 छोटी फ़ाइलों में विभाजित करें। यदि किसी भी पत्र फाइलें अभी भी बड़ी हैं, तो दूसरे अक्षर का उपयोग करके उस पत्र फ़ाइल को विभाजित करें।

डुप्लिकेट को हटाने के लिए Set का उपयोग करके प्रत्येक पत्र फ़ाइलों को अलग से संसाधित करें।

Answer 3

बड़ी फ़ाइलों के लिए मैं डेटा को स्मृति में पढ़ने की कोशिश नहीं करता बल्कि इसके बजाय मेमोरी मैप किए गए फ़ाइल पर काम करता हूं और ओएस पेज को आवश्यकतानुसार स्मृति में/आउट करने देता हूं। यदि आपके सेट स्ट्रक्चर में वास्तविक स्ट्रिंग्स की बजाय इस मेमोरी मैप की गई फ़ाइल में ऑफ़सेट हैं, तो यह काफी कम स्मृति का उपभोग करेगा। इस लेख को

की जांच:

http://javarevisited.blogspot.com/2012/01/memorymapped-file-and-io-in-java.html

Answer 4

मैं इस जावा में एक ही तरह से हर दूसरे भाषा के रूप में से निपटने चाहते हैं: एक डिडुप्लीकेशन फिल्टर और यह पाइप के रूप में अक्सर के रूप में आवश्यक लिखें।

• इनपुट पैरामीटर:: Offset, Size
• आकार Size के खोजने योग्य संरचना का आवंटन (= Set, लेकिन नहीं की जरूरत है एक हो)
• पढ़ें

  यह मैं (छद्म कोड में) क्या मतलब है Offset (या ईओएफ का सामना करना पड़ता है) stdin से तत्व और बस उन्हें

• पर पोस्ट करें Size स्टडीन (या ईओएफ) से elments, उन्हें सेट में स्टोर करें। यदि डुप्लिकेट करें, ड्रॉप करें, तो stdout पर लिखें।
• stdin EOF जब तक है, अगर वे Set में हैं तो छोड़, बाकी लिखने से पढ़ें तत्वों

अब पाइप के रूप में कई मामलों stdout के रूप में आप की जरूरत है (भंडारण कोई समस्या नहीं है, शायद ही के रूप में कई आप के रूप में कोर) Offset एस और सेन Size बढ़ने के साथ। यह आपको अधिक कोर का उपयोग करने देता है, क्योंकि मुझे संदेह है कि प्रक्रिया सीपीयू बाध्य है। यदि आप जल्दी में हैं तो आप netcat का उपयोग भी कर सकते हैं और अधिक मशीनों पर प्रसंस्करण फैल सकते हैं।

Answer 5

इस तरह की समस्या को हल करने का एक क्लासिक तरीका Bloom filter है। असल में आप अपने शब्द को कई बार हश करते हैं और प्रत्येक हैश परिणाम के लिए थोड़ा बिट वेक्टर में कुछ बिट सेट करते हैं। यदि आप एक शब्द की जांच कर रहे हैं और उसके हैंश से सभी बिट्स आपके पास संभवतः वेक्टर में सेट हैं (आप वेक्टर में हैंश/बिट्स की संख्या को बढ़ाकर मनमाने ढंग से कम कर सकते हैं) इसे पहले देखा और यह एक डुप्लिकेट है ।

यह कितना जल्दी वर्तनी जांचकर्ता काम करता था। वे जानते थे कि शब्द में शब्द था या नहीं, लेकिन वे आपको नहीं बता सके कि सही वर्तनी क्या थी क्योंकि यह केवल आपको बताती है कि वर्तमान शब्द देखा गया है या नहीं। कर रहे हैं इन वास्तव में शब्दों, या वे कुछ और कर रहे हैं - वाक्यांशों, भाग संख्या, आदि:

वहाँ सहित java-bloomfilter

Answer 6

प्रश्न वहाँ खुला स्रोत कार्यान्वयन के एक नंबर रहे हैं?

एक सामान्य बोली जाने वाली भाषा में शब्द के लिए एक उम्मीद करेगा कि पहले कुछ हज़ारों के बाद आपको सबसे अनोखे शब्द मिलेंगे, इसलिए आपको वास्तव में एक शब्द पढ़ना है, इसे एक शब्दकोश के विरुद्ध जांचें , अगर पाया जाता है, तो इसे नहीं मिला, तो इसे शब्दकोश में जोड़ें और इसे लिखें।

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

Answer 7

यदि आप आइटम को सॉर्ट करते हैं, तो डुप्लिकेट का पता लगाना और निकालना आसान होगा, क्योंकि डुप्लिकेट एक साथ गुच्छा करेंगे।

वहाँ आप बड़ी फ़ाइल mergesort लिए इस्तेमाल कर सकते हैं यहाँ कोड है: http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

Answer 8

आप (बैच आवेषण का उपयोग करके) एक डेटाबेस की एक अस्थायी तालिका में शब्द डालने के लिए posibility है, तो यह एक होगा उस तालिका की ओर अलग चुनें।

Answer 9

क्विक्सोर्ट इस मामले में विर्जोर्ट पर एक अच्छा विकल्प होगा क्योंकि इसे कम स्मृति की आवश्यकता है। This thread के बारे में एक अच्छी व्याख्या है क्यों।

Answer 10

आप एक पास में नौकरी करने के लिए trie डेटा संरचना का उपयोग करने में सक्षम हो सकते हैं। इसमें फायदे हैं जो इस प्रकार की समस्या के लिए अनुशंसा करते हैं। लुकअप और डालने जल्दी हैं। और इसका प्रतिनिधित्व अपेक्षाकृत अंतरिक्ष कुशल है। आप राम में अपने सभी शब्दों का प्रतिनिधित्व करने में सक्षम हो सकते हैं।

Answer 11

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

for(word : stream) { 
    if(!DB.exists(word)) { 
    DB.put(word) 
    outstream.add(word) 
    } 
} 

समस्या आसान सार में है, तो आप डिस्क पर चीजों को स्टोर करने की जरूरत है क्योंकि पर्याप्त स्मृति या तो छँटाई हे उपयोग नहीं है वहाँ है, तो ऐसा (एन लॉग ऑन एन) (अनावश्यक) या हैशिंग ओ (एन) अद्वितीय शब्दों को खोजने के लिए।

यदि आप एक समाधान चाहते हैं जो बहुत अधिक काम करेगा लेकिन ऐसा करने की गारंटी नहीं है तो एलआरयू प्रकार हैश तालिका का उपयोग करें। अनुभवजन्य Zpif's law के अनुसार आपको ठीक होना चाहिए।

वहां कुछ स्मार्ट लड़के के लिए एक फॉलो अप प्रश्न, अगर मेरे पास 64-बिट मशीन है और 12 जीबी कहने के लिए ढेर आकार सेट करें, तो वर्चुअल मेमोरी समस्या का ख्याल नहीं रखनी चाहिए (हालांकि इष्टतम तरीके से नहीं) जावा इस तरह से डिजाइन नहीं किया गया है?

Answer 12

यहां तक ​​कि अंग्रेजी में, जिसमें प्राकृतिक भाषा के लिए बड़ी संख्या में शब्द हैं, ऊपरी अनुमान केवल 80000 शब्द हैं। उस आधार पर, आप सिर्फ एक HashSet का उपयोग करें और अपने सभी शब्द यह जोड़ सकता है (शायद सभी लोअर केस में मामले के मुद्दों से बचने के लिए):

Set<String> words = new HashSet<String>(); 
while (read-next-word) { 
    words.add(word.toLowerCase()); 
} 

वे असली शब्द हैं, तो यह स्मृति समस्याओं के कारण नहीं जा रहा है , भी बहुत तेज़ होगा!

Answer 13

अधिकतर सहायक समाधान अनावश्यक सामान को छोड़ने से उत्पन्न होते हैं। आप केवल डुप्लीकेट के लिए देखते हैं, इसलिए केवल शब्दों को स्टोर न करें, स्टोर हैंश करें। लेकिन प्रतीक्षा करें, आप हैंश में रुचि नहीं रखते हैं, केवल तभी जब वे पहले से ही देख चुके हैं - उन्हें स्टोर न करें। वास्तव में बड़ी संख्या के रूप में हैश का इलाज करें, और यह देखने के लिए कि क्या आप पहले से ही यह संख्या देख चुके हैं, बिटसेट का उपयोग करें।

तो आपकी समस्या हैश चौड़ाई के आधार पर आकार के साथ वास्तव में बड़े स्पैस आबादी वाले बिटमैप तक उबालती है। यदि आपका हैश 32 बिट तक है, तो आप riak बिटमैप का उपयोग कर सकते हैं।

... 128+ बिट के लिए वास्तव में बड़ी बिटमैप के बारे में सोच चला% हैश) (मैं वापस हो जाएगा)

समाधान के लिए