搜索引擎 · 单词词典和倒排列表

点击关注上方“ 知了小巷 ”，

设为“置顶或星标”，第一时间送达干货。

搜索引擎 · 单词词典和倒排列表

单词词典

单词词典是倒排索引中非常重要的组成部分，它用来维护文档集合中出现过的所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表，并以此作为后续排序的基础。对于一个规模很大的文档集合来说，可能包含几十万甚至上百万的不同单词，能否快速定位某个单词，这直接影响搜索时的响应速度，所以需要高效的数据结构来对单词词典进行构建和查找，常用的数据结构包括 哈希加链表结构 和 树形词典结构 。

哈希加链表

如下图所示，这种词典结构主要由两个部分构成，主体部分是哈希表，每个哈希表项保存一个指针，指针指向冲突链表，在冲突链表里，相同哈希值的单词形成链表结构。之所以会有冲突链表，是因为两个不同单词获得相同的哈希值，如果是这样，在哈希方法里被称做是一次冲突，可以将相同哈希值的单词存储在链表里，以供后续查找。

在构建索引的过程中，词典结构也会相应地被构建出来。比如在解析一个新文档的时候，对于某个在文档中出现的 单词T ，首先利用哈希函数获得其哈希值，之后根据哈希值对应的哈希表项读取其中保存的指针，就找到了对应的冲突链表。如果冲突链表里已经存在这个单词，说明单词在之前解析的文档里已经出现过。如果在冲突链表里没有发现这个单词，说明该单词是首次碰到，则将其加入冲突链表里。通过这种方式，当文档集合内所有文档解析完毕时，相应的词典结构也就建立起来了。

在响应用户查询请求时，其过程与建立词典类似，不同点在于即使词典里没出现过某个单词，也不会添加到词典内。在上图中，假设用户输入的查询请求为 单词3 ，对这个单词进行哈希，定位到哈希表内的 2号槽 ，从其保留的指针可以获得冲突链表，依次将 单词3 和冲突链表内的单词比较，发现 单词3 在冲突链表内，于是找到这个单词，之后可以读出这个单词对应的倒排列表来进行后续的工作，如果没有找到这个单词，说明文档集合内没有任何文档包含单词，则搜索结果为空。

树形结构

B树（或者B+树） 是另外一种高效查找结构，下图是一个 B树结构示意图 。 B树 与 哈希方式 查找不同，需要字典项能够按照大小排序（数字或者字符序），而哈希方式则无须数据满足此项要求。

B树 形成了 层级查找 结构，中间节点用于指出一定顺序范围的词典项目存储在哪个子树中，起到根据词典项比较大小进行导航的作用，最底层的叶子节点存储单词的地址信息，根据这个地址就可以提取出单词字符串。

倒排列表（Posting List）

倒排列表用来记录有哪些文档包含了某个单词。一般在文档集合里会有很多文档包含某个单词，每个文档会记录 文档编号（DocID） ， 单词在这个文档中出现的次数（TF） 及 单词在文档中哪些位置出现过等信息 ，这样与一个文档相关的信息被称做 倒排索引项（Posting） ，包含这个单词的一系列倒排索引项形成了列表结构，这就是某个单词对应的倒排列表。如下图所示，在文档集合中出现过的所有单词及其对应的倒排列表组成了倒排索引。

在实际的搜索引擎系统中，并不存储倒排索引项中的实际文档编号，而是代之以 文档编号差值（D-Gap） 。文档编号差值是倒排列表中相邻的两个倒排索引项文档编号的差值，一般在索引构建过程中，可以保证倒排列表中后面出现的文档编号大于之前出现的文档编号，所以 文档编号差值总是大于0的整数 。如上图所示的例子中，原始的3个文档编号分别是 187、196和199 ，通过编号差值计算，在实际存储的时候就转化成了：187、9、3【 类似首地址+偏移量 】。

之所以要对文档编号进行差值计算，主要原因是为了更好地对数据进行压缩，原始文档编号一般都是大数值，通过差值计算，就有效地将大数值转换为了小数值，而这有助于增加数据的压缩率。

- END -

• 搜索引擎索引基础

• 安全有效地输出价值：大数据是这个游戏的名字

• Apache Atlas元数据管理界面操作指南

• Hadoop YARN日志查看方式

• Impala使用md5函数对数据加密

• ClouderaManager6.3.1+CDH6.3.2+PHOENIX-5.0.0集成部署

• 大数据基础：Linux操作系统（下）

• 大数据基础：Linux操作系统（上）

• Apache Kafka客户端KafkaProducer