6

ドキュメント内の特定のフレーズの出現回数をカウントしたいと考えています。たとえば、「stackoverflow フォーラム」。Dが、両方の用語を含むドキュメントを含むドキュメント セットを表しているとします。

ここで、次のデータ構造があるとします。

A[numTerms][numMatchedDocuments][numOccurInADocument]

ここで、numMatchedDocuments は D のサイズであり、numOccurInADocument は特定のドキュメントで特定の用語が出現する回数です。次に例を示します。

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

つまり、「stackoverflow」という用語がドキュメント「document1」に出現し、その最初の出現が位置「3」にあることを意味します。

次に、出現頻度が最も低い用語を選択し、そのすべての位置をループして、現在の用語「stackoverflow」の位置 + 1 で「フォーラム」が出現するかどうかを調べます。つまり、4 番目の位置に「フォーラム」が見つかった場合、それはフレーズであり、一致するものを見つけたことになります。

マッチングはドキュメントごとに簡単で、かなり高速に実行されますが、ドキュメントの数が 2,000,000 を超えると非常に遅くなります。私はそれをコアに分散しましたが、もちろん高速になりますが、アルゴリズム的にこれを行うより良い方法があるかどうか疑問に思います。

ありがとう、

疑似コード:

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;
   }
 }
}
4

1 に答える 1

2

コメントで述べたように、Suffix Arrayはこの種の問題を解決できます。同様の質問 ( C# で名前のリストを検索する最速の方法) に、サフィックス配列の単純な c# 実装を使用して答えました。

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

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

これは、単一の非常に大きな文字列を操作するサフィックス配列について通常話しているサフィックス配列の古典的な説明とは少し異なります。ただし、文字列/ドキュメントの配列で機能させるための変更はそれほど大きくありませんが、ドキュメントの最大数とドキュメントの最大長、およびコードのエンコード方法に応じて、サフィックス配列によって消費されるメモリ量が増加する可能性があります。インデックス ペア。

于 2012-12-18T01:24:52.177 に答える