倒排索引:提升搜索引擎性能的核心技术

01 倒排索引简介

我们先来看比较简单的那个问题：给出一首诗的题目，马上背出内容。这其实就是一个典型的键值查询场景。针对这个场景，我们可以给每首诗一个唯一的编号作为 ID，然后使用哈希表将诗的 ID 作为键（Key），把诗的内容作为键对应的值（Value）。这样，我们就能在 O(1) 的时间代价内，完成对指定 key 的检索。这样一个以对象的唯一 ID 为 key 的哈希索引结构，叫作正排索引（Forward Index）。

一般来说，我们会遍历哈希表，遍历的时间代价是 O(n)。在遍历过程中，对于遇到的每一个元素也就是每一首诗，我们需要遍历这首诗中的每一个字符，才能判断是否包含“极”字和“客”字。假设每首诗的平均长度是 k，那遍历一首诗的时间代价就是 O(k)。从这个分析中我们可以发现，这个检索过程全部都是遍历，因此时间代价非常高。对此，有什么优化方法吗？

我们先来分析一下这两个场景。我们会发现，“根据题目查找内容”和“根据关键字查找题目”，这两个问题其实是完全相反的。既然完全相反，那我们能否“反着”建立一个哈希表来帮助我们查找呢？也就是说，如果我们以关键字作为 key 建立哈希表，是不是问题就解决了呢？接下来，我们就试着操作一下。

我们将每个关键字当作 key，将包含了这个关键字的诗的列表当作存储的内容。这样，我们就建立了一个哈希表，根据关键字来查询这个哈希表，在 O(1) 的时间内，我们就能得到包含该关键字的文档列表。这种根据具体内容或属性反过来索引文档标题的结构，我们就叫它倒排索引（Inverted Index）。在倒排索引中，key 的集合叫作字典（Dictionary），一个 key 后面对应的记录集合叫作记录列表（Posting List）。

02 倒排索引构建

1. 给每个文档编号，作为其唯一的标识，并且排好序，然后开始遍历文档。
2. 解析当前文档中的每个关键字，生成 < 关键字，文档 ID，关键字位置 > 这样的数据对。为什么要记录关键字位置这个信息呢？因为在许多检索场景中，都需要显示关键字前后的内容，比如，在组合查询时，我们要判断多个关键字之间是否足够近。所以我们需要记录位置信息，以方便提取相应关键字的位置。
3. 将关键字作为 key 插入哈希表。如果哈希表中已经有这个 key 了，我们就在对应的 posting list 后面追加节点，记录该文档 ID（关键字的位置信息如果需要，也可以一并记录在节点中）；如果哈希表中还没有这个 key，我们就直接插入该 key，并创建 posting list 和对应节点。
4. 重复第 2 步和第 3 步，处理完所有文档，完成倒排索引的创建。

更准确的展示，则是如下这种结果，包括了term index、term dictionary、posting list

term index 记录了词项的索引偏移量

term dictionary 记录了每个词项信息，若内存不够，则可存在磁盘

posting list 记录了文档id等信息

term index可以采用Trie树或FST的方式实现

03 Trie树及缺点

依次输入：msb、msn、msbtech、wltech会产生如上图数据结构

1、如果出现可以公用的元素，则另开分支将不可以公用的部分进行存储，最后一个节点标记为绿色

2、在查找时按照从头到尾的顺序进行查找，只有每个节点都符合并且最后一个字母为绿色final节点时代表查询成功

3、若没有可以公用的部分，则单独开分支进行存储，如wltech

问题：msbtech和wltech在前缀上没有可以公用的部分，但是tech可以公用，那么有什么方式将前缀和后缀都公用吗？可采用FST方式

04 FST

FST（Finite State Transducer），即“有限状态转换机”

通常我们在计算机的语言中标示一件事物，都会通过某种数学模型来描述。假如现在我们要描述一件事：张三一天的所有活动。这里我们采用了一种叫做FSM（Finite State Machine）的抽象模型，如图5-1所示，这种模型使用原型的节点标示某个“状态”，状态之间可以互相转换，但是转换过程是无向的。比如睡觉醒了可以去工作，工作累了可以去玩手机；或者工作中想去上厕所等等。在这个模型中，标示状态的节点是有限多个的，但状态的转换的情况是无限多的，同一时刻只能处于某一个状态，并且状态的转换是无序切循环的。

接着上图前缀树与红色字体问题，提出当输入wltech时，tech可以复用，得出FSA将tech直接复用减少存储空间

注意：当输入msn时，如果是前缀树，n节点会单独新增一个节点表示final节点。在使用FSA之后n节点直接指向最后的final节点

FST会在final节点中新增Final Output数值，当查找某一字符串的时候，会根据当前字符串的路径相加每个节点中的value得到最终值与初始value对应判断是否一致。

05 倒排索引的检索

如果只是查询包含A或者B这样单个字的文档，我们直接以查询的字作为 key 去倒排索引表中检索，得到的 posting list 就是结果了。

若要检索A且B的文档，则可以先分别用两个 key 去倒排索引中检索，这样会得到两个不同的 posting list。第一个posting list中的文档都包含了A字，第二个posting list中文档都包含了B字。那么，如果一个文档在两个posting list都存在，则找出了A且B的文档。

在实际应用中，我们可能还需要对多个 key 进行联合查询

参考资料
[1] https://www.cnblogs.com/lyc-code/p/15873576.html
[2] https://time.geekbang.org/column/article/219268?utm_source=related_read&utm_medium=article&utm_term=related_read&screen=full

[3] 极客时间、知乎、CSDN