搜索引擎技术之倒排索引原理详解，及案例分析 _搜索引擎

倒排索引是搜索引擎中最为核心的一项技术之一，可以说是搜索引擎的基石。可以说正是有了倒排索引技术，搜索引擎才能有效率的进行数据库查找、删除等操作。
1. 倒排索引的思想
倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index) 。
【搜索引擎技术之倒排索引原理详解，及案例分析】在搜索引擎中，查询词可以切分成若干个单词，所以对于搜索引擎中的倒排索引对应的属性就是单词，而对应的记录就是网页（也可以广泛地称为是文档）。所以，搜索引擎中的倒排索引是实现“单词-文档矩阵”的一种具体存储形式，通过倒排索引，可以根据单词（属性）快速获取包含这个单词的文档列表（记录）。倒排索引主要由两个部分组成：“单词词典”和“倒排文件” 。
2. “单词-文档矩阵”
单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型，图1展示了其含义。图1的每列代表一个文档，每行代表一个单词，打对勾的位置代表包含关系：

文章插图
图1 单词-文档矩阵
从纵向即文档这个维度来看，每列代表文档包含了哪些单词，比如文档1包含了词汇1和词汇4，而不包含其它单词。从横向即单词这个维度来看，每行代表了哪些文档包含了某个单词。比如对于词汇1来说，文档1和文档4中出现过单词1，而其它文档不包含词汇1 。矩阵中其它的行列也可作此种解读。
搜索引擎的索引其实就是实现“单词-文档矩阵”的具体数据结构。可以有不同的方式来实现上述概念模型，比如“倒排索引”、“签名文件”、“后缀树”等方式。但是各项实验数据表明，“倒排索引”是实现单词到文档映射关系的最佳实现方式。
3. 倒排索引的基本框架
单词和单词字典：搜索引擎的通常索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。
倒排列表：倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项(Posting) 。根据倒排列表，即可获知哪些文档包含某个单词。
倒排文件：所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件即被称之为倒排文件，倒排文件是存储倒排索引的物理文件。
搜索引擎中倒排索引大概流程框架：用户在搜索引擎搜索框输入查询词进行搜索时，搜索引擎会对查询词进行切词以及近义词匹配等操作，根据原始查询词得到一系列的单词列表。然后根据搜索引擎内部的字典来查询每个单词对应的倒排列表，从而定位到包含这个单词的网页或者说是文档。最后搜索引擎根据特定的网页排序算法将查询到的网页进行排序，通过前端将搜索结果展示给用户。下图2为倒排索引的主要流程：

文章插图
图2 倒排索引流程框架
4. 单词字典
其实，我们通过上述倒排索引的流程也可以看出来，倒排索引的关键技术在于建立单词字典。
单词词典用来维护文档集合中出现过的所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表，并以此作为后续排序的基础。
对于一个规模很大的文档集合来说，可能包含几十万甚至上百万的不同单词，能否快速定位某个单词，这直接影响搜索时的响应速度，所以需要高效的数据结构来对单词词典进行构建和查找，常用的数据结构包括哈希加链表结构（哈希存储的拉链法）和树形词典结构。
1）哈希拉链法
图3是这种词典结构的示意图。这种词典结构主要由两个部分构成：
主体部分是哈希表，每个哈希表项保存一个指针，指针指向冲突链表，在冲突链表里，相同哈希值的单词形成链表结构。之所以会有冲突链表，是因为两个不同单词获得相同的哈希值，如果是这样，在哈希方法里被称做是一次冲突，可以将相同哈希值的单词存储在链表里，以供后续查找。