倒排索引是一种数据结构，用于有效地将术语（如单词或数字）映射到它们出现的文档或记录。与正向索引（列出每个文档中包含的术语）不同，倒排索引颠倒了这种关系：它从术语开始，指向包含它们的文档。这种结构是搜索引擎和数据库的基础，可以快速查找诸如“查找包含单词 'apple' 的所有文档”之类的查询。 倒排索引的核心包含两个主要组成部分：唯一术语的字典和倒排列表，倒排列表将每个术语链接到它出现的文档（通常还有这些文档中的位置）。
要构建倒排索引，首先通过分词将文档解析为单个术语（将文本拆分为单词、符号或短语）。 例如，句子“Hello, world!” 可能会变成 ["hello", “world”]。 然后对这些术语进行规范化（例如，转换为小写或词干提取），以确保一致性。 通常会删除“the”或“and”之类的停用词，以节省空间。 然后将每个术语映射到包含文档 ID 且可以选择包含位置数据的倒排列表。 例如，如果术语“apple”出现在文档 ID 1 和 3 中，则“apple”的倒排列表将存储 [1, 3]。 位置数据可能会跟踪 “apple” 在文档 1 中字符偏移量为 10 和 25。 此过程允许索引快速回答诸如“哪些文档包含 'apple’？”或“'apple’ 出现在文档 1 的什么位置？”之类的问题。
当用户提交搜索查询时，倒排索引会检索查询中每个术语的倒排列表。 对于诸如“apple”之类的单项查询，系统会返回与该术语关联的文档列表。 对于诸如“apple pie”之类的多项查询，索引会交叉 “apple” 和 “pie” 的倒排列表，以查找包含这两个术语的文档。 位置数据可以通过验证术语是否按顺序出现（例如，“apple pie”作为一个短语）来进一步优化结果。 然后，TF-IDF 或 BM25 等排名算法会根据术语频率或文档相关性等因素对结果进行评分。 例如，文档中“apple”出现五次可能比出现一次的文档排名更高。 压缩（例如，文档 ID 的增量编码）和分布式存储（跨服务器分片）等优化措施可确保索引能够高效地扩展以处理大型数据集。 Elasticsearch 和 Apache Lucene 等工具依赖于倒排索引，以在从电子商务到日志分析的各种应用程序中提供快速、灵活的搜索功能。
