### 倒排索引

倒排索引是什么？

倒排索引是一种非常重要且应用广泛的数据结构，它是现代搜索引擎的核心技术之一

它的基本思想是：将文档中的每个词语与包含该词语的文档列表关联起来

你可以把它想象成一本书后面的索引。在这本书的索引里，你不会看到“第10页有...，第11页有...”，而是会看到“人工智能：第10页、第11页、第25页...”

倒排索引就是这样一种结构，它将词语（或术语）作为键（Key），将包含该词语的文档列表作为值（Value）。这种“词语到文档”的映射关系与传统的“文档到词语”的映射（即正向索引）正好相反，因此得名“倒排”

倒排索引的核心构成

一个典型的倒排索引通常包含两个部分：

1. 词典

- 作用：存储所有文档中出现过的所有不重复的词语
- 结构：通常是一个经过排序的列表或哈希表。它能让你快速定位到某个词语在倒排列表中的位置。

2. 倒排列表

- 作用：存储每个词语出现的文档ID列表，以及该词语在文档中的位置、频率等信息
- 结构：与词典中的每个词语相对应，包含以下信息：
  - 文档ID（Document ID）：包含该词语的文档的唯一标识符
  - 词频（Term Frequency）：该词语在特定文档中出现的次数
  - 位置（Position）：该词语在文档中出现的位置（如第几个词）。这对于处理短语查询（比如"人工智能"）非常重要

倒排索引的工作原理

让我们通过一个简单的例子来理解它的工作流程：

假设我们有三个文档：

- 文档1：`人工智能是未来。`
- 文档2：`学习人工智能。`
- 文档3：`未来是美好的。`

1. 分词（Tokenization）

首先，对每个文档进行分词，得到词语列表

- 文档1：`[“人工智能”, “是”, “未来”]`
- 文档2：`[“学习”, “人工智能”]`
- 文档3：`[“未来”, “是”, “美好”]`

2. 构建倒排索引

然后，我们构建倒排索引，将每个词语与包含它的文档关联起来

词语 | 倒排列表（文档ID，词频，位置）
--- | ---
人工智能 | [ (文档1, tf:1, pos:0), (文档2, tf:1, pos:1) ]
是 | [ (文档1, tf:1, pos:1), (文档3, tf:1, pos:1) ]
未来 | [ (文档1, tf:1, pos:2), (文档3, tf:1, pos:0) ]
学习 | [ (文档2, tf:1, pos:0) ]
美好 | [ (文档3, tf:1, pos:2) ]

3. 查询过程

现在，如果你搜索关键词“人工智能”，搜索引擎会怎么做呢？

1. 查询词典：它会直接在倒排词典中找到“人工智能”这个词
2. 获取倒排列表：获取与“人工智能”对应的倒排列表，即 `[ (文档1, ...), (文档2, ...) ]`
3. 返回结果：根据这个列表，搜索引擎可以立即知道文档1和文档2包含了“人工智能”这个词，并迅速将它们作为搜索结果返回

如果你搜索“人工智能 未来”，搜索引擎会：

1. 分别找到“人工智能”和“未来”的倒排列表
2. 对这两个列表进行求交集（Intersection），找到同时包含这两个词的文档ID
3. 最终得到结果是文档1