分块 Elias–Fano 与精确分区

形式陈述

普通Elias–Fano用整个序列的平均间距选择低位宽。若一些值挤成连续段，另一些值跨越大空隙，同一个低位宽便难以同时适配。分块版本按局部跨度选择表示，但每多一块也多一份定位目录；分区必须把这项代价一起优化。[1, §§3–4]

输入为严格递增整数列

0\le x_0<\cdots<x_{N-1}<U,\qquad U\ge1.

空列单独编码，查询返回无值。非空列划成连续下标区间 $[i,j)$ 。本块基数、大小及局部宇宙为

a_i=\begin{cases}0&i=0,\\x_{i-1}+1&i>0,\end{cases} \quad k=j-i,\quad u=x_{j-1}-a_i+1.

存的是 $y_h=x_{i+h}-a_i\in[0,u)$ 。因为输入严格递增， $u\ge k$ ，且本块最后一个局部值恰为 $u-1$ 。块前空隙仍进入 $u$ ，不能凭空丢掉；恢复基数只需上一块末值。

每块选择哪一种负载

本页固定三种模式，并按下表计算负载位数 $L(k,u)$ 。

模式	条件与内容	位数
ALL，编号0	$u=k$ ，隐含全部 $0,1,\ldots,k-1$	0
BITMAP，编号1	长度 $u$ 的位串，在各 $y_h$ 处置1	$u$
EF，编号2	低位加一元高位，使用原EF接口	$k\ell+k+\lceil u/2^\ell\rceil$

其中 $\ell=\lfloor\log_2(u/k)\rfloor$ 。若 $u=k$ 取ALL；否则比较BITMAP与EF，位数相等时取BITMAP。EF的最后桶零位也写入负载；不能一处用 $k+\lceil u/2^\ell\rceil$ ，另一处又省掉末尾零后仍报告相同长度。

固定宽目录与完整文件长

令

W=\lceil\log_2U\rceil,\qquad C=\lceil\log_2(N+1)\rceil, \qquad P_{\max}=N(W+3),\quad P=\lceil\log_2(P_{\max}+1)\rceil.

每块目录保存：两位模式、本块末值的 $W$ 位、本块结束时累计元素数的 $C$ 位，以及负载起点的 $P$ 位。固定目录费为

F=2+W+C+P.

$U=1$ 时末值只可能为0， $W=0$ 合法；空列的 $C=P=0$ 也合法。选中负载至多等于EF长度，而 $\lceil u/2^\ell\rceil\le2k$ ，故每块负载不超过 $k(W+3)$ 。任何分区的总负载都不超过 $P_{\max}$ ，该指针宽度在优化前已经确定。

文件头依次存gamma码 $N+1,U$ ，再用固定 $C,P$ 位存块数和负载总长。正整数 $v$ 的gamma码长度为 $2\lfloor\log_2v\rfloor+1$ ；它可由前导零数确定后续字段长。其后紧排全部目录和全部负载，末字节补零。因此在固定 $N,U$ 下，头长度 $H$ 不随分区改变，总有效位数为

H+\sum_{[i,j)\text{为块}}\bigl(F+L(j-i,x_{j-1}-a_i+1)\bigr).

字节填充再增加至多七位。下面优化这个明确格式，不声称它在所有整数压缩格式中最短。

直觉

分块的收益来自“在本块中，哪些数字已经由边界推知”。一整段连续值只要知道前一块结束在哪、当前块有多少项，内部就无需再存。稀疏块用EF节省大量零；中等密度块直接用位图，有时反而更短。

块并非越小越好。一个单元素块可以有很短的负载，却仍要支付模式、末值、累计长度和指针四项。把所有元素切成单块，相当于反复保存导航信息；精确分区比较的是整块账单，而不是仅比较内部压缩率。

相同八个整数按一块、三块或八块编码，目录费与负载一起决定三块方案更短 — 局部密度和目录费共同决定分界

例子与边界

两个密集簇之间的大空隙

取 $U=1024$ ，序列为

text

0, 1, 2, 3, 1000, 1001, 1002, 1003

这里 $N=8,W=10,C=4,P=7$ ，每块目录费 $F=23$ 位。一个块的局部宇宙为1004， $\ell=6$ ，EF负载为 $8\times6+8+16=72$ 位，块账单95位。

若在下标4、5、8结束三块，得到

下标块	基数	局部宇宙 $u$	模式	负载	含目录
[0,4)	0	4	ALL	0	23
[4,5)	4	997	EF	12	35
[5,8)	1001	3	ALL	0	23

中间块只存局部值996。它有 $\ell=9$ ，低九位为484，高位为1；一元高位串是 010，所以负载 $9+3=12$ 位。大空隙并未免费消失，而是由这一块承担。

三块账单共81位，目录占69位，负载占12位。头为39位，总有效长度120位，恰15字节；参考器输出的十六进制为

text

1200400318006802fa1401f5c0cf22

同一格式的一块方案是134位，逐元素八块是235位。仅看12位负载会夸大压缩收益；只在两簇之间切一刀也未达到本例最优。

改变分布，最优切点也会改变

仍在 $U=1024$ 中，把八个值改成 $0,1,\ldots,7$ ，一块ALL就够，总有效长度62位。改成 $0,128,\ldots,896$ ，精确最优同样只用一块，但采用EF，总长133位。相同元素数和全局宇宙并不决定最优分区；局部间隙和每块固定费都会参与。

重复值不属于本页输入。原EF可以表示非降序列，但ALL条件、位图的一个位置至多一个元素以及 $u\ge k$ 都依赖严格递增，不能只放松入口比较而保留本页其余证明。无序输入也必须先排序，并将排序成本单列。

零负载不是缺数据。空列 $N=0,U=1$ 只写两个gamma码 1,1，有效长度两位；序列 $[0]$ 在同一宇宙中有一块ALL，但仍需头和目录，共12位。解码器靠元素数和模式区分这些情况。

推论与应用

用前缀状态求精确分区

令 $D[j]$ 为前 $j$ 项的最小块账单，不含共同文件头。按动态规划取

D[0]=0,\qquad D[j]=\min_{0\le i<j}\left\{ D[i]+F+L(j-i,x_{j-1}-a_i+1) \right\}.

记录一个达到最小值的 $i$ ，从 $j=N$ 反向走回零，即恢复全部块。本参考器按 $i$ 从小到大检查，只在严格变小时替换，因而平局选择最小末块起点。主例的完整表是

(D[0],\ldots,D[8])=(0,23,23,23,23,58,68,77,81).

状态为什么足够？不论前缀怎样分区，只要在下标 $i$ 截断，下一个块的基数都恰为 $x_{i-1}+1$ ；目录字段宽度也已经由全局 $N,U$ 固定。因此后缀块费用不依赖更早切点。任何最优前缀的末块都有一个起点 $i$ ，去掉它后若剩余前缀不是最优，就可以替换为更便宜方案而保持末块编码不变。反过来，每个递推候选都能拼成有效分区，给出上下两个方向的最优性证明。

把 $0,1,\ldots,N$ 看成节点，边 $i\to j$ 的权就是该块账单，这也是一条有向无环图最短路。实现无需存下全部 $\Theta(N^2)$ 条边：逐个 $j$ 枚举 $i$ 即可，保留 $D$ 和回溯指针只用 $O(N)$ 个整数。原论文另外给出近似剪枝算法；本页没有实现它，不借用其近线性时间结论。[1, §4.2]

位流为何能独立恢复全部值

目录给当前块末值和前块末值，由此得到 $a_i,u$ ；相邻累计元素数之差给 $k$ 。ALL直接恢复整个连续区间；BITMAP列出1的位置；EF按原高低位公式恢复局部值，再加 $a_i$ 。这些步骤都不需要原始整数列。

装载器还核每块元素数为正、累计数最终为 $N$ 、末值严格递增且小于 $U$ 、负载指针等于此前负载和。EF必须解出恰好 $k$ 项，所有局部值严格递增，最后值与目录一致；未使用模式3、非规范局部模式、截断字段、额外字节及非零填充均拒绝。调用者预先选择RRR或本格式的解码器，这两个独立教学格式没有自动类型标记。

访问下标 $h$ ，先对累计元素数二分，找到首个结束数大于 $h$ 的块，再定位块内第 $h-i$ 项。查询 next_geq(z)，其中 $0\le z\le U$ ，先找末值不小于 $z$ 的第一块，再在该块取第一个不小于 $z$ 的值；若不存在这样的块，返回 $\bot$ 。结果同时给出原序列下标和数值。本例查询500得到 $(4,1000)$ ，查询1004无值，access(6)得到1002。

构建、查询和存储怎样计费

在Word-RAM中令一个字能容纳键、编码地址及总费用，提供整数乘除、移位和最高有效位定位。 $\ell$ 可由 $\lfloor u/k\rfloor$ 的位长取得，因此每条候选边费用可在常数次字操作内计算。DP需要 $O(N^2+1)$ 时间、 $O(N+1)$ 个工作字；把所选块真正写成 $S$ 位文件另付 $O(S+N+1)$ 的逐位工作。任意精度整数下，每个算术操作还要支付其位成本。

参考器没有为局部高位串额外建select索引。目录字段逐位读取，若选中块有 $k_b$ 个元素，则查询上界为 $O(F\log(K+1)+k_b(W+1)+1)$ 次单字操作，其中 $K$ 是块数；位图仅在它不长于EF时被选中，因此扫描该块也满足此界。它只解所选块，不先展开全部序列。装载阶段会完整验证文件，需另付全文件扫描和合法性检查，不能把验证时间算进首次查询后再省略。

如果另给每个EF块加常数select索引，查询可以更快，但辅助位数也会改变块费用；重新优化时必须把它们加入 $L$ 或目录费。本文报告的是实际紧存字节数，不是Python解释器中列表和整数对象的堆大小。文件最小位长也不表示运行时最省内存。

终点任务：交出主例三块目录、12位负载、120位完整文件和全部DP前驱；穷举七个可能切点的128种取舍，独立核最优81。再把RRR例中的1位置作为输入，比较两份文件及查询结果，见分块压缩练习。

参考资料

Giuseppe Ottaviano、Rossano Venturini，Partitioned Elias-Fano Indexes，SIGIR2014，§§3、4.1–4.2，PDF4–6页：局部三模式、目录与分区图。本文自行固定半开宇宙、前块末值加一、固定宽头/目录和确定性平局；精确二次DP与原文的近似加速区分。
Sebastiano Vigna，Quasi-Succinct Indices，WSDM2013，§4；高低位表示与查询原语复用本库Elias–Fano条目，不另定义一套高位位置约定。

形式陈述 ​

每块选择哪一种负载 ​

固定宽目录与完整文件长 ​

两个密集簇之间的大空隙 ​

改变分布，最优切点也会改变 ​

用前缀状态求精确分区 ​

位流为何能独立恢复全部值 ​

构建、查询和存储怎样计费 ​

反向链接