索引压缩原理

[Yhzhtk]

索引构建总结

1. 基于排序的索引构建算法

• 它是一种最原始的在内存中进行倒排的方法
• 基于块的排序索引算法
• 合并排序操作对于基于磁盘的排序来说很高效(避免寻道)

2. 内存式单遍扫描索引构建算法

• 没有全局的词典
• 对每个块都生成单独的词典
• 不对倒排记录进行排序
• 有新的倒排记录出现时，直接在倒排记录表中增加一项

3. 采用MapReduce的分布式索引构建算法

4. 动态索引构建算法：多个索引，对数合并

索引压缩

几个定律

• Zipf定律
• Heaps定律

词典压缩

• 将词典看成单一字符串的压缩方法 • 按块存储/前端编码 • 倒排记录表压缩 • 可变长字节码 • 一元编码/ γ 编码

索引压缩

• 统计信息(对RCV1语料库) • 词典和倒排记录表将会有多大？ • Heaps定律：词项数目的估计 • Zipf定律：对词项的分布建模 • 词典压缩 • 将词典看成单一字符串的压缩方法 • 按块存储/前端编码 • 倒排记录表压缩 • 可变长字节码 • 一元编码/ γ 编码

推荐 PPT 信息检索与数据挖掘 - 索引压缩