快速高效的數組計算

我想統計文檔中特定短語的出現次數。例如「stackoverflow論壇」。假設D表示包含這兩個詞的文檔集。快速高效的數組計算

現在，假設我有下面的數據結構：

A[numTerms][numMatchedDocuments][numOccurInADocument]

其中numMatchedDocuments是d和numOccurInADocument的尺寸是一個特定的文檔中出現的特定術語出現的次數，例如：

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

表示術語「堆棧溢出」出現在文檔「document1」中並且其第一次出現在位置「3」處。

然後我選擇發生最少的術語並遍歷所有位置，以查找「論壇」是否出現在位置+1當前術語「stackoverflow」位置。換句話說，如果我在位置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; 
    } 
} 
}

來源

2012-12-18 DotNet

也許在代碼中發佈您的當前實現僅供參考。 – OmniOwl

你的問題是什麼？ –

@MelNicholson ......但不知道算法上是否有更好的方法。 – DotNet

正如我在評論中提到，Suffix Array可以解決這類問題。我用一個簡單的c＃實現了一個後綴數組來回答類似的問題（Fastest way to search a list of names in C#）。

基本思想是你有一個索引對的數組，指向文檔索引和該文檔中的一個位置。索引對代表從文檔中的該點開始並繼續到文檔結尾的字符串。但實際的文件及其內容只在您的原始商店中存在一次。後綴數組只是這些索引對的數組，每個文檔中的每個位置都有一對。然後按照它們指向的文本的順序對後綴數組進行排序。一旦排序，您現在可以通過在後綴數組上執行簡單的二進制搜索，在任何文檔中快速找到任何短語。構建（主要是分類）後綴數組可能是耗時的。但一旦建成，搜索速度非常快。由於實際的文檔內容只存在一次，因此內存相當簡單。

將它擴展到返回每個文檔中詞組匹配的計數是微不足道的。

這與後綴數組的經典描述有些不同，他們通常在討論後綴數組在單個超大字符串上的操作。但是，使其適用於字符串/文檔數組的更改並不是很大，但它可以增加後綴數組佔用的內存量，具體取決於文檔的最大數量和最大文檔長度，以及如何編碼索引對。

來源

2012-12-18 01:24:52 hatchet

快速高效的數組計算

回答

相關問題