倒排索引（Inverted Index）原理与实现

1. 什么是倒排索引？
倒排索引是一种用于快速检索的数据结构，常用于搜索引擎、数据库全文检索等场景。与正排索引（从文档ID到内容）相反，倒排索引将文档中的每个词项（term）映射到包含该词项的文档ID列表。例如：

• 文档1："算法与数据结构"
• 文档2："算法设计"
• 倒排索引：
  • "算法" → [文档1, 文档2]
  • "数据" → [文档1]
  • "结构" → [文档1]
  • "设计" → [文档2]

2. 倒排索引的核心组成
倒排索引包含两部分：

• 词项字典（Term Dictionary）：存储所有词项，通常用哈希表或有序结构（如B树）实现，支持快速查找。
• 倒排列表（Posting List）：每个词项对应一个列表，记录包含该词项的文档ID及其出现位置、频率等信息。

3. 构建倒排索引的步骤
假设有3个文档：

• Doc1: "数据结构的算法"
• Doc2: "算法与数据"
• Doc3: "数据结构设计"

步骤1：文本分词
对每个文档进行分词（中文需额外分词处理，英文按空格分割）：

• Doc1: ["数据", "结构", "的", "算法"]
• Doc2: ["算法", "与", "数据"]
• Doc3: ["数据", "结构", "设计"]

步骤2：构建词项-文档映射
遍历所有文档，记录每个词项出现的文档ID（忽略停用词如“的”“与”）：

• "数据" → [Doc1, Doc2, Doc3]
• "结构" → [Doc1, Doc3]
• "算法" → [Doc1, Doc2]
• "设计" → [Doc3]

步骤3：优化倒排列表

• 排序：文档ID按升序排列，便于后续合并操作（如多词检索）。
• 压缩存储：对文档ID列表使用差值编码（Delta Encoding），例如原列表[1,2,3]存储为[1,1,1]，减少存储空间。

4. 查询处理
单词查询：直接返回对应倒排列表。例如查询"算法"，返回[Doc1, Doc2]。
多词交集查询（如"数据" AND "结构"）：

1. 分别获取"数据"的列表[1,2,3]和"结构"的列表[1,3]。
2. 使用双指针法求交集：
   • 指针i指向列表1的文档1，指针j指向列表2的文档1，匹配成功，加入结果。
   • 移动指针至下一个文档，最终得到交集[1,3]。

5. 扩展优化

• 词项归一化：统一转为小写、处理同义词（如“算法”和“Algorithm”）。
• 排名支持：在倒排列表中存储词频（TF）或文档频率（DF），用于计算相关性得分（如TF-IDF）。
• 分布式索引：将索引分片（Sharding）存储在不同节点上，提高大规模数据下的并发检索能力。

6. 代码实现简例（Python）

class InvertedIndex:
    def __init__(self):
        self.index = {}
    
    def add_document(self, doc_id, words):
        for word in words:
            if word not in self.index:
                self.index[word] = []
            if doc_id not in self.index[word]:  # 去重
                self.index[word].append(doc_id)
    
    def search(self, word):
        return self.index.get(word, [])
    
    def search_and(self, words):
        if not words:
            return []
        result = self.search(words[0])
        for word in words[1:]:
            result = sorted(list(set(result) & set(self.search(word))))
        return result

# 测试
index = InvertedIndex()
index.add_document(1, ["数据", "结构", "算法"])
index.add_document(2, ["算法", "数据"])
index.add_document(3, ["数据", "结构", "设计"])
print(index.search_and(["数据", "结构"]))  # 输出 [1, 3]

7. 总结
倒排索引通过“词项→文档”的映射大幅提升检索效率，是搜索引擎的基石。实际应用中还需结合压缩算法、分布式架构和排名策略，以应对海量数据和高并发场景。