倒排索引是一种在信息检索 (IR) 中使用的数据结构，用于有效地将术语（如单词或短语）映射到它们出现的文档。 与正向索引（列出每个文档中包含的术语）不同，倒排索引颠倒了这种关系。 它的作用类似于字典，其中每个条目都是一个术语，值是一个文档标识符 (ID) 列表，通常还包含术语位置或频率等其他详细信息。 例如，如果 ID 为 1 的文档包含单词“apple”和“banana”，而 ID 为 2 的另一个文档包含“apple”和“orange”，则倒排索引会将“apple”映射到 [1, 2]，“banana”映射到 [1]，“orange”映射到 [2]。 这种结构使搜索引擎能够快速定位包含特定术语的所有文档，而无需扫描集合中的每个文档。
为了构建倒排索引，首先通过诸如分词（将文本拆分为单词）、规范化（小写、删除标点符号）和词干提取（将单词简化为其词根形式，如“running”到“run”）等过程将文档解析为单个术语。 通常会排除停用词（如“the”或“and”等常用词）以节省空间。 然后将每个处理后的术语与其文档 ID 及其在文档中的位置一起记录。 当用户提交查询时，搜索引擎将其分解为术语，在倒排索引中查找它们，检索相应的文档列表，并将结果组合在一起。 例如，对“apple AND banana”的查询将相交“apple”([1, 2]) 和“banana”([1]) 的列表以返回文档 1。
倒排索引的主要优点是速度。 通过预先计算术语到文档的映射，它可以避免在搜索期间扫描每个文档，这对于像网页或文档数据库这样的大型数据集至关重要。 它还支持诸如 TF-IDF 或 BM25 之类的排名算法，这些算法使用术语频率和文档统计信息来评估相关性。 开发人员经常使用压缩（减少内存使用）或分布式存储（用于像 Elasticsearch 这样的系统中的可扩展性）来优化倒排索引。 虽然构建和维护倒排索引需要前期处理，但查询性能的显着提高证明了这种权衡是合理的，这使其成为现代搜索引擎、数据库和 IR 系统的基础组件。