第11章 Integer Coding：整数编码

从 d-gap 和自定界要求出发，比较 Elias、Rice、PForDelta、Variable-byte、Interpolative 与 Elias-Fano 的长度、分布假设和随机访问能力。

学习目标

能解释“11 Integer Coding”如何按整数分布、单调性与查询需求选择自定界和块级编码
能逐项核对Elias Codes: γ and δ、Rice Code、PForDelta Code、Variable-Byte Code and (s, c)-Dense Codes、Interpolative Code、Elias–Fano Code，不把平台页数或相邻章节主题冒充原版目录
能固定输入和参数，按“Elias-Fano ≤ n ceil(log2(U/n)) + 2n bits”手算一个最小样例，并找到输出或成本的首个分叉
能注入“把只支持正整数的码直接用于零或在差分时溢出，破坏码流边界”，保存基线、故障、恢复和同输入重放证据

来源、版次与独立重写边界

“11 Integer Coding”对应 Paolo Ferragina 的 Pearls of Algorithm Engineering（Cambridge University Press，2023）。出版社书籍页确认作者、版次、ISBN、318页与算法工程定位；官方目录页和官方前置信息 PDF共同给出16章、61个编号节与索引的正式顺序。

对“11 Integer Coding”而言，当前公开可核验材料是出版社目录、前言与书籍说明，并非获授权完整正文。因此，下方中文讲解、公式推导、代码和实验是按公开目录坐标进行的独立教学重写，不声称逐段翻译原书；涉及“按整数分布、单调性与查询需求选择自定界和块级编码”的结论必须由本页的最小输入、预言机与成本记录重新证明。

官方目录坐标：11 Integer Coding

11.1 Elias Codes: γ and δ：在本页正文中以“按整数分布、单调性与查询需求选择自定界和块级编码”的对象、状态、复杂度或工程边界核对。
11.2 Rice Code：在本页正文中以“按整数分布、单调性与查询需求选择自定界和块级编码”的对象、状态、复杂度或工程边界核对。
11.3 PForDelta Code：在本页正文中以“按整数分布、单调性与查询需求选择自定界和块级编码”的对象、状态、复杂度或工程边界核对。
11.4 Variable-Byte Code and (s, c)-Dense Codes：在本页正文中以“按整数分布、单调性与查询需求选择自定界和块级编码”的对象、状态、复杂度或工程边界核对。
11.5 Interpolative Code：在本页正文中以“按整数分布、单调性与查询需求选择自定界和块级编码”的对象、状态、复杂度或工程边界核对。
11.6 Elias–Fano Code：在本页正文中以“按整数分布、单调性与查询需求选择自定界和块级编码”的对象、状态、复杂度或工程边界核对。

从“直接拼二进制”为何不可解码开始

integer coding输入正整数序列 S。若要支持有符号数，可把非负 x 映射到2x、负 x 映射到 -2x-1，再编码所得非负整数。

只把每个 x 写成最短二进制并拼接不是自定界码。例如1、2、3产生1|10|11，去掉分隔后 11011 还可解释成6、1、1等序列。编码器必须让解码器仅凭 bitstream 确定每个 codeword 在哪里结束。

先预测搜索引擎 posting list 3、10、11、25、29、60 应直接编码还是先变形。有序 ID 的绝对值越来越大，邻差却是3、7、1、14、4、31；小 d-gap 更频繁，变长码才容易用短 codeword。

第一项显式存储，后续保存相邻差；解码以 prefix sum 恢复。这个表示层变换常比更换 bit code 更重要。LZ77 距离/长度、RLE run、图邻接表和 token ID 也会把问题归约为正整数序列。

固定宽度用 1+floor(log2 m) 位表示最大值 m，在近均匀且范围紧凑时合适；若 m 远大于大多数值，它会浪费高位。Unary code U(x) 写 x-1 个0再写1，长度 x，适合极偏向小值的几何分布，却对大 x 迅速膨胀且逐 bit 解码慢。

Elias 编码：先描述二进制长度

Elias codes对任意 x 都只需 O(log x) 位，不依赖预先统计分布。

gamma(x) 先写 |B(x)|-1 个0，再写完整 B(x)。首个1既结束一元长度前缀，也是二进制最高位。长度为：

|\gamma(x)| = 2\lfloor\log_2 x\rfloor+1

delta(x) 不再用一元码直接描述 |B(x)|，而用 gamma 编码长度，再接 B(x) 去掉最高1后的尾部：

|\delta(x)| = \lfloor\log_2 x\rfloor +2\left\lfloor\log_2(\lfloor\log_2x\rfloor+1)\right\rfloor +1

gamma 至多比最短二进制多约一倍，适合小数；delta 约 log x + 2 log log x + 1，大数的相对冗余趋近0。二者 prefix-free、无需码表，但要数前导零、位移和跨字读取，速度常不如字节/字宽对齐方案。

DecodeGamma(bits):
  c = count zeros until first 1
  read c following bits
  return binary value of 1 followed by those c bits

Rice 编码：用参数 k 对齐数值尺度

Rice code定义：

q=\left\lfloor\frac{x-1}{2^k}\right\rfloor, \qquad r=(x-1)\bmod 2^k

q 用 q 个0加终止1编码，r 用恰好 k 位编码，所以：

|R_k(x)| = \left\lfloor\frac{x-1}{2^k}\right\rfloor+1+k

2^k 太小会让 quotient 一元串很长；太大则每个 remainder 浪费位。几何分布参数为 p 时，2^k 约取 ln2/p；用样本均值估计时约为0.69倍 mean(S)。Rice 是 Golomb code 的 2 的幂特例，除法和余数可直接用移位与掩码。

RiceEncode(x, k):
  q = (x - 1) >> k
  r = (x - 1) & ((1 << k) - 1)
  emit q zero bits and one stop bit
  emit r in exactly k bits

分块自适应时，每块 k 必须写入 header，并限制估计噪声；对一个异常大数，Rice 会生成极长 quotient，应设置 fallback 或选后面的 exception code。

PForDelta：大多数定宽，少数异常旁路

PForDelta code假设块内大多数值落在 [base,base+2^b-1]。

主流中每项占 b 位；exception 槽写 escape，完整值另存 w 位异常数组。若块长 k、异常数 e，粗略位成本为：

kb+ew+\mathrm{header}

b 增大，主流每项都多付位但异常减少；b 减小，主流紧凑却增加 escape、异常值和 merge 工作。原方案常让约90%值落入范围；更稳妥的实现枚举候选 b，联合估计 header、异常位置、异常值与解码成本。

固定 b 使多个整数能装进机器字并 SIMD unpack；异常在第二流顺序合并，可减少数据依赖。搜索索引中它常比位级通用码稍大，却因 word alignment、branchless decode 和批处理更快。

变长字节与 (s,c)-dense：用对齐换吞吐

variable-byte code把 B(x) 从低位起每7位一组。非末组状态位为1，末组状态位为0；解码读到小于128的字节停止。

|VB(x)| = 8\left\lceil\frac{|B(x)|}{7}\right\rceil \text{ bits}

它至少用1字节，平均有 padding 和状态位浪费，却避免任意 bit offset，解码循环简单、载入自然对齐。本页的 (s,c)-dense code 把256种字节配置分成 s 个 stopper 与 c 个 continuer，不要求各128个。

一字节可表示 s 个值，两字节再表示 sc 个，k 字节层新增 sc^(k-1) 个。增大 s 会让更多高频小值一字节完成，却减少 continuation 基数，使长值需要更多字节；最优 s 由整数频率分布决定。

DecodeVariableByte(stream):
  value = 0
  repeat:
    byte = nextByte()
    value = (value << 7) | (byte & 0x7f)
  until byte < 128
  return value

Interpolative code：用邻居约束动态缩小区间

Interpolative code 面向严格递增序列 S'。原 d-gap 序列可先做前缀和得到 S'。对索引区间 [l,r] 与已知值域 [low,hi]，取中点 m。

因为值严格递增，中点满足：

low+m-l \le S'[m] \le hi-r+m

只需编码 S'[m] 相对下界的偏移，再递归左右半区，并用中点值收紧新的 hi 或 low。

密集区间的可行值域很小，甚至只有一个值而无需输出位；聚簇序列因此压缩很好。相同整数在不同上下文中可能获得不同 code，整体也不是逐项 prefix-free。它能优于“静态 prefix code 最优”的 Huffman，并不矛盾，因为两者优化的模型类别不同。

代价是递归依赖和随机访问困难：要解一个元素，往往先解祖先中点。适合整块顺序解码且聚簇明显的 posting list，不适合频繁 Access(i)。

Elias-Fano：单调序列的紧凑索引

Elias-Fano code输入 n 个递增整数，值域 [0,u)。选：

\ell = \left\lceil\log_2\frac{u}{n}\right\rceil

每个值 x 拆为 high=floor(x/2^ell) 与 ell 位 low。所有 low 连成 L；按 high bucket 从小到大，每桶有 c 个元素就向 H 写 c 个1再写0。

L 长 n ell；H 有 n 个1和约 u/2^ell 个0。选定 ell 后总空间：

2n+n\log_2\frac{u}{n} \text{ bits}

与输入分布无关，对均匀散布单调序列只比信息下界约多2 bits/item。

Access(i) 先取 L 的第 i 个 ell-bit block。H 中第 i 个1的位置为 Select1(i,H)；减去之前 i 个1，就得到它之前的0数，也就是 high bucket。拼接 high 与 low 恢复 x，支持 O(1) 随机访问，Select 辅助结构只需 o(n) 位。

NextGEQ(x) 先由 high(x) 和 Select0 定位目标 bucket 的起点，再在该 bucket 的 low 段找首个不小于 low(x) 的值；若没有就取下一个非空 bucket。分桶版 Elias-Fano 可进一步适应聚簇：一级索引块末值，二级对块内相对值单独选参数，以少量访问开销换更小空间。

选择编码要同时看分布、粒度与操作

Elias gamma/delta 无 header，适合未知分布的小规模流；Rice 适合近几何且尺度稳定；PForDelta 适合块内集中、追求 SIMD 吞吐；Variable-byte 适合字节对齐和简单高速解码；Interpolative 擅长聚簇单调块；Elias-Fano 在压缩、Access、NextGEQ 之间平衡。

评测先固定表示：绝对值还是 d-gap，是否严格递增，block size、header 和异常流是否计入。正确性做 encode/decode round-trip、随机截断、损坏输入、边界1、2^k-1、2^k、最大 word 和跨块前缀和溢出。

性能同时报告 bits/int、编码/解码 Mints/s、分支误预测、SIMD 宽度、随机 Access 延迟、NextGEQ 跳步与缓存 miss。最小 bitstream 未必最省查询时间；解压更多数据导致的带宽与 CPU 也可能抵消磁盘节省。

先预测，再操作三个章专属实验

分步1 / 3

1. 成本模型与工作集

在“11 Integer Coding”中先预测层级和访问模式如何改变“Elias-Fano ≤ n ceil(log2(U/n)) + 2n bits”，再切换工作集与局部性；最终结果相同不代表代价相同。

Cost-model laboratory

11 Integer Coding

按整数分布、单调性与查询需求选择自定界和块级编码

工作集所在层级

规模8192

传输256

相对成本8×

Elias-Fano ≤ n ceil(log2(U/n)) + 2n bits

不变量：编码可唯一解码，整数域与零值约定明确，round-trip 保持完整序列

可重放工程合同

“11 Integer Coding”的实验必须保留：输入域、参数、逐项码字、位偏移、总位数、解码序列与边界样例。本章性能数据至少预热一次、重复多次并报告分布；正确性必须与独立预言机比较，不能只比较两个共享同一错误的优化实现。

练习与答案

练习

问题 1：正式目录。 “11 Integer Coding”的公开目录边界是什么，平台如何证明没有把其他章主题混入？

问题 2：最小反例。 怎样验证“Elias-Fano ≤ n ceil(log2(U/n)) + 2n bits”不是只写在页面上的公式？

问题 3：恢复证据。 怎样证明“把只支持正整数的码直接用于零或在差分时溢出，破坏码流边界”已经修复？

本章回顾

最短二进制直接拼接不可自定界；整数流必须能唯一切分。
posting list 先排序做 d-gap，常把大 ID 变成小正整数。
Gamma 长度约2log x，Delta 以 gamma 编码长度，渐近更接近最短二进制。
Rice 把 x-1 分成一元 quotient 与 k 位 remainder，k 由几何尺度决定。
PForDelta 把块内多数值定宽编码，异常通过 escape 与旁路数组恢复。
Variable-byte 每字节7位 payload，以对齐和简单循环换少量空间。
(s,c)-dense 根据频率调整 stopper/continuer 配额。
Interpolative 用严格递增邻界缩小中点可行范围，适合聚簇块。
Elias-Fano 拆 high/low，以约 2n+n log(u/n) bits 保存单调序列。
Select 支持 Elias-Fano 常数 Access，bucket 定位支持高效 NextGEQ。