用Golang写一个搜索引擎(0x05)—- 文本相关性排序

https://www.jianshu.com/p/a1426137780c

上面我们已经说过了一些倒排索引的东西,并且也知道了如何来实现一个倒排索引完成检索功能,那么检索完了以后如何排序呢,这一篇简单的说一下倒排索引的文本相关性排序,因为排序实在是太复杂了,我们这里就说说文本的相关性排序,而且是最简单的TD-IDF排序,之后有机会可以再说说整个搜索的排序算法有些什么。

文本相关性排序

首先明白几个概念:

  • Term,分词以后最小的单位,比如用Golang写一个搜索引擎,分词以后就是golang一个搜索引擎,那么每一个词就是一个Term。

  • TF(Term Frequency),Term在文章中出现的频率,就是当前term在文章中出现的频率,就是term次数/总term数,比如上文中的搜索引擎这个term的TF就是1/5,TF越高那么这篇文章中的这个词就越重要。

  • DF(Document Frequency),文档频率,就是某个Term在总文档中出现的频率,比如总共有100个文档,其中搜索引擎这个term在10个文档中出现了,那么他的IDF就是5/100=0.5。
  • IDF(Inverse Document Frequency),逆文档频率,听名字就知道是和上面的DF是反的,用总文档数除以包含term的文档数,再求对数即可,上面的搜索引擎的IDF是log(100/5)

如何在一堆文章中找到包含关键词的文章,倒排索引技术已经帮我们解决了,只要分词分得准确,那么找文章没什么问题了。问题是找到一堆文章以后怎么进行排序,让最重要的文章排在最前面,这里介绍一下相关性排序。

TF-IDF相关性排序

上面我们看到TF和IDF的概念,TF明显作用就是表示一个term在文章中的重要程度,TF越高那么这个词在文章中的重要程度越明显,IDF呢,IDF主要用来描述term在整体文章中的重要程度(也就是区分程度),IDF越高,那么这个term的整体重要性越高,也就是区分度越大,越能体现这个term的重要性。

为什么用log呢?其实我个人觉得啊,用不用log其实区别没那么大,TF-IDF只是一种计算文本相关度的思想,并不是一个有严格证明的公式,所以用不用log区别不大,不过从信息论的角度看的话,妖人香农提出的信息量的公式就是logX的样子,值越大信息量就越大,正好可以套在我们这,IDF越大,信息量也越大。

信息量是什么大家可以自己去百度,简单描述起来就是某一件事情发生的概率的,如果某件事情发生的概率是P,那么他的信息量就是 -logP,注意有个负号,比如中国队男子足球队和巴西队男子足球队打比赛,假设中国队赢的概率是 0.01(可能高估了),但如果巴西队赢了,根据公式算出来信息量几乎没有,因为谁都知道巴西会赢,但如果(我是说如果)最后中国队赢了,那么信息量算出来就是巨大的,肯定上各个头版了,这也和我们的直觉比较一致,在IDF中,就是用的这个公式,不过吧负号放里面去了,变成了log(1/P),而P就是DF,term在总文档中出现的频率。

TF和IDF合起来表示这个term的相关性,就是把这两个值乘起来。

为什么要把这两个概念合起来呢,第一个TF已经可以描述term的重要性了,为什么还要用IDF呢,主要可以解决两个问题。

  • 去掉高频词的噪音,既然IDF可以简单理解为term的信息量,那么它主要就是为了去掉噪声,也就是去掉那些个信息量很小的term的影响。比如这个词,它的TF非常高,但实际上没什么含义,但是你一算他的IDF,基本是0,所以如果用TF*IDF的话,结果还是0,可以比较有效的去掉这类通用词的干扰。
  • 同时IDF还可以更好的区分重要的词,如果一个term的IDF越高,证明带这个term的文章的更加能用这个term来表示,这个很好理解,如果一个term只在某一篇文章中出现,那么这个词更能代表这篇文章的内容。

最后,多个term联合检索的时候,他们的相关性就是每一个term的TF-IDF加起来,

OK,TF-IDF就是这些了,实现的时候,如果是最初做全量索引的话,由于整体文档数是已知的,那每个term的TF-IDF一般是建立索引的时候就把它算好了,检索的时候按这个一排序就行了,我实现的时候由于没有全量索引的概念,所以只是在每添加一个文档的时候算好这个文档的TF存起来,检索的时候通过term倒排召回的文档数来确定IDF的值,实时算出TF-IDF的,如果是非常巨大的文档数量,那么实时算还是很吃亏的,所以说全量索引还是非常必要的,只是我这没有完整实现全量索引建立而已,但后面接下来我会说说全量索引如何建立。

词距

除了TF-IDF来进行相关性排序以外,还有一些其他的文本因素也可以用在排序上,一是term的距离,也就是词距,如果检索关键词是小米手机,那么明显的,如果一篇文章中这两个term(小米,手机)挨在一起,比如小米手机是一款很热门的手机手机应用中有很多关于健康的文章,比如吃小米有什么好处这两篇文档,明显第一篇的相关度比第二篇要高。

所以,为了保持词距的信息,我们在存储倒排的时候还需要将每个term的位置信息保存下来,检索的时候用过这些个位置信息计算各个词直接的词距,从而和TF-IDF合在一起来表述文本相关性。

位置信息

同时,除了词距以外,还有一个因素也影响相关度的排序,那就是term的位置,这个也很好理解,如果在标题摘要命中的话明显应该比在正文中命中term的权重高,一般这种情况是把标题摘要命中的TD-IDF乘以一个系数来扩大影响,从而影响最后的相关度计算结果。

其他模型

除了直接使用TF-IDF以外,现在还有很多其他的文本相关性的排序模型,比如BM25这种以概率为基础的排序模型,这里就不展开了,如果大家有兴趣,写完这些篇以后可以专门写几篇怎么排序的,包括文本排序,以及文本之后的重要性排序啊,怎么离线利用机器学习计算文档重要性来排序之类的。

下面一篇文章会再讲讲倒排索引存储的一些我没有实现的东西,比如索引压缩之类的,然后会讲讲如何建立倒排,如果进行增量添加文档,如何进行索引合并。

ft_authoradmin  ft_create_time2019-05-24 13:04
 ft_update_time2019-05-24 13:04