2

次のクエリをサポートするように、全長nのSドキュメントのコレクションのインデックス作成に役立つデータ構造を構築しています。2つの単語P1とP2が与えられた場合、P1を含むがP2を含まないすべてのドキュメントをカウントします。答えを完全なものにしたい（結果を見逃さないようにする）。

一般化された接尾辞木を作成し、すべてのsqrt（n）番目の葉とその祖先を選択します（そして、すべての1子ノードを削除します）。内部ノードごとにvノードuに対するクエリの回答を事前に計算します。

しかし、これにより、ノードvとuのツリーに表示される単語がクエリに含まれている場合、O（1）で答えを得ることができますが、選択したノードの1つに単語がない場合はどうすればよいですか？

前処理でO（n 2）データ構造を維持し、O（1）時間検索の準備ができているすべての可能な答えを用意することで簡単にそれを行うことができますが、目標はO（n）空間でこのデータ構造を構築することです。クエリを可能な限り効率的にします。

4

1 に答える 1

2

転置インデックスはまだあなたに役立つように思えます。これは、単語を含むドキュメントの順序付きリストへの単語のマップです。ドキュメントは、共通の全体的な順序である必要があり、単語ごとのバケットに表示されるのはこの順序です。

あなたが単語の出現nにおけるコーパスの全長（語彙のサイズではない）であると仮定すると、それは時間と線形空間で構築することができます。O(n log n)

とを指定するP1とP2、2つの個別のクエリを実行して、それぞれ2つの用語を含むドキュメントを取得します。P12つのリストは共通の順序を共有しているため、線形マージのようなアルゴリズムを実行して、以下を含むが含まないドキュメントのみを選択できますP2。

c1 <- cursor to first element of list of docs containing P1
c2 <- cursor to first element of list of docs containing P2
results <- [] # our return value

while c1 not exhausted
  if c2 exhausted or *c1 < *c2
    results.append(c1++)
  else if *c1 == *c2
    c1++
    c2++
  else # *c1 > *c2
    c2++

return results

ループのすべてのパスが少なくとも1つのカーソルを繰り返すことに注意してください。2つの初期クエリのサイズの合計で線形時間で実行されます。c1カーソルからのものだけが入るresultsので、すべての結果にが含まれていることがわかりますP1。

最後に、常に「遅れている」カーソルのみを進めることに注意してください。これ（およびドキュメントの順序の合計）は、ドキュメントが両方の初期クエリに表示される場合、両方のカーソルがそのドキュメントを指すループ反復があることを保証します。この反復が発生すると、必ず中央の句が開始され、両方のカーソルを進めることでドキュメントがスキップされます。したがって、を含むドキュメントはP2必ずしもに追加されませんresults。

このクエリは、ブールクエリと呼ばれる一般的なクラスの例です。このアルゴリズムを拡張して、ほとんどすべてのブール式をカバーすることができます。特定のクエリはアルゴリズムの効率を損ないます（語彙スペース全体を強制的にウォークオーバーすることにより）が、基本的に各用語を否定しない限り（つまり、要求しない限りnot P1 and not P2）問題ありません。詳細な治療法については、こちらをご覧ください。

于 2012-06-20T07:04:41.310 に答える