12

如果我编写和使用 Lucene 执行搜索的算法，我该如何说明它的计算复杂性？我知道 Lucene 使用 tf*idf 评分，但我不知道它是如何实现的。我发现 tf*idf 具有以下复杂性：

O(|D|+|T|)

其中 D 是文档集，T 是所有术语的集。

但是，我需要有人可以检查这是否正确并解释我为什么。

谢谢

4

2 回答 2

12

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)是给定术语的已提交查询的权重。请注意，查询被视为 abag of words并且可以考虑权重向量（就好像它是另一个文档一样）。
  • wf(d,q)是查询和文档的对数项权重

如此处所述：向量点积的复杂度，向量点积为O(n)。这里的维度是我们词汇表中术语的数量：|T|，其中T是术语集。

因此，该算法的时间复杂度为：

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

我们认为 |Q| 固定，其中Q是查询中的单词集（平均大小很小，平均一个查询有 2 到 3 个词）并且D是所有文档的集合。

但是，对于搜索，这些集合是有界的，并且索引不会经常增长。因此，结果是，使用 VSM 的搜索速度非常快（当搜索量很大时T，D搜索速度真的很慢，必须找到一种替代方法）。

于 2012-08-31T10:19:09.957 回答
0

D是所有文档的集合

在（老实说，旁边）VSM 之前，调用布尔检索。因此，我们可以说d只匹配文档（几乎。好的。在最好的情况下）。由于Scores优先级队列（至少在 doc-at-time-scheme 中）是在堆上构建的，因此将每个队列d放入 take 中log(K)。因此我们可以将其估计为O(d·log(K))，这里我省略了，T因为预计查询很短。（否则，你就有麻烦了）。

http://www.savar.se/media/1181/space_optimizations_for_total_ranking.pdf

于 2018-08-15T13:21:10.177 回答