设计一个简单的搜索引擎索引系统

题目

设计一个简单的搜索引擎索引系统

信息

• 类型：问答
• 难度：⭐

考点

倒排索引, 基本数据结构, 搜索匹配

快速回答

实现一个简单的搜索引擎索引系统需要：

• 使用倒排索引作为核心数据结构
• 通过add_document方法将文档ID和内容添加到索引
• 通过search方法查询包含关键词的文档ID
• 处理文本时进行分词和小写转换等基础预处理

1. 核心原理：倒排索引

倒排索引（Inverted Index）是搜索引擎的核心数据结构，它将文档中的单词映射到包含该单词的文档ID列表。与传统索引（文档→单词）相反，倒排索引的结构是：单词→文档ID列表。

示例数据结构：

inverted_index = {
    "apple": [1, 3, 5],
    "banana": [2, 3],
    "orange": [1, 4]
}

2. 代码实现示例

class SimpleSearchEngine:
    def __init__(self):
        self.inverted_index = {}

    def add_document(self, doc_id, content):
        """添加文档到索引"""
        # 1. 文本预处理：分词+小写化
        words = content.lower().split()

        # 2. 更新倒排索引
        for word in words:
            if word not in self.inverted_index:
                self.inverted_index[word] = set()
            self.inverted_index[word].add(doc_id)

    def search(self, keyword):
        """搜索包含关键词的文档"""
        # 1. 统一小写格式
        keyword = keyword.lower()

        # 2. 返回匹配的文档ID集合
        return list(self.inverted_index.get(keyword, set()))

# 使用示例
engine = SimpleSearchEngine()
engine.add_document(1, "Apple and banana")
engine.add_document(2, "Banana orange")
print(engine.search("banana"))  # 输出 [1, 2]

3. 最佳实践

• 文本预处理：统一小写确保大小写不敏感
• 使用集合(Set)：避免文档ID重复存储
• 简单分词：使用空格分词满足基础需求
• 内存存储：适合小型系统（实际系统需持久化存储）

4. 常见错误

• 未统一大小写：导致 "Apple" 和 "apple" 被识别为不同单词
• 忽略标点符号："apple." 和 "apple" 应视为相同单词
• 使用列表(List)而非集合(Set)：可能存储重复文档ID
• 缺少边界处理：搜索不存在的关键词时应返回空列表而非报错

5. 扩展知识

• TF-IDF：进阶排序算法（词频-逆文档频率）
• 布尔查询：支持 AND/OR 的多关键词查询（如 "apple AND banana"）
• 分布式索引：当数据量过大时，需使用分片技术（如Sharding）
• 中文分词：中文需使用分词库（如jieba）替代空格分词