倒排索引

算法 3 分钟

世界上最伟大的互联网产品,说是搜索引擎,绝对没有别的产品可以替代,尤其是伟大的先在市场占用率最高的搜索引擎,Google Search.

还有很多差一大截的,比如 Bing, Yahoo 和 YANDEX.

什么是搜索引擎

所谓搜索引擎,就是根据用户需求与一定算法,运用特定策略从互联网检索出制定信息反馈给用户的一门检索技术。

搜索引擎技术的核心模块一般包括爬虫、索引、检索和排序等,同时可添加其他一系列辅助模块,以为用户创造更好的网络使用环境。

搜索引擎干了些什么

简单的说搜索引擎从网络上爬取网页,然后对网页信息进行提取,构建正排索引,然后分析网页内容,建立倒排文件.

接下来我将依次介绍 正排索引、 倒排索引 等知识点.

正排索引

正排索引通常是 id-document 的键值对

idnamecontexteng_context
1小明今天吃了3个包子today eating 3 baozi
2小仓最后一天看了一本书read a book last day
3仓颉去年造了个新华字典make a xinhua dictionary last year

倒排索引

倒排索引是关键词到id列表的映射关系.

倒排索引里面左边的列叫做 term , 里面存储的通常是一个关键词; 右边的列叫做 posting list,里面存储的是文档的id.

左侧的一列一起叫做 term dictionary.

首先上面有每个 document 有3个 field , 所以会创建3个倒排索引.

如果使用默认的英文分词器,那么表格会创建的索引大概是下面这个样子:

name index:

termposting list
[1, 2]
[2, 3]
[1]
[3]

context index:

termposting list
[1, 3]
[1, 2, 3]
[1]

eng_context index:

termposting list
last[2, 3]
a[2, 3]
dictionary[3]

读到这里想来你也会有些许疑问?

  • 比 MySQL Index 的优势在哪?
  • 当有1亿 Term 时如何高效查询?
  • 联合查询怎么办?
  • 相关度排序?

Term index

假象一下我们现在有 1 亿个 term, 那么这个 trem dictionary 会占多少内存呢? 假设每个 trem 占用内存 6 byte, 那么亿个大约占用 0.6 GB, 那么如果是一个非常复杂的文档, 岂不是内存不够用? 而且为什么搜索引擎的速度远远快于MySQL 的索引速度?

首先 Trem Index 实际上是一种字典树(前缀树), 可以将 term dictionary 里的内容组成树状结构. 下图会是一个普通的字典树.

而 Term Index 的 Value 就是 Term 在磁盘中的位置.

而且 Trem Index 通常会被缓存到内存中, 再加上优秀的树结构, 所以查询速度极快, 字典树的数据结构优势, 使体积远小于 term dictonary.

快于 MySQL 的主要原因是, 减少了访问磁盘的次数.MySQL 的B+树会在磁盘中多次读写不同位置, 而使用 term index , 则只会在匹配到 term 时进行一次磁盘访问.

联合查询

如何进行索引的联合查询, 当程序获得多个Posting list 那么程序需要从list 中进行多次交集并集操作.如何减少这些操作呢?

通常有两个解决方案.

  • bitset
  • 跳表

可以自己去看一下相关的工作原理。

END

想必看完之后,你也对倒排索引工作原理有一定的了解了吧。感谢阅读!