1. 概念
纠正一个概念：倒排索引这个名字是典型的「渣翻译」，容易造成理解误区。我觉得叫反向索引更合适。不过网上大都叫倒排索引叫习惯了，所以下面我们也这么引用这个名称。
一个倒排索引由文档中所有不重复词的列表构成，对于其中每个词，有一个包含它的 Term 列表。
倒排索引的组成
倒排索引由两个部分组成：单词词典和倒排文件。
倒排文件
所有单词的倒排列表顺序的存储在磁盘的某个文件里，这个文件即被称为倒排文件，倒排文件是存储倒排索引的物理文件。
单词词典
单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。
单词词典是倒排索引中非常重要的组成部分，它是用来维护文档集合中所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表。
对于一个规模很大的文档集合来说，可能包含了几十万甚至上百万的不同单词，
快速定位某个单词直接决定搜索的响应速度，所以我们需要很高效的数据结构对单词词典进行构建和查找。
常用的数据结构包含哈希加链表和树形词典结构。
2. 倒排表举例
倒排索引（一个关键词对应许多doc）：
Term1: [Doc1, Pos1], [Doc2, Pos2], …
Term2: [Doc1, Pos1], [Doc2, Pos2], …
原文档（和上面正向索引的原文档一样）
| 文档编号（id） | 文档内容 |
|---|
| 1 | 我喜欢数学 | | 2 | 我喜欢编程 | | 3 | 我考试数学成绩很好 | | 4 | 编程太难了 |
a) 分词之后的简单的倒排索引?Map<token,list< id>>
| 编号 | 词元（token） | 倒排列表（list< id>） |
|---|
| 1 | 我 | 1,2,3 | | 2 | 喜欢 | 1,2 | | 3 | 数学 | 1,3 | | 4 | 编程 | 2,4 | | 5 | 考试 | 3 | | 6 | 成绩 | 3 | | 7 | 很好 | 3 | | 8 | 太难了 | 4 |
b) 有单词频率信息（TF）的倒排索引 Map<item,list< (id;TF)>>
在单词对应的倒排列表中不仅记录了文档编号，还记载了词元频率信息，即这个词元在某个文档中的出现次数。之所以要记录这个信息，是因为词频信息在搜索结果排序时，计算查询和文档相似度是很重要的一个计算因子，将其记录在倒排列表中，以方便后续排序时进行分值计算。
| 编号 | 词元（token） | 倒排列表（list< (id;TF)>） |
|---|
| 1 | 我 | (1;1),(2;1),(3;1) | | 2 | 喜欢 | (1;1),(2,1) | | 3 | 数学 | (1;1),(3;1) | | 4 | 编程 | (2;1),(4;1) | | 5 | 考试 | (3;1) | | 6 | 成绩 | (3;1) | | 7 | 很好 | (3;1) | | 8 | 太难了 | (4;1) |
c) 有词元频率和出现位置（pos）信息的倒排索引 Map<Term,list<(id;TF;< pos>)>>
| 编号 | 词元（token） | 倒排列表（list<(id;TF;< pos>)>） |
|---|
| 1 | 我 | (1;1;<1>),(2;1;<1>,(3;1;<1>) | | 2 | 喜欢 | (1;1;<2>),(2;1;<2>) | | 3 | 数学 | (1;1;<3>),(3;1;<3>) | | 4 | 编程 | (2;1;<3>),(4;1;<1>) | | 5 | 考试 | (3;1;<3>) | | 6 | 成绩 | (3;1;<4>) | | 7 | 很好 | (3;1;<5>) | | 8 | 太难了 | (4;1;<2>) |
3. 检索过程
由 Term 查询 id 的过程，是倒排索引。
倒排索引可以理解为 Map<Term, list< id>>，能够由查询词快速（时间复杂度 O(1)）找到包含这个查询词的文件的数据结构。
简单来讲：先分词，再找到每个 Term 对应的list< id>，最后进行集合求交集的过程。
分词和倒排查询时间复杂度都是 O(1)，整个搜索的时间复杂度取决于「求list< id>的交集」，因此实际上问题也变成了求两个集合的交集。
比如你搜索「喜欢」，搜索引擎可以快速检索出包含「喜欢」搜索词的位置，为后续的相关度和权重计算奠定基础，从而大大加快了返回搜索结果的速度。
|