Lucene的搜索的複雜性

Question

如果我使用Lucene編寫和執行搜索的算法，我該如何說明它的計算複雜度？我知道Lucene使用tf * idf評分，但我不知道它是如何實現的。我發現tf * idf具有以下複雜性：

O(|D|+|T|) 

其中D是文檔集合，T是所有術語集合。

但是，我需要有人可以檢查這是否正確，並解釋我爲什麼。

謝謝

Answer 1

Lucene的基本使用Vector Space Model（VSM）與tf-idf方案。因此，在制定標準有：

• 文檔的集合各自表示爲矢量
• 文本查詢也表示爲矢量

我們決定收集與K文件查詢q上的最高矢量空間分數。通常情況下，我們會按照降序排列的方式查找這些K個頂級文檔，例如許多搜索引擎使用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很大時，搜索速度非常慢，而且必須找到另一種方法）。