Elias–Fano 编码 | Codeboy's Blog

形式陈述

高低位拆分

固定整数 $U\ge1$ 。本页先编码严格递增的整数有限序列

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

空序列单独记录长度零，访问和前驱查询都报告无值。对非空序列，令

\ell=\left\lfloor\log_2(U/n)\right\rfloor,\qquad q=\left\lceil U/2^\ell\right\rceil.

低位 $l_i=x_i\bmod2^\ell$ 以固定宽度顺序紧存，共 $n\ell$ 位。高位 $h_i=\lfloor x_i/2^\ell\rfloor$ 非降；建立含 $n$ 个 1 与 $q$ 个 0 的位串 $H$ ，第 $h$ 桶写出其元素数个 1，再写一个 0。于是第 $i+1$ 个 1 的零基位置恰为 $h_i+i$ ，所以

h_i=\operatorname{select}_1(H,i+1)-i, \qquad x_i=2^\ell h_i+l_i.

这里遵守rank/select的“位置从零、出现次数从一”约定。

因为 $2^\ell\le U/n<2^{\ell+1}$ ，有 $q<2n+1$ ；高位串长度为 $n+q=O(n)$ ，总编码长为

n\ell+n+q\le n\log_2(U/n)+O(n).

参数 $n,U,\ell$ 的元数据另占 $O(\log(U+1))$ 位，不能把编码负载和文件头混在一起。对严格递增集合，信息下界是 $\log_2\binom Un$ 位，稀疏区间内其主项正是 $n\log_2(U/n)$ 。

访问与前驱

给 $H$ 加上支持常数时间 select 的静态索引，辅助空间为 $o(|H|)$ 位；在一字容纳键、地址和一段低位字段，并支持单位时间乘法、可变移位与位掩码的Word-RAM上，一次 select 和常数次字操作即可访问 $x_i$ 。这项速度依赖所选索引，裸位串本身只规定表示。

对前驱查询 $x\in[0,U)$ ，令 $h=\lfloor x/2^\ell\rfloor$ 、 $l=x\bmod2^\ell$ 。第 $h$ 桶的序列下标范围是 $[a_h,b_h)$ ，其中

a_0=0,\qquad a_h=\operatorname{select}_0(H,h)-(h-1)\quad(h\ge1),\qquad b_h=\operatorname{select}_0(H,h+1)-h.

这些式子从零位置减去此前的零数量，留下已编码元素数。在该桶非降的低位数组中二分找最后一个不超过 $l$ 的值；若不存在，则返回下标 $a_h-1$ 的元素， $a_h=0$ 时报告无前驱。

严格递增输入使每桶至多有 $2^\ell$ 个元素，所以这个直接实现的最坏前驱时间为 $O(1+\ell)=O(1+\log(U/n))$ ，访问则为 $O(1)$ 。更强的前驱索引需要另报空间与字操作条件，不能由一次 select 的访问界推成无条件常数时间前驱。

直觉

单调序列的高位不会回退，因此无需为每个数重复存完整高位，只要用一元位串记录“向前跨了多少桶”；低位则固定宽度紧排。参数 $\ell$ 在每项多存一位低位与把高位桶数约减半之间取得平衡，最终空间由平均间距 $U/n$ 而非整个宇宙 $U$ 决定。

例子与边界

稀疏倒排例子

某词在文档 ID 宇宙 $[0,U)$ 中只出现 $n$ 次，ID 已递增。高位一元串记录粗桶，低位数组记录桶内偏移；当 $U/n$ 大时，每项主要花 $\log(U/n)$ 位，比直接存每个 $\log U$ 位 ID 更省。

边界

输入必须有序；无序集合须先排序并计成本。非降序列也能直接编码：即使若干 $h_i$ 相等， $h_i+i$ 仍严格递增，因此各个 1 的位置始终不同。重复值不要求先做 $x_i+i$ 变换。动态插入会移动高位位向量中的后续位置，静态 $O(1)$ select 不能无条件继承。高位位置公式最易产生一基/零基错误。

高位一元串例子

取 $U=16,n=4$ ，序列 $1,3,10,14$ ，有 $\ell=2$ 。低位为 $1,3,2,2$ ，高位为 $0,0,2,3$ ；在位置 $h_i+i$ 即 $0,1,4,6$ 置 1。对第三项（零基 $i=2$ ），select 得位置 4，减 $i$ 恢复高位 2，再拼低位 2 得 10。

选择 $\ell$ 平衡两部分：增加一位低位花 $n$ 位，却约把高位宇宙长度减半。对允许重复的非降输入，取 $\ell=\max\{0,\lfloor\log_2(U/n)\rfloor\}$ ，同一解码式仍成立，总负载为 $n\max\{0,\log_2(U/n)\}+O(n)$ 。这时每桶可包含许多相同值，上述“桶内至多 $2^\ell$ 项”的前驱时间论证便不再适用。

推论与应用

前驱查询经过哪些位

对查询值 $x$ ，先拆成高位 $h$ 与低位 $l$ 。借高位一元串的 select/rank 找出所有高位小于 $h$ 的最后元素，并定位高位恰为 $h$ 的连续候选区间；只在该区间比较低位，取不超过 $l$ 的最后一个。若同高位组为空，就返回上一非空高位组末项。

Elias–Fano 的优势取决于单调与稀疏：访问第 $i$ 项可由一次 select 恢复高位，再拼低位；普通未排序数组没有这个一元单调编码。重复版本沿用同一高位位置式和 select 解码式，但用带重数序列的大小与查询成本分析，不能套用严格集合的计数下界。

局部密度差异明显时，分块Elias–Fano为每块重设基数与宇宙，并在连续段、位图和EF之间选择。每块末值、累计元素数与负载指针也占空间；把这些目录费加入前缀递推，才能比较切块后的完整文件长，而不是只优化块内负载。

参考资料

Peter Elias, Efficient Storage and Retrieval by Content and Address of Static Files, JACM, 1974.
Sebastiano Vigna, Quasi-Succinct Indices, WSDM, 2013，§4：非降序列的高低位表示、零低位宽边界与查询实现。

形式陈述 ​

高低位拆分 ​

访问与前驱 ​

稀疏倒排例子 ​

边界 ​

高位一元串例子 ​

前驱查询经过哪些位 ​

反向链接