Luceneの検索の複雑さ

Question

Luceneを使用して検索を実行するアルゴリズムを書くと、その計算の複雑さをどのように表現できますか？私はLuceneがtf * idfスコアリングを使用していることを知っていますが、実装方法がわかりません。私は、TFの*のIDFは、以下の複雑さを持っていることを発見しました：Dは、文書やTすべての用語の集合の集合である

O(|D|+|T|) 

。

しかし、これが正しいかどうかをチェックして理由を説明できる人が必要です。

が

Answer 1

ありがとうLuceneには、基本的にtf-idfスキームでVector Space Model（VSM）を使用しています。だから、私たちは、標準設定で：

• ベクトル
• もベクトル

として表さテキストクエリとして表されたドキュメントの各コレクションの我々はとコレクションのK文書を決定しますクエリの最高ベクトル空間スコアはqです。典型的には、スコア順に並べられたこれらのK個のトップ文書を、降順で検索する。例えば、多くの検索エンジンは、10個の最良結果のうちの最初のページを検索し順位を付けるためにK = 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)は、クエリと文書

対数用語の重みである：Complexity of vector dot-product、ベクトルドット積はO(n)あります。ここでの次元は語彙の用語の数です：|T|、ここでTは用語の集合です。

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

我々は考える

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

| Q |ここで、Qはクエリ内の単語の集合です（平均サイズは小さく、平均でクエリは2〜3項です）。Dはすべてのドキュメントの集合です。

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