倒排索引

倒排索引将集合中的每个词项映射到包含该词项的文档列表，使搜索系统无需扫描每个文档即可找到匹配的文档。

Definition

倒排索引是一种数据结构，由一个索引词项字典组成，每个词项指向一个倒排列表，该列表枚举包含该词项的文档，通常附有频率和词项位置，以便通过交叉或合并倒排列表来执行检索。

Scope

本主题涵盖倒排索引的结构和构建：词项字典、记录文档标识符的倒排列表、词项频率和位置，以及构建和更新大型集合索引的算法，包括基于块排序的索引和单次内存索引。它涉及用于短语查询的位置信息和索引维护的工程，而将压缩和查询评估策略留给相关主题。

Core questions

• 字典条目及其倒排列表包含什么？
• 如何存储位置以支持短语和邻近查询？
• 当集合过大无法放入内存时，如何构建倒排索引？
• 当文档被添加、更改或删除时，索引如何更新？
• 倒排列表如何支持合取查询的高效交叉？

Key concepts

• 词项字典
• 倒排列表
• 文档标识符
• 位置索引
• 词项频率存储
• 基于块排序的索引 (BSBI)
• 单次内存索引 (SPIMI)
• 索引合并和更新

Key theories

字典和倒排列表组织

将紧凑的词项字典与可变长度的倒排列表分离，使系统能够快速查找词项，然后仅流式传输相关文档，这是所有倒排索引检索的结构基础。

可扩展索引构建

基于磁盘的方法，如基于块排序的索引和单次内存索引，通过累积和合并部分索引，为远大于内存的集合构建倒排文件。

Clinical relevance

倒排索引是几乎所有文本搜索系统的核心数据结构，包括网络搜索引擎、Lucene及其衍生产品等开源搜索平台以及数据库全文搜索。其设计决定了支持哪些查询类型以及它们可以多快、多经济地得到回答。

History

倒排文件用于早期的文献检索系统，并随着集合的增长成为全文搜索的标准结构。20世纪90年代和21世纪的研究，包括单次内存索引等可扩展构建方法，使得索引网络规模语料库成为可能，该结构现在是广泛使用的开源搜索库的基础。

Key figures

• Justin Zobel
• Alistair Moffat
• Steffen Heinz

Seminal works

• zobel2006
• heinz2003
• manning2008

Frequently asked questions

为什么它被称为“倒排”索引？

正常的（正向）索引列出每个文档包含的词项。倒排索引反转了这种映射，列出每个词项包含它的文档。这种反转正是使基于词项的查找快速的原因。

位置索引有什么用？

位置索引存储每个词项在每个文档中出现的位置。这使得系统能够回答短语查询和邻近查询，其中词项的顺序或接近度很重要，而不仅仅是词项是否出现在文档中的某个位置。