12

Lucene を使用して検索を実行するアルゴリズムを記述した場合、その計算の複雑さをどのように述べることができますか? Lucene が tf*idf スコアリングを使用していることは知っていますが、それがどのように実装されているかはわかりません。tf*idf には次の複雑さがあることがわかりました。

O(|D|+|T|)

ここで、D はドキュメントのセット、T はすべての用語のセットです。

ただし、これが正しいかどうかを確認し、その理由を説明できる人が必要です。

ありがとうございました

4

2 に答える 2

12

Lucene は基本的にVector Space Model(VSM) とtf-idfスキームを使用します。したがって、標準設定では次のようになります。

  • それぞれがベクトルとして表されるドキュメントのコレクション
  • ベクトルとしても表されるテキスト クエリ

Kクエリで最高のベクトル空間スコアを持つコレクションのドキュメントを決定しますq。通常、スコアの降順で並べられた上位 K 個のドキュメントを探します。たとえば、多くの検索エンジンは K = 10 を使用して、10 件の最良の結果の最初のページを取得し、ランク付けします。

ベクトル空間スコアを計算するための基本的なアルゴリズムは次のとおりです。

float Scores[N] = 0
Initialize Length[N]
for each query term t
do calculate w(t,q) and fetch postings list for t (stored in the index)
    for each pair d,tf(t,d) in postings list
    do Scores[d] += wf(t,d) X w(t,q)  (dot product)
Read the array Length[d]
for each d
do Scored[d] = Scores[d] / Length[d]
return Top K components of Scores[]

どこ

  • 配列Lengthは各ドキュメントの長さ (正規化係数) を保持しN 、配列Scoresは各ドキュメントのスコアを保持します。
  • tfドキュメント内の用語の用語頻度です。
  • w(t,q)特定の用語に対して送信されたクエリの重みです。クエリは として扱われ、bag of words重みのベクトルは (別のドキュメントであるかのように) 考慮できることに注意してください。
  • wf(d,q)は、クエリとドキュメントの対数項の重み付けです

ここで説明されているように:ベクトル内積の複雑さ、ベクトル内積はO(n)です。ここで、次元は語彙の用語の数です。|T|ここで、Tは用語のセットです。

したがって、このアルゴリズムの時間計算量は次のとおりです。

O(|Q|· |D| · |T|) = O(|D| · |T|)

|Q| を考慮します。ここQで、 はクエリ内の単語のセット (平均サイズは小さく、クエリには平均で 2 ～ 3 個の用語があります) でありD、すべてのドキュメントのセットです。

ただし、検索の場合、これらのセットは制限されており、インデックスが頻繁に大きくなる傾向はありません。したがって、結果として、VSM を使用した検索は非常に高速です (TとDが大きい場合、検索は非常に遅くなり、別の方法を見つける必要があります)。

于 2012-08-31T10:19:09.957 に答える