lucene - 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 个 top 文档；例如，许多搜索引擎使用 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 很大时，搜索确实很慢，必须找到替代方法)。