- +在此添加单个AI新笔记
索引 - 倒排索引 - 按词项快速定位文档集合
倒排索引（Inverted Index）简介
倒排索引是信息检索领域最核心的数据结构之一，用于快速定位包含特定词项的文档集合。与传统的“文档→词项”的正排索引不同，倒排索引是“词项→文档”的逆向映射，因此称为“倒排”。
核心思想
- 逆向映射：为每个词项维护一个列表，记录所有包含该词项的文档ID。
- 快速查询：通过词项直接找到相关文档，无需逐一遍历所有文档。
倒排索引的构建与示例
示例数据集
假设有3个文档：
- 文档1: “苹果手机”
- 文档2: “苹果电脑”
- 文档3: “香蕉手机”
分词后的词项
对每个文档分词得到词项（假设按分词结果为单个词语）：
- 文档1 → [“苹果”, “手机”]
- 文档2 → [“苹果”, “电脑”]
- 文档3 → [“香蕉”, “手机”]
构建倒排索引
通过词项映射到文档集合，结果如下：
- 苹果 → [文档1, 文档2]
- 手机 → [文档1, 文档3]
- 电脑 → [文档2]
- 香蕉 → [文档3]
可视化表格
| 词项 | 文档ID列表 |
|---|---|
| 苹果 | [1, 2] |
| 手机 | [1, 3] |
| 电脑 | [2] |
| 香蕉 | [3] |
如何工作？
查询场景：
- 用户搜索“苹果” → 系统直接返回文档1和文档2。
- 用户搜索“手机” → 返回文档1和文档3。
- 组合查询（如“苹果 AND 手机”） → 取交集得到文档1。
优化性能：
- 词项归一化：忽略大小写、复数形式（如”apple”和”Apple”统一为”apple”）。
- 压缩存储：对文档ID列表进行差值编码（如[100, 101, 103]存储为100,1,2）。
实际应用场景
- 搜索引擎（如Google、百度）: 用户输入关键词，快速返回网页。
- 数据库全文检索（如Elasticsearch）: 支持对文本字段的高效模糊搜索。
- 推荐系统：根据用户搜索词快速筛选关联内容。
总结
倒排索引通过“词项→文档”的映射，将时间复杂度从O(N)（遍历所有文档）降低到O(1)（直接取词项对应列表），是大规模文本检索的基石。其核心价值在于快速定位数据，满足实时查询需求。