倒排索引(Inverted Index)，主要是用于存储某个词在文档中位置的映射，是文档检索中很常见的一种结构。

举个例子

使用乱数假文举个例子，我们有几个文档

0 - lorem ipsum dolor sit amet, consectetur adipiscing elit. 
1 - Nulla sit amet est consequat, pretium risus ut, consectetur mi. 
2 - Curabitur dui enim, mattis non blandit at, consectetur in turpis. 
3 - Praesent sit amet metus nibh amet.

我们要寻找同时包含 amet 和 consectetur 这两词的文档，朴素的做法是根据关键词依次遍历所有文档来取得结果。

在句子的数量成指数级增长后，遍历的做法就不太可行了，复杂度太高。这个时候就需要找到一个可以提升检索速度的方法，那么就有一种看起来很暴力的做法了——打表。

打表也是有讲究的，如果以文档ID为键，文档里包含的字词列表为值，实际上就是朴素做法，因为实际上我们要检索的词的数目通常远小于文档数目，那么反过来对检索词建表，存储的是包含这个词的文档ID，这个做法就叫做倒排索引。

对于第一句假文，可以生成的索引部分如下

'Lorem': [0]
'ipsum': [0]
'sit': [0, 1, 3]
'amet': [1, 3]
'consectetur': [0, 1, 2]
...

假设检索条件同上，那么得出的结果就是 [0, 1, 2] and [1, 3] => [1]，可以很方便的通过倒排索引去取出包含这个搜索结果的文档。当然，在搜索系统里，仅检索到文档的ID是远远不够的，我们往往要在结果里插入额外信息辅助相关性排序。

辅助信息

如果我们使用常规的 TF-IDF + 权重的方式对结果进行排序，那么我们可以在倒排索引里存储的格式如下

Term: [[文档编号，出现次数(&Term Frequency), 文档长度, [起始位置, ...]], ...]

term 是一个搜索（信息检索）领域的概念，是分词后的基本表述单位，不一定是文档中出现的词语，但可以用于描述文档。上面这种格式的数据经过在线处理我们可以得到一些 TF-IDF 和计算辅助权重需要的参数

• TF(Term Frequency)，词频
• DF(Document Frequency) & IDF(Inverse Document Frequency)，文档频率和逆文档频率
• 词距

不过这些都属于相关性的部分，此处就按下不表，以后再谈。

所以在中文搜索引擎里构建倒排索引的 term，主要有如下几部分

分词

回到最开始的例子，举的例子是英文文档，而中英文NLP最大的差异之一就在于分词。英文拥有天然的空格作为分隔符，可以很方便的切分出单词，中文则不然，虽说有的中文文档存在可以作为参考的标点（像是逗号书名号等），但是子句往往是由一串连续的汉字构成且不存在分隔符，所以切分出符合需要的 term 也是要花费一番功夫，往往会通过新词发现、维护自定义词典和领域词典等方式来优化分词结果。此外，为了提高召回率，有时候也会结合多粒度分词（比如 IKAnalyzer）等方法进行优化。

停用词过滤

停用词(Stop Words)，即在处理文档的时候所不需要的字词，它们不能很好地用来区分文档。在中文语境下常见的助词（的/地/得/着/啊/吗…）、副词（很/十分/居然…）、介词（在/随/以…）和连词（那么/所以/但是…）等词性很多都属于停用词。

归一化

理想情况下用户输入的 query 经过分词后正好与文档的 term 能完全匹配上，但实际上用户的输入时很难预测的。归一化的目的就是将同义近义/拼写错误/拼音转写等表面不一致的多个 term 归一成一个等价的 term。

之后的步骤就是构建倒排记录表，这个和业务场景关系比较密切，本文也就不展开了。

本文属于历史文章，整理自笔者19年的私有云笔记。