Lucene搜索的复杂性

Question

如果我编写并使用Lucene执行搜索的算法,我如何说明它的计算复杂性？我知道Lucene使用tf*idf得分,但我不知道它是如何实现的.我发现tf*idf具有以下复杂性:

O(|D|+|T|) 

其中D是文档集,T是所有术语集.

但是,我需要有人能够检查这是否正确并解释原因.

谢谢

Answer 1

Lucene基本上使用Vector Space Model带有tf-idf方案的(VSM).因此,在标准设置中,我们有:

• 每个文档的集合,每个文档表示为向量
• 文本查询也表示为向量

我们确定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)是给定术语的已提交查询的权重.请注意,查询被视为a bag of words,可以考虑权重向量(就好像它是另一个文档).
• wf(d,q) 是查询和文档的对数项加权

如下所述:矢量点积的复杂性,矢量点积O(n).这里的维度是我们词汇表中术语的数量:,术语集在|T|哪里T.

因此,该算法的时间复杂度为:

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

我们考虑| Q | fixed,Q查询中的单词集合(平均大小较低,平均查询有2到3个术语),并且D是所有文档的集合.

但是,对于搜索,这些集合是有界的,索引不会经常增长.因此,使用VSM进行搜索的速度非常快(当T且D搜索速度非常快且需要找到替代方法时).