前言
当我们使用搜索引擎时，它总是会把相关性高的内容显示在前面，相关性低的内容显示在后面。那么，搜索引擎是如何计算关键字和内容的相关性呢？这里介绍2种重要的相似度算法：TF-IDF和BM25。
TF-IDF是Lucene上一代（6.0以前）相似度算法，BM25是Lucene新一代（6.0以后）正使用的相似度算法。
先举个例子。假如，我们想找和“Lucene”相关的文章。可以想一下，那些内容里只出现过一次“Lucene”的文章，有可能是在讲某种技术，顺便提到了Lucene这个工具。而那些出现了两三次“Lucene”的文章，很可能是专门讨论Lucene的。通过直觉，我们可以得出判断：关键字出现的次数越多，文档与关键字的匹配度越高。
TF
Term Frequency，缩写为TF。通常叫做“词频”，表示文档中关键字出现的次数。
通常TF越大，相关性越高。
但是，你可能会发现一个问题。例如一篇小短文里出现了一次“Lucene”，而一部好几百页的书里提到两次“Lucene”，此时我们就不能说后者相关度更高了。为了消除文档本身大小的影响，在计算TF时引入文档长度这个参数，做文档长度标准化
TF socre ＝ 某个词在文档中出现的次数 ／ 文档的长度
举例：某文档D，长度为200，其中“Lucene”出现了2次，“的”出现了20次，“原理”出现了3次，那么
TF(Lucene|D) = 2/200 = 0.01
TF(的|D) = 20/200 = 0.1
TF(原理|D) = 3/200 = 0.015
其中我们发现“的”这个词的比重非常高，搜索引擎中一般把这种“的、地、得”这些虚词去掉，不计算其分数。
IDF
Inverse Dcument Frequency, 缩写为IDF。通常叫做“逆文档频率”，其定义为
IDF = log(语料库的文档总数 / 包含该词的文档数 + 1)
可见包含该词的文档数越小，分母就越小，IDF越大；该词越常见，分母就越大，IDF越小越接近0。分母之所以要加1，是为了避免分母为0（即所有文档都不包含该词）。
举例：世界上文档总数位100亿，"Lucene"在1万个文档中出现过，“原理”在2亿个文档中出现过，那么它们的IDF值分别为：
IDF(Lucene) = log(100亿/1万+1) = 19.93
IDF(原理) ＝ log(100亿/2亿+1) ＝ 5.64
“Lucene”重要性相当于“原理”的3.5倍，可见“Lucene”更能表征这篇文档。
TF-IDF
TF-IDF算法的相似度公式就是TF和IDF的加权求和
simlarity = TF1*IDF1 + TF2*IDF2 + ... + TFn*IDFn
上面的例子最终相似度得分为
simlarity(Lucene的原理|D) = 0.01*19.93 + 0 + 5.64*0.015 ＝ 0.2839
其中，“Lucene”占了总分70%的权重，“原理”仅占总分30%的权重。
Lucene中的TF-IDF
Lucene对TF-IDF算法做了适当调整，它的相似度公式为
simlarity = log(numDocs / (docFreq + 1)) * sqrt(tf) * (1/sqrt(length))
各参数含义
- numDocs： 索引的文档总数量
- docFreq： 包含关键字的文档数量
- tf：关键字在一篇文档中出现的次数。
- length：文档的长度
上面的公式在Lucene打分计算时会被拆分成三个部分：
IDF Score = log(numDocs / (docFreq + 1))
TF Score = sqrt(tf)
fieldNorms = 1/sqrt(length)
log()，sqrt()主要是为了降低分值大小，缩写文档之间分数差距
fieldNorms是对文本长度的归一化(Normalization)，为了消除文档长度对分数的影响
所以，上面公式也可以表示成
simlarity = IDF score * TF score * fieldNorms
Lucene在score打分时会遍历匹配到的每篇文档计算每篇文档的score，每篇文档分别计算这三部分分值。最后默认根据score sort。
BM25,下一代的TF-IDF
新版的Lucene不再把TF-IDF作为默认的相关性算法，而是采用了BM25(BM是Best Matching的意思)。BM25是基于TF-IDF并做了改进的算法。先来看下改进之后的BM25算法
simlarity = log(1 + (numDocs - docFreq + 0.5) / (docFreq + 0.5)) * ((k1 + 1) * tf) / (K + tf)
上面的公式在Lucene打分计算时会被拆分成两部分：
IDF Score = log(1 + (numDocs - docFreq + 0.5) / (docFreq + 0.5))
TF Score = ((k1 + 1) * tf) / (K + tf)
这里k1和K下面展开讨论
-
TF项比较
两者公式如下
传统 TF Score = sqrt(tf)
BM25的 TF Score = ((k1 + 1) * tf) / (K + tf)
传统的TF值理论上是可以无限大的。而BM25与之不同，它在TF计算方法中增加了一个常量k1和K，用来限制TF值的增长极限，BM25的 TF Score的范围会控制在[0, k1+1]。其中K
K = k1(1 - b + b*dl/avgdl)
取值k1，b是调节因子，Lucene中默认是k1=2，b=0.75，用户可以自定义。dl为文档的长度，avgdl为所有文档的平均长度。
两者的分布曲线来看，随着tf增大，BM25的TF会接近k1+1，传统的TF会无限变大。
TF中还引入了文档的长度dl，所有文档的平均长度avgdl，这里假设L = dl/avgdl，下面是不同L的条件下，词频对TFScore影响的走势图
从图上可以看到，文档越短，它逼近上限的速度越快，反之则越慢。这是可以理解的，对于只有几个词的内容，比如文章“标题”，只需要匹配很少的几个词，就可以确定相关性。而对于大篇幅的内容，比如一本书的内容，需要匹配很多词才能知道它的重点是讲什么。
关于参数b的作用：公式中L前面有个常系数b，如果把b设置为0，则L完全失去对评分的影响力。b的值越大，L对总评分的影响力越大。
- IDF项比较
两者公式如下
传统的 IDF Score = log(numDocs / (docFreq + 1))
BM25的 IDF Score = log(1 + (numDocs - docFreq + 0.5) / (docFreq + 0.5))
从分布曲线来看两者走势基本一致。
TF-IDF vs BM25
传统的TF-IDF是自然语言搜索的一个基础理论，它符合信息论中的熵的计算原理，你观察IDF公式会发现，它与熵的公式是类似的。实际上IDF就是一个特定条件下关键词概率分布的交叉熵。
BM25在传统TF-IDF的基础上增加了几个可调节的参数，使得它在应用上更佳灵活和强大，具有较高的实用性。
