倒排索引
倒排索引是什么？
倒排索引是一种非常重要且应用广泛的数据结构，它是现代搜索引擎的核心技术之一
它的基本思想是：将文档中的每个词语与包含该词语的文档列表关联起来
你可以把它想象成一本书后面的索引。在这本书的索引里，你不会看到“第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包含了“人工智能”这个词，并迅速将它们作为搜索结果返回
如果你搜索“人工智能 未来”，搜索引擎会：
- 分别找到“人工智能”和“未来”的倒排列表
- 对这两个列表进行求交集（Intersection），找到同时包含这两个词的文档ID
- 最终得到结果是文档1