जावा में सबसे अधिक प्रभावी तरीका टेक्स्ट को अपनी आवृत्ति के साथ 50 से अधिक बार प्राप्त करने के लिए क्या है?अधिकतर लगातार शब्द
मैं लगभग ~ 10,000,000 ग्रंथों को खोजना चाहता हूं जिनमें प्रत्येक के पास लगभग 10,000 शब्द हैं और उम्मीद है कि यह एक उचित समय सीमा में काम करता है।
अधिकतर कुशल Patricia trie का उपयोग कर रहे हैं जो max-heap से लिंक करता है। प्रत्येक बार जब आप एक शब्द पढ़ते हैं, find इसे त्रिभुज पर, ढेर और increase-key पर जाएं। यदि यह trie में नहीं है, add इसे और ढेर में अपनी कुंजी उचित रूप से सेट करें।
Fibonacci heap, increase-keyO(1) है।
एक तो अनुचित नहीं समाधान एक Map<String, Integer> उपयोग करने के लिए, गिनती हर बार एक शब्द का सामना करना पड़ा है जोड़ने है, और फिर शीर्ष 50
हैं पाने के लिए गणना के आधार पर कस्टम छँटाई अपनी entrySet()O(N log N) सॉर्ट अस्वीकार्य है, में शीर्ष 50 को खोजने के लिए selection algorithm का उपयोग करें।
कौन सा तकनीक वास्तव में बेहतर है आप जो चाह रहे हैं पर निर्भर करता है (अर्थात टिप्पणी है कि क्या यह एक [java] सवाल से एक [algorithm] प्रश्न के और अधिक बहुत कह है)।
Map<String, Integer> चयन एल्गोरिदम के बाद सबसे व्यावहारिक है, लेकिन पेट्रीसिया ट्राई समाधान अकेले अंतरिक्ष दक्षता में इसे धड़कता है (क्योंकि सामान्य उपसर्गों को अनावश्यक रूप से संग्रहीत नहीं किया जाता है)।
एन शब्दों के साथ बड़े पाठ में अद्वितीय शब्दों की संख्या आमतौर पर बहुत कम (एन >> यू) है। नक्शा हर बार जीतता है, क्योंकि यू में शब्द चमकने के लिए पर्याप्त नहीं हैं, और इसे लागू करने के लिए बहुत आसान है। इसके अलावा, ओ (एन) >> ओ (यू लॉग यू): सॉर्टिंग तुलनात्मक रूप से सस्ते है। – tucuxi
आपके नोटेशन से, Ptrie में 'यू' शब्द होंगे, इसलिए मुझे यकीन नहीं है कि आपकी शिकायत क्या है। – polygenelubricants
छोटे स्ट्रिंग (= शब्द) आकारों के लिए हैशमैप्स की तुलना में पेस्ट्री तेज नहीं हैं, और इसलिए समस्या के लायक नहीं हैं। अगर मैं लंबे सबस्ट्रिंग खोजने की ज़रूरत है तो मैं निश्चित रूप से उनका उपयोग करूंगा; लेकिन यह समस्या आप बाहर के शेल्फ कंटेनरों के साथ हल कर सकते हैं। – tucuxi
आपका सबसे अच्छा मौका ओ (एन) एल्गोरिदम होगा, मैं एक पाठ पाठक के लिए जाऊंगा जो शब्दों को विभाजित करेगा और फिर इसे एक आदेशित पेड़ में जोड़ें, जिसे आप उपस्थितियों की संख्या से आदेश देंगे और उन्हें लिंक करेंगे एक शब्द। इसके बाद उच्चतम मूल्य प्राप्त करने के लिए केवल 50-पुनरावृत्तियों को पार करें।
आदेशित पेड़ को कैसे जोड़ना ओ (एन) होगा? –
O(n):
बेशक इस चरणों में से कुछ आप का उपयोग करेंगे डेटा संरचनाओं के आधार पर एक ही समय में किया जा सकता है या अनावश्यक पाने के लिए शब्द की कुल संख्या से उन्हें विभाजित
बाद स्यूडोकोड चाल करना चाहिए:
build a map<word, count>
build a tokenizer that gives you a word per iteration
for each word*,
if word in map, increment its count
otherwise add with count = 1
sort words by count
for each of the first 50 words,
output word, frequency = count/total_words
यह अनिवार्य रूप से हे (एन) है, और क्या jpabluz का सुझाव दिया। हालांकि, अगर आप किसी भी प्रकार के "जंगली" पाठ पर इसका उपयोग करने जा रहे हैं, तो आपको बहुत सारे कचरे का पता चल जाएगा: अपरकेस/लोअरकेस, विराम चिह्न, यूआरएल, स्टॉप-शब्द जैसे 'द' या 'और' बहुत अधिक गणना, एक ही शब्द के कई बदलाव ...ऐसा करने का सही तरीका सभी शब्दों को कम करना है, सभी विराम चिह्न (और यूआरएल जैसी चीजें) को हटाएं, और उपरोक्त छद्म कोड में तारांकन के साथ चिह्नित बिंदु पर स्टॉप-वर्ड हटाने और स्टेमिंग जोड़ें।
"यह अनिवार्य रूप से ओ (एन)" है - यह तब होता है जब इनपुट में शब्दों की संख्या 'एन' है। यदि 'यू' अद्वितीय शब्दों की संख्या है, तो "गिनती से शब्दों को क्रमबद्ध करें" है 'ओ (यू लॉग यू)'। आप वास्तव में चयन एल्गोरिदम का उपयोग करके 'ओ (यू)' में शीर्ष 50 (अनियंत्रित) प्राप्त कर सकते हैं। – polygenelubricants
चूंकि एन >> यू किसी भी सबसे संक्षिप्त ग्रंथों के लिए, ओ (एन) ओ (यू लॉग यू) पर हावी होगा। हां, अधिकतम-ढेर कुछ समय बंद हो जाता है, लेकिन लाभ बहुत छोटा है, और यह मुफ़्त नहीं है (अतिरिक्त कोड जटिलता)। – tucuxi
मुझे गलत मत समझो, आपका जवाब अनुचित नहीं है और यह बहुत व्यावहारिक है (जैसा कि मैंने इसे अपने उत्तर में एक विकल्प के रूप में भी उल्लेख किया है), लेकिन ओपी "सबसे कुशल" मांगता है, और स्पष्ट रूप से Ptrie मानचित्र से अधिक स्थान कुशल है चाबियों के रूप में पूरे शब्दों को संग्रहित करना। – polygenelubricants
क्या यह होमवर्क है? – XpiritO
होमवर्क टिप्पणी के लिए संदिग्ध। –
यह एक जावा प्रश्न की तुलना में एक एल्गोरिदमिक प्रश्न की तरह लगता है। –