配列の高速かつ効率的な計算

Question

文書内の特定のフレーズの出現回数を数えたいと思います。たとえば、 "stackoverflow forums"などです。 Dは、両方の用語を含む文書で設定された文書を表しているとします。今

、私は次のようなデータ構造を有していると仮定：

numMatchedDocumentsはDの大きさであり、numOccurInADocumentは、特定の用語は、例えば、特定のドキュメントで発生する発生回数である

A[numTerms][numMatchedDocuments][numOccurInADocument] 

：

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

という用語は、文書「document1」に「stackoverflow」という用語があり、最初の出現が位置「3」にあることを意味します。

次に、 "forum"が現在の用語 "stackoverflow"の位置+ 1にあるかどうかを調べるために、すべての位置でループしているループを探します。言い換えれば、私がポジション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#）にサフィックス配列の単純なC＃実装で答えました。

基本的な考え方は、ドキュメントインデックスとそのドキュメント内の位置を指すインデックスペアの配列があることです。インデックスのペアは、ドキュメント内のそのポイントから始まり、ドキュメントの最後まで続く文字列を表します。しかし、実際の文書とその内容は元の店に1回しか存在しません。サフィックス配列は、これらのインデックスペアの配列にすぎず、すべてのドキュメント内のすべての位置に一対があります。次に、それらが指すテキストの順にサフィックス配列をソートします。並べ替えが完了したら、Suffix Arrayで簡単なバイナリ検索を実行することで、ドキュメントの中の任意のフレーズをすばやく見つけることができるようになりました。サフィックス配列の構築（主にソート）には時間がかかることがあります。しかし、一度構築されると、それは検索するのが非常に高速です。実際のドキュメントの内容は1度しか存在しないので、メモリ上ではかなり簡単です。

各ドキュメント内のフレーズ一致のカウントを返すように拡張することは自明です。

これは、サフィックス配列の古典的な記述とは少し異なります。サフィックス配列は、通常、1つの非常に大きな文字列で動作するサフィックス配列について言及しています。しかし、文字列/ドキュメントの配列に対応するための変更はそれほど大きくはありませんが、ドキュメントの最大数とドキュメントの最大長に応じてサフィックス配列が消費するメモリ量を増やすことができます。インデックスのペア。