सरणी पर तेज और कुशल गणना

Question

मैं किसी दस्तावेज़ में किसी विशेष वाक्यांश के लिए घटनाओं की संख्या को गिनना चाहता हूं। उदाहरण के लिए "stackoverflow मंच"। मान लीजिए डी दोनों शर्तों वाले दस्तावेज़ के साथ सेट दस्तावेज़ों का प्रतिनिधित्व करता है।

अब, मान लीजिए मैं निम्न डेटा संरचना है:

:

A[numTerms][numMatchedDocuments][numOccurInADocument] 

जहां numMatchedDocuments विकास तथा numOccurInADocument के आकार है उदाहरण के लिए, घटनाओं की संख्या किसी विशेष शब्द एक विशेष दस्तावेज़ में होता है

A[stackoverflow][document1][occurance1]=3; 

का अर्थ है, "stackoverflow" शब्द दस्तावेज़ "दस्तावेज़ 1" में होता है और इसका पहला मौका "3" स्थिति में होता है।

तब मैं उस शब्द को चुनता हूं जो कम से कम और लूप होता है ताकि यह पता चल सके कि "फोरम" स्थिति में "फोरम" वर्तमान शब्द "स्टैक ओवरफ्लो" स्थिति में होता है या नहीं। दूसरे शब्दों में, अगर मुझे स्थिति 4 पर "फोरम" मिलता है तो यह एक वाक्यांश है और मुझे इसके लिए एक मैच मिला है।

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

धन्यवाद,

psudo-कोड:

boolean docPhrase=true; 
int numOfTerms=2; 
// 0 for "stackoverflow" and 1 for "forums" 
for (int d=0;d<D.size();d++){ 
//D is a set containing the matched documents 
int minId=getTheLeastOccuringTerm(); 
for (int i=0; i<A[minId][d].length;i++){ // For every position for LeastOccuringTerm 
    for(int t=0;t<numOfTerms;t++){ // For every terms 
     int id=BinarySearch(A[t][d], A[minId][d][i] - minId + t); 
     if (id<0) docPhrase=false; 
    } 
} 
} 

Answer 1

मैं टिप्पणी में उल्लेख किया है, Suffix Array समस्या की इस तरह हल कर सकते हैं। मैंने एक समान प्रश्न (Fastest way to search a list of names in C#) का उत्तर दिया एक सफ़िक्स ऐरे के एक सरल सी # कार्यान्वयन के साथ।

मूल विचार यह है कि आपके पास इंडेक्स जोड़े की एक सरणी है जो दस्तावेज़ अनुक्रमणिका को इंगित करती है, और उस दस्तावेज़ के भीतर एक स्थिति है। इंडेक्स जोड़ी उस स्ट्रिंग का प्रतिनिधित्व करती है जो दस्तावेज़ में उस बिंदु से शुरू होती है, और दस्तावेज़ के अंत तक जारी है। लेकिन वास्तविक दस्तावेज और उनकी सामग्री आपके मूल स्टोर में केवल एक बार मौजूद है। प्रत्यय ऐरे इन इंडेक्स जोड़े की एक सरणी है, जिसमें प्रत्येक दस्तावेज़ में प्रत्येक स्थिति के लिए एक जोड़ी है। फिर आप उस पाठ के क्रम में प्रत्यय ऐरे को सॉर्ट करते हैं जो वे इंगित करते हैं। एक बार सॉर्ट हो जाने पर, अब आप प्रत्यय ऐरे पर एक साधारण बाइनरी खोज करके किसी भी दस्तावेज़ के बीच किसी भी वाक्यांश को तुरंत खोज सकते हैं। सफ़िक्स ऐरे का निर्माण (मुख्य रूप से सॉर्टिंग) समय लेने वाला हो सकता है। लेकिन एक बार बनाया गया, यह खोजना बहुत तेज़ है। यह स्मृति पर काफी आसान है क्योंकि वास्तविक दस्तावेज़ सामग्री केवल एक बार मौजूद है।

प्रत्येक दस्तावेज़ में वाक्यांश मिलानों की संख्या को वापस करने के लिए इसे विस्तारित करना मुश्किल होगा।

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