淘先锋技术网

首页 1 2 3 4 5 6 7

什么是倒排索引

倒排索引(Inverted index),个人理解倒排的意思是说,普通的搜索算法,是从文档里搜索一个关键词(文档→关键词),而倒排索引是首先知道了每个关键词都出现在了哪些文档里,从关键词搜文档(关键词→文档),正好目的反过来,和“颠倒搜索”没什么关系。

倒排索引的好处

想象一个场景,你要对一个很大的文件搜索其中是否有一个关键词,常规的做法是遍历整个文档,那么如果关键词在文档最后,就会非常慢

倒排索引先记录了每个关键词出现在了哪些文档里,需要哪个关键词,把含有的文档直接拎出来就可以,这样就快多了

主流的搜索工具,ElasticSearch都是基于倒排索引的方式

如何建立一个倒排索引

举个栗子,假设我们有如下0-4五个文档

3402507047d28a44bede734f9c119a4b.png

分词后可以得到这16个关键词,倒排列表中记录的是那些文档包含这个关键词

c3b7456ce33959efde184fb4fa84e396.png

实际使用的一些问题

自己实现一个倒排,个人感觉需要注意一下模糊搜索的问题和匹配算法的设计,在使用ES时,虽然这些已经做好了,但是感觉有时效果不佳,具体实现机制还需要再研究。

模糊匹配

我们应该希望系统具有这样的能力

  • 匹配缩写:搜索 UK ,会返回包含 United Kindom 的文档
  • 匹配词根:搜索 jump ,会匹配 jumpedjumps
  • 匹配同义词:搜索 johnny walker 会匹配 Johnnie Walker , 搜索 people ,会返回包含 person 的文档
  • 理解语境:搜索fox news hunting 应该返回福克斯新闻( Foxs News )中关于狩猎的故事,而搜素so fox hunting news 应该返回关于猎狐的故事

要使得系统能够坐到这一点,就需要在分词阶段,对词条进行规范,真实场景下,很多时候并不能实现两个token之间的完美匹配,这时基于token的匹配就失去的作用

自己在使用ES的过程中,普通的匹配无法做到对单复数这种简单情况的处理,或许在建立索引是有一些操作,还需要继续研究

匹配算法设计

如何设计一个合理的匹配算法也是值得研究的问题,如何给搜索结果打分。

例如一个文档,我们用大写字母表示词条,大写字母组成的字符串表示一个文档,对于一个关键词CDEF,匹配算法应该能够对于这几种情况给出不同的分数

  1. 匹配到不同数量的词条的得分应该是不一样的
    比如有的匹配到CDF三个,有的只匹配到CD两个,通常是匹配更多数量的分数应该更高
  2. 匹配到相同数量的词条得分应该是不一样的
    比如都是匹配到三个词条,一个是CDE,一个是DEF,如果C是一个类似频繁项的词条,F是一个对文档比较重要的词条,那么后者的的风应该更高

匹配到相同的词条列表的得分应该是不一样的
比如都是匹配到CDE三个词条,有的是连续出现的(ABCDEFG),有的是分开出现(ABCGDFE)或者顺序不同(ABCEDFG),他们的得分应该是不同的。
另外从搜索的意图上看

  1. 如果搜索的关键词是一个专有名词
    一些专有名词本质上就是不可分割的(New York不能看成New和York)
    一些专有名词去掉其中一些token或改变顺序也并不影响词义(University of Pittsburgh和Pittsburgh university)。

2. 如果搜索仅仅是几个关键词的组合,比如平时使用搜索引擎的场景,那么每个token都是独立的可以以任意顺序在文档中出现。

参考资料

  1. https://www.zhihu.com/question/23202010