Lucence 中的排序算法解析

排序采用下面的算法：

score(q,d) = sum( tf(t in d) * idf(t) * getBoost(t.field in d) * lengthNorm(t.field in d) ) * coord(q,d) * queryNorm(q)。 

q 是查询 d 是一篇文章， score 表示 q 在 d 中的评分。

t 表示 q 的一个部分，一个词汇： 比如，中国人民 可能会分割成 “中国” 和 “人民”，q = “中国人民”，t= {“中国” ，“人民”}。

tf 表示 term frequency  词频，就是这个词汇在一篇文章中出现的次数。所以有个d参数。

idf ，是另外一个参数，它表述的是：inverse document frequency。逆向文件频率，这个参数说的是：一个词语普遍重要性的度量。比如“的” 这个词，几乎每篇文章都有，所以，不能代表什么实际的意义和信息，所以，要降低“的”这个词重要性。

下面一个重要的概念是：boost 的概念，不是每个字段的权重都是一样的，比如标题，匹配到了，要比正文匹配到了优先。实际上，它的作用是协调字段之间的权重的。原来的索引中，没有对标题进行优先处理，现在进行了优先的处理。

lengthNorm 也是一个比较重要的参数，这个也是表现为文档的长度问题。一般来说，一篇文章很长，你匹配到了一个关键字 和 一篇文章很短，你匹配到了关键字，要做点差别。

Coord 一般来说，如果 几个关键词都在一篇文章中匹配到了，应该给个更高的权重，如果10个关键词，才匹配到了一个，那么应该降低权重。排序算法其实一直是文本搜索里面的重点，其中有两类比较常用的算法：向量空间模型 和 统计模型，lucunece 使用的是向量空间模型。
向量空间模型可以说贯穿整个索引系统的始终，是索引系统的核心内容。其他的内容，如，存储问题可能会影响性能，但是不影响搜索的质量。

1.       基本的思想：

向量空间模型将文档和用户查询形式转化为向量形式,对于所有文档和用户查询都映射到文本向量空间. 用户查询和被检索文档两者的相似程度可用向量之间的夹角来度量,从而将信息检索转化为向量空间的向量匹配问题. 这种表示模型考虑到了文档的内容特征,而且文档之间的相似程度的度量比较简单,并且可以根据向量之间的相似程度对所有返回结果进行排。说道向量空间，就应该有它的基，也就是坐标系。这个向量空间的基就是 所有的关键字。而一篇文章就是里面的点。一个查询也是里面的一个点。那么如何很好的把一篇文字表示为关键字的一个向量集呢，关键是要计算，每个关键字的系数。有了文章的表示方法了以后，我们就知道如何评分了。

2.       计算文本向量：

关键字的数目可能会非常的多，所以整个系统是一个维数非常高的向量空间。当然，对于一篇文章来说，关键字最多几千个，不会很多，所以这个文章的向量大部分都是为0，一般为0的就省略了，否则无法表示，就计算有关键字的值。

最简单的方法，或许就是更具关键字出现的次数，可是，这有些不公平，应为文章的长度可能会不一样，这样对长的文章可能更加有利，于是，有人觉得用 tf 比较好，也技术词频。也就是 次数/总字数。但是，这样还是不对，因为，有些词汇 很常用，比如：我，你，它，的，是。基本每篇文章中都有，但是，他没有包含什么信息量。如果，这部分字的权重太大的话，就无法区分不同的文章之间的差别了。最后，我们或许终于想明白了，应该用某个词的信息量 * 词频 。 一个词的信息量这个问题貌似还是很难的一个问题。这个以前是一个世界级的难题，其实某个词的信息量的概念就是一个特定条件下、关键词的概率分布的交叉熵（Kullback-Leibler Divergence)。当然，这个计算公式提出很早，只是大家都无法解释。最后，用公式表示 就是 tf * idf , tf 就是词频，idf 就是词在文章中的信息量。但是，如果要比较相似度的话，必须要做归一化处理，这个在线性代数里面都学过。

Wij = tfij ×log(N / dfi )/sqrt(ΣTk∈D i[ tfij ×log(N / dfi ) ]2)

不必理解上面的公式，如果需要进一步了解可以查询论文库。

相似度的计算就比较简单了。就是计算量向量的 夹角。

3.       Lucunece 中的评分算法：

Lucunece 中的评分算法是向量空间模型的一种扩展

首先要从一个简单的例子说起：

A1 =（a1，b1，c1）；

A2 = （a2，b2，c2）；

A1 和 A2 是归一化的向量，那么 相关度 A1 * A2 = a1*a2 + b1*b2 + c1 * c2。从这个公式可以看出，实际上，如果一个查询字符串 和 一个文章相似度，只和查询字符串 和 文章中都存在的关键字相关。否则，两个里面一个为0的话，相乘还是为0，没有意义。在lucunce 里面没有保存 wij ，为了更加灵活的处理，而是保存了下面的值：

freq 就是 tf

docFreq  文档的数目

numDocs 有这个关键字的文档的数目

利用这些值就可以计算相关度了。

要注意，前面的公式的 idf  实际上是 idf * idf （query 中的idf 和 document中的idf 是一样的），而query 中的 tf 都默认为1（这样做就要通过搜索的关键字的数目来修正score）。

当然，其中还有好多个对算法的修正，从理论上解释这些问题以及为什么要修正的问题，可以参考更加进一步的资料。

 

公式为：

score_d = sum_t(tf_q * idf_t / norm_q * tf_d * idf_t / norm_dt_t)

score_d: Document(d) 的得分
sum_t: Term(t) 的总和
tf_q: 查询中 t 的频度的平方根
tf_q: d 中 t 的频度的平方根
idf_t: log(numDocs/docFreq_t + 1) + 1.0
numDocs: 索引中Document的数量
docFreq_t: 包含t的Document的数量
norm_q: sqrt(sum_t((tf_q*idf_t)^2))
norm_d_t: 在与 t 相同域的 d 中 tokens 数量的平方根

基础排序算法的不足

要点:
    查询词在一个 Document 中的位置并不重要。
    如果一个 Document 中含有该查询词的次数越多，该得分越高。
    一个命中document中，如果除了该查询词之外，其他的词越多，该得分越少。

不足：
    查询精确度不好。
    没有体现网页的重要性。
    Lucene的得分算法, 不适合网页搜索。
    google的pagerank算法主要是根据link

改进的算法：
    Score_d = k1 * OldScore + k2 * PrScore + k3 * ReScore + k4 * homePageScore

    Score_d: 记录d的得分。
    OldScore: 由基础排序算法计算出的记录d的得分。
    PrScore: 记录d的PageRank的得分。
    ReScore: 记录d的二次检索的加分, ReScore = rescore + (hitNum - 1) * increment
    homePageScore: 主页的加分
    K1, K2, K3, K4为权重系数

    PR(A) = (1 - d) + d(PR(1) / C(1) + ... + PR(n)/C(n))

    PageRank, 二次检索, 以及主页加分的调整确实优化了查询精确度

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/redez/archive/2005/11/17/531963.aspx

 

转载补充：

传统排序算法可以参看 BM25。Xapian中即使用BM25进行scoring。

其实BM25在相关文档信息未知(讲相关参数设置成0)时，即退化成类似于tf*idf的形式，跟本文的排序算法类似