索引压缩

索引压缩以紧凑的方式编码倒排索引的倒排列表，从而使搜索系统存储更少的数据并更快地回答查询。

Definition

索引压缩是将整数和字符串编码方法应用于倒排索引的字典和倒排列表，以减少其存储占用空间，同时在查询处理期间保持倒排列表的快速可解码性。

Scope

本主题涵盖了压缩倒排索引的技术，特别是使用变长和字对齐整数编码对文档标识符间隙和词频进行编码。它涉及字典压缩、间隙（增量）编码、经典编码（如一元码、伽马码和Golomb-Rice码）、字节对齐和基于块的方案（如变长字节码和PForDelta），以及压缩比和解码速度之间的权衡。它不包括索引本身的构建以及消耗索引的查询评估策略。

Core questions

• 为什么文档标识符之间的间隙编码能有效压缩倒排列表？
• 使用了哪些整数编码，它们如何在压缩比和解码速度之间进行权衡？
• 词典本身是如何压缩的？
• 如何才能足够快地解码压缩的倒排列表以保持较低的查询延迟？
• 压缩如何与缓存行为和输入/输出成本相互作用？

Key concepts

• 间隙（增量）编码
• 变长字节编码
• 伽马码和Golomb-Rice码
• PForDelta和基于块的编码
• 字典压缩
• 压缩比
• 解码吞吐量
• SIMD / 向量化解码

Key theories

倒排列表的间隙编码

由于倒排列表中的文档标识符是递增的，存储连续标识符之间的差值（间隙）会产生较小的数字，这些数字可以很好地压缩，特别是对于具有密集倒排列表的频繁词项。

压缩-速度权衡

伽马码和Golomb码等位对齐编码能最大化压缩，但解码速度较慢；而变长字节码和PForDelta等字节对齐和基于块的编码则牺牲了一些压缩比，以换取更快的、可向量化的解码速度，这通常能带来整体查询性能的提升。

Clinical relevance

压缩对于大规模搜索操作至关重要：它能缩小索引使其适应内存或更小的存储空间，减少输入/输出并改善缓存局部性，从而降低查询延迟和硬件成本。生产搜索引擎和开源搜索库都依赖于压缩的倒排列表。

History

文本索引的紧凑编码与倒排文件一同发展，经典的位对齐编码（一元码、伽马码、Golomb码）在20世纪90年代的《管理千兆字节》工作中得到了系统化。随着网络规模搜索对更快解码速度的需求，变长字节码和PForDelta等字节对齐和基于块的方案，以及后来能够每秒处理数十亿整数的向量化解码器，将重点转向了速度。

Key figures

• Alistair Moffat
• Ian H. Witten
• Daniel Lemire
• Justin Zobel

Seminal works

• wittenmgb1999
• lemire2015
• manning2008

Frequently asked questions

为什么压缩索引比未压缩索引更快？

压缩减少了从磁盘或内存读取的数据量，这通常是瓶颈所在。现代整数编码解码速度非常快，经常使用向量指令，因此在输入/输出上节省的时间和更好的缓存行为足以弥补解码工作。

为什么存储间隙而不是原始文档标识符？

倒排列表中的文档标识符是排序且递增的，因此连续标识符之间的差异很小。存储这些小间隙而不是大的绝对标识符会产生紧凑编码可以用非常少的位表示的值。