Lucene – 评分公式

Lucene是盘冷饭,过去几年已经有海量的文章各种分析它的代码和机制。我之前用过很久,但一直没太深入。最近又正好接到了相关的项目,所以花了几天时间,将Lucene的内部机制梳理了一遍。

在我看来,Lucene的核心分成了3个部分:
1. Lucene的打分机制;这部分直接决定了搜索结果如何排序,比较偏理论和公式;
2. Lucene的索引文件格式;复杂的索引结构如何在硬盘上精细的实现;
3. Lucene的搜索过程;如何在索引文件的基础上实现搜索和打分排序的;

这篇blog主要谈第一点。

———————————-

Lucene的scoring采用的是VSM和Boolean Model的混合模型:

Lucene combines Boolean model (BM) of Information Retrieval with Vector Space Model (VSM) of Information Retrieval – documents “approved” by BM are scored by VSM.

按照VSM的定义,一个query q 和 一个document d之间的相似度计算可以采用Consine Simlarity,如下:

image

V(q) 和 V(d) 是 q 与 d 的向量表示,公式的分子是这两个向量的点积,而|V(q)| |V(d)|是它们欧式范数。

Lucene实际中采用的Similarity计算,没有完全采用上述公式,而是略作修改:

image

一个明显的区别是,原公式中的 |V(d)| 不见了。ref<1>中的解释是,|V(d)| 存在明显的问题,它将document的长度信息扔掉了。因此Lucene用 doc-len-norm(d) 替换掉了 |V(d)|,doc-len-norm 的好处是,它会将document的长度信息引入;
其它的,query-boostdoc-boost都是和boost有关的。所谓boost,其实就是人为的权重信息。在建立索引的时候,可以人为调节某个document或者某个field的权重,同样,在做查询的时候,也可以人为调整query的权重,这些因素对排序的影响被放到了 query-boost 和 doc-boost中;
coord-factor(q,d)表示 query 和 document 相匹配的程度,q 和 d 匹配的term越多,coord-factor的值越大;

另外一个有意思的问题是,因为|V(q)|这个值是和document无关的,所以它其实并不对query的查询结果排序产生任何的影响,是可以剔除的。但Lucene还是将这个factor保留了。原因是保留了|V(q)|的score除了用于query的查询结果排序以外,还可以考虑用到其它的地方。ref<1>关于这点有更详细的解释。

具体计算中,因为Lucene是采用TF-IDF来表示向量的权重,所以V(q) V(d) 向量表示为:

image

则两向量点积为:

image

因为tf(t, q) 的值为1(因为query中一个term只出现一次),所以上式中的 tf(t, q) 可以剔除。

|V(q)|的表示为(同样的,因为tf(t,q) = 1,所以可以剔除):

image

如果在计算|V(q)|的时候,将query-boost(q)考虑进去,就变成了:

image

最后,将doc-boost(d) 和 doc-len-norm(d) 放到一起考虑:

image

其中,如果document中有多个field的name都和term的name一样,那么这些field的boost需要相乘起来。lengthNorm就是之前的doc-len-norm。

将上述的公式合并起来,就得到了最终Lucene的评分公式:

lucene-similarity

— END. —

Advertisements
相册 | 此条目发表在Lucene分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s