Chapter 3 Inverted Index

约 618 个字 预计阅读时间 2 分钟

预处理

1. 词干分析（Word Stemming）：将文档中具有同一词干的单词归为一类，如 running、run、runner 等归为 run
2. 停用词（Stop Words）：如 the、and、of 等高频词汇在查询时几乎没有约束力，可以不做索引，减少索引大小并加快查询时间

在查询时，我们通常会把 Query 中所有的词（除了停用词）转换为词干，然后通过倒排索引查找包含这些词的文档集合，最后取交集作为最终的结果. 取交集时通常从最小的集合开始处理，以减少计算量.

索引存储

1. 搜索树：B- trees, B+ trees 等
2. 哈希表

存储容量问题的解决方案

1. 分布式索引存储（Distributed Indexing）

   • 根据单词的字典序分配存储位置（Term-partitioned Index）：索引效率较高
   • 根据文档顺序分配存储位置（Document-partitioned Index）：容灾能力较强，不易造成单点故障

2. 压缩（Compression）

3. Thresholding（阈值化）

动态请求的处理

文档会随时间增加/减少，索引必须随之更新.

我们使用动态索引技术（Dynamic Indexing）：

• 主索引分区中存储之前已经创建索引过的文档
• 当有新文档加入时，将其索引添加到辅助索引分区（Auxiliary Index）
• 查询时从主索引分区与辅助索引分区中同时检索，并将结果合并
• 定期合并辅助索引分区到主索引分区

性能评估

1. 数据检索的性能表现

   1. 索引消耗的时间
   2. 查询的响应时间
   3. 查询语言的表达能力（支持复杂的查询请求）

2. 检索到的信息相关度

相关度评估

相关度评估需要：

1. 测试文档集合
2. 测试查询
3. 相关度表：存储每个文档与每个查询之间的相关性（相关或不相关）

相关度评估指标：

1. 准确率（Precision）：检索出的相关文档占所有检索出的文档的比例
2. 召回率（Recall）：检索出的相关文档占全部相关文档的比例

若 Precision 较高，Recall 较低，说明检索出的文档基本是与查询相关的文档，但还有很多相关文档被漏掉；

若 Recall 较高，Precision 较低，说明与查询相关的文档基本都出现在搜索结果中，但是搜索结果中也会有很多不相关的文档.