问题 Lucene搜索的复杂性

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) 是给定术语的已提交查询的权重。请注意，查询被视为a 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 很大，搜索非常慢，人们必须找到另一种方法）。

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) 是给定术语的已提交查询的权重。请注意，查询被视为a 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 很大，搜索非常慢，人们必须找到另一种方法）。