Elias–Fano 编码

高低位拆分 ​

对前驱查询公理库Word-RAM 前驱问题Predecessor problem在 Word-RAM 的有限整数宇宙中维护有序集合，并查询不大于给定键的最大成员。所用的严格递增序列 $0\le x_0<\cdots <x_{n-1}<U$，取

$$\ell =max(0,\lfloor {\log }_2(U/n)\rfloor ).$$

低 $\ell$ 位顺序紧存，共 $n\ell$ 位。高位 $h_i=\lfloor x_i/2^{\ell }\rfloor$ 单调，把位向量 $H$ 的位置 $h_i+i$ 置 1；于是

$$h_i={\mathrm{select}}_1(H,i+1)-i.$$

高位向量长度至多 $n+U/2^{\ell }=O(n)$，总空间 $n\log \left(U/n\right)+O(n)$ 位。

访问与前驱 ​

access/select 由一次高位 select 和低位读取恢复。前驱 $x$ 先定位高桶：rank/select 找到高位等于 $\lfloor x/2^{\ell }\rfloor$ 的连续 1 区间，再在对应低位段找最后一个不超过目标低位的值；配适当索引可达到常数或模型规定的快速查询。

稀疏倒排例子 ​

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

边界 ​

输入必须有序；无序集合须先排序并计成本。重复非降序列可用 $y_i=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$ 位，却约把高位宇宙长度减半。若 $U<n$ 或序列允许大量重复，原参数式需先做单调变换，不能直接取负的 $\log \left(U/n\right)$。

前驱查询经过哪些位 ​

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

Elias–Fano 的优势取决于单调与稀疏：访问第 $i$ 项可由一次 select 恢复高位，再拼低位；普通未排序数组没有这个一元单调编码。若序列允许重复，需要把严格递增改为非降版本并明确 select 解码式，不能继续直接套 $h_i+i$ 的唯一位置解释。

参考资料

• Peter Elias, Efficient Storage and Retrieval by Content and Address of Static Files, JACM, 1974.
• Sebastiano Vigna, Quasi-Succinct Indices, WSDM, 2013.