Anh-Moffat 2005 — 让倒排表压到接近熵下限还能 SIMD 解码

是什么

Anh-Moffat 提出的 字对齐二进制编码（word-aligned binary codes，常被叫做 Simple-9 / Simple-16）是一类专门给倒排索引里那串”小整数”做压缩的方案。日常类比：你要把一摞高矮不齐的木棍塞进 32 厘米的盒子，不是一根一根塞，而是先看这一批木棍最长的那根多长，按那个长度切格子，一盒装一批。

倒排索引里要压的就是这种数字流：每个词后面挂着一串”出现在哪些文档”的 ID，相邻 ID 做差以后基本都是几到几十的小数。Simple-9 把 32 位整数当成一个盒子，用 4 位 写”这一盒里每个数占几位、装了几个”，剩下 28 位 装实际数据，总共有 9 种装法（所以叫 9）。

落地结果：压缩率接近变长编码（如 Elias gamma），但 解码速度快 4-5 倍——因为每次只读一个 32 位字，做一次位移和掩码就能拿出整个 batch。Lucene、Tantivy、Vespa 至今还在用它的变体。

为什么重要

不理解 Anh-Moffat，下面这些事都没法解释：

为什么 Lucene 倒排表比直接存 int 数组小 5-10 倍，但搜索还更快——磁盘 IO 省了，CPU 也没多花
为什么搜索引擎面试爱问”你怎么压一串递增整数”——答案永远绕不开 d-gap + Simple-X / PFOR
为什么 Tantivy（Rust 写的 Lucene）2016 年新写代码，还选了 2005 年的算法——SIMD 友好这件事 20 年没过时
为什么 Vespa 的 posting list 模块文档里直接写”Simple-9 variant”——这是工业默认选项

核心要点

Simple-9 把压缩问题反过来想：不追求每个数字最优，追求每个 32 位字最优。三步：

先做 d-gap：倒排表存的是文档 ID，相邻做差变成一串小整数。例：[7, 12, 18, 33] → [7, 5, 6, 15]。这一步不是 Simple-9 发明的，但它依赖这一步把数字压小。
贪心装盒：从当前位置往后看，问”如果我用 1 位/数装，能装几个？2 位/数能装几个？……” 选 9 种合法布局里装最多数据的那种。9 种布局是 (1×28 / 2×14 / 3×9 / 4×7 / 5×5 / 7×4 / 9×3 / 14×2 / 28×1)，前面是位宽，后面是个数。
解码全靠位移：读 32 位字 → 取前 4 位看是哪种布局 → 按布局表查一次”位宽 + 个数”→ 一次性把所有数解出来。没有分支预测、没有变长，直接 SIMD。

四个字概括：位宽随批选。

实践案例

案例 1：一个 32 位字到底装多少

假设 d-gap 后这串数都很小（< 8），用”3 位 × 9 个”布局：

[ 4 位选择器 = 0010 ][ 3 位 ][ 3 位 ]...[ 3 位 ]   共 4 + 3×9 = 31 位（浪费 1 位）

如果碰到一个比较大的数（< 16384），切换到”14 位 × 2 个”布局：

[ 4 位选择器 = 0111 ][ 14 位 ][ 14 位 ]   共 4 + 14×2 = 32 位（满）

关键：选择器只占 4 位，对解码非常友好——掩码 & 0xF 一步出来。

案例 2：和 VarInt 比，省了什么

Google Protobuf 的 VarInt：每字节最高位标”还有没有下一字节”，每解一个数要看 1-5 字节、做 1-5 次分支判断。

Simple-9：每解 batch 只看一次选择器，剩下纯位移。1000 个数字 Simple-9 大约 9 次循环 + 9 次掩码搞定，VarInt 要 1000-5000 次分支判断。CPU 流水线友好度差一个数量级。

案例 3：Lucene FOR / PFOR 里的影子

Lucene 现代版本用的是 PForDelta（Zukowski 2006）—— Simple-9 的演化版。差别是 PForDelta 一次处理 128 个数（而不是 28 位字），用一个主位宽装绝大多数，把少数”异常大”的值单独存。但思想完全继承 Anh-Moffat：批量选位宽、解码不分支。

案例 4：贪心装盒到底是怎么决策的

输入 d-gap 流：[3, 1, 2, 5, 1, 4, 2, 6, 3, 1, 8, 2, …]。装第一个 32 位字时：

看前 28 个数最大值 → 假设是 8 → 最少需要 4 位/数
查表：4 位/数 → 一个字装 7 个
再问”如果用 3 位/数能装更多吗？” → 3 位最大装 7，但 8 超了 → 不行
决定：4×7 布局，吃掉前 7 个数，输出 1 个字

下一个字从第 8 个数开始重新算。贪心 = 看眼前一批，最大化装载量，O(n) 时间，无回溯。

踩过的坑

没做 d-gap 就上 Simple-9 = 浪费：原始文档 ID 可能是 1 千万级，每数要 24 位，Simple-9 全跑 28×1 模式，没收益。先 d-gap 把数字压小再装盒是前置条件。
9 种布局不一定都常用：长尾分布下大多数批量在 1×28 / 2×14 / 3×9 之间切换，靠后那几种（14×2 / 28×1）很少用。选择器表静态写死比动态构建更快。
batch 边界对随机访问不友好：要查”第 1000 个文档 ID”，Simple-9 必须从头解到第 1000 个所在的那个字。Lucene 用跳表 + skip list补这个洞——每 128 个加一个跳点。
Simple-16 是修补不是革命：Anh-Moffat 后来出 Simple-16，把那 1 位浪费补上，多了几种布局。压缩率提升 3-5%，但实现复杂度涨一倍。默认上 Simple-9，极端场景再换。
64 位机器上不要原样移植：Simple-9 是为 32 位字设计的。在 64 位机器上想当然地放大成 60 位数据 + 4 位选择器，反而变慢——因为 SIMD 寄存器宽度和缓存行还是按 32/128 位对齐，64 位字在向量化时多走一道转换。要么坚持 32 位，要么重新设计 SIMD-BP128 这种方案。
熵下限不是真下限：论文里说”接近熵下限”是相对独立分布假设，实际倒排表里 d-gap 有强相关性（某个词热门则相邻文档间隔变短），用上下文模型能再压 20-30%，但解码慢 10 倍。Simple-9 的赢点不是压缩率，是压缩率/解码速度的乘积最优。

适用 vs 不适用场景

适用：

倒排索引的 docID / 词频列表（压完仍能 SIMD 顺序解码）
列式存储的”小整数列”（计数、ID、bitmap 索引）
任何”读多写少 + 顺序扫描为主”的整数序列
时序数据库的时间戳 d-gap 流（InfluxDB / VictoriaMetrics 都用过这条思路）

不适用：

数字很大且分布均匀（如 hash 值）→ d-gap 不缩小，Simple-9 退化成 28×1
需要随机访问任意位置 → batch 边界让随机访问变 O(n)，要配跳表
压缩率敢牺牲速度的场景 → Elias-Fano / Roaring bitmap 压得更狠
流式增量写入 → batch 边界让追加成本高，要么累够一批再压，要么用 LSM 思路分层

与同类算法的对比表

方案	压缩率	解码速度	复杂度	工业代表
Elias gamma	高	慢（变长 + 分支）	低	早期教科书
VarInt	中	中	低	Protobuf
Simple-9	中-高	快	中	Lucene 早期
PForDelta	高	快	中-高	Lucene 现役
SIMD-BP128	高	极快	高	FastPFor / Pisa
Elias-Fano	极高	中	高	学术 IR / 图压缩

怎么选：默认 PForDelta；极致吞吐选 SIMD-BP128；极致存储选 Elias-Fano。Simple-9 是入门理解整个家族最容易的那一档。

历史小故事（可跳过）

1989-1999 年：Moffat 等人在墨尔本大学持续做”信息检索的整数压缩”，Elias gamma / delta / Golomb 编码已经熟透。Witten-Moffat-Bell 的教材《Managing Gigabytes》成为这个领域的奠基书。
2003 年：Trotman 第一次正式比较各种编码，发现解码速度才是工业瓶颈，不是压缩率。这篇被引论文为 Anh-Moffat 提供了直接动机。
2005 年：Anh & Moffat 在 IRJ 发表本文，字对齐这一思路被工业界迅速接受。同年作者也在 SIGIR 发表姊妹篇讨论实验细节。
2006 年：Zukowski 把思路推广到 128 整数 batch，PForDelta 成为 MonetDB / Lucene 的默认。
2010 年代：Lemire 等人推出 SIMD-BP128 / FastPFor，把 Simple-9 思路完全 SIMD 化，吞吐再涨 3-5 倍。
2014 年至今：Tantivy / Vespa / Pisa（学术 IR 引擎）继续用这家族变体，没人换。Elasticsearch 默认编码本质上仍是这条线。

学到什么

批处理胜过个体最优：每数省 1 位 vs 每字省一次分支判断，工业上后者赢。
位宽随数据分布走：d-gap 让分布偏小，Simple-9 顺势压；分布变了换布局。
格式即接口：4 位选择器 + 28 位数据是个永远不会改的 ABI，Lucene 升级版本时新旧倒排表能共存。
20 年的算法仍在线：硬件变（SIMD 宽度从 128 到 512），但”对齐 + 不分支”这个原理穿越硬件代际。
压缩率不是唯一指标：Anh-Moffat 用”压缩率 × 解码速度”重新定义了 IR 整数编码的成本函数，从那以后这个领域几乎所有论文都跟进了这个评价方式。

关联

anserini-2017 —— Lucene 之上的 IR 基准，直接受益于这类编码
okapi-bm25-1994 —— 评分算法依赖倒排表能被快速扫
salton-vsm-1975 —— 向量空间模型，倒排表是它的物理实现
pagerank-1998 —— 大规模图算法对整数压缩的需求与 IR 同源

反向链接

amdahl-law-1967 —— Amdahl 定律 — 串行比例决定并行加速比的上界
anserini-2017 —— Anserini — 把工业搜索引擎 Lucene 改造成学术 IR 实验台
block-max-wand-2011 —— Block-Max WAND — 给倒排索引加分块上界，跳过算不过 top-k 的整块
bpr-2009 —— BPR — 用『i 比 j 更受欢迎』替代『i 是正例 j 是负例』
brill-moore-2000 —— Brill-Moore 2000 — 把拼写纠错的编辑操作从单字符扩成任意子串
gbrank-2007 —— GBRank — 把决策树堆起来学排序，一棵树纠正一处错排
pagerank-1998 —— PageRank — 用随机游走给整个网络的页面打分
ranknet-2005 —— RankNet — 让搜索引擎学会比较两个结果谁更好
rm3-2001 —— RM3 — 让搜索引擎自己看一眼结果再重搜一次
salton-vsm-1975 —— Salton VSM 1975 — 把文档变成向量再用余弦比相似度