RRR 类与偏移编码 | Codeboy's Blog

形式陈述

长度为 $N$ 、含 $m$ 个1的位串有 $\binom Nm$ 种。若仍把每位原样保存，已经用了 $N$ 位，再精简查询目录也无法省掉这部分。RRR把每个小块拆成“有多少个1”与“这些1怎样排列”两份信息，以二项式系数给出类内编码的精确范围。[1, §4.1]

本页输入静态位串 $B[0..N)$ 。查询沿用rank/select：rank(i)数半开前缀 $[0,i)$ 的1， $0\le i\le N$ ；select(k)返回第 $k$ 个1的零基位置， $k$ 从1起，不存在返回 $\bot$ 。编码同时保留access，允许空串、全零、全一和不足一整块的末块。

类别和可逆偏移

取块宽 $b\ge1$ ，第 $j$ 块实际长度为 $s_j=\min\{b,N-jb\}$ 。类别 $c_j$ 是该块1的个数。若1的位置为

0\le p_1<\cdots<p_{c_j}<s_j,

定义偏移

z_j=\sum_{h=1}^{c_j}\binom{p_h}{h},\qquad 0\le z_j<\binom{s_j}{c_j}.

这里采用colex次序：比较两个位置集合时，最大不同位置属于哪一边，哪一边就排后。它不是把左到右显示的二进制文本按普通字典序排序。类别固定后， $z_j$ 恰好无遗漏地编号全部 $\binom{s_j}{c_j}$ 种排列。

类别紧存为 $\lceil\log_2(b+1)\rceil$ 位；偏移用

w_j=\left\lceil\log_2\binom{s_j}{c_j}\right\rceil

位。 $c_j=0$ 或 $c_j=s_j$ 时只有一种排列， $w_j=0$ ，偏移不占位。若组合数不是2的幂，尚有未使用的二进制码，解码器必须拒绝 $z_j\ge\binom{s_j}{c_j}$ 。末块按真实 $s_j$ 处理，不把补入的零算进原位串。

同时保存两种前缀

偏移字段长短不一，不能用 $j$ 乘固定宽度找到第 $j$ 个字段。定义块前累计1数和偏移起点

A_j=\sum_{h<j}c_h,\qquad O_j=\sum_{h<j}w_h.

每 $t\ge1$ 块组成一大块。在大块起点存全局 $(A_j,O_j)$ ；每个小块存相对本大块起点的两个差值。全局字段各用 $\lceil\log_2(N+1)\rceil$ 位，因为总1数和总偏移位数均不超过 $N$ 。局部字段各用 $\lceil\log_2(bt+1)\rceil$ 位。

两个目录作用不同： $A_j$ 给rank已跨过的1数， $O_j$ 给压缩数据的物理位置。类别给出 $w_j$ 后，从 $O_j$ 读取偏移，便能解出本块。查询 $i<N$ 时令 $j=\lfloor i/b\rfloor$ ，把 $A_j$ 与块内前 $i-jb$ 位的1数相加； $i=N$ 直接返回头中总数 $m$ 。

直觉

八位全零和八位全一各只有一种形状。类别已经把形状说完，再存八位内容没有新增信息。八位恰有四个1时却有70种形状，类内偏移需要七位。压缩效果取决于每块所属类别，而非只把所有块换成同一个较短整数。

不等长编码省下内容位，也打破了固定宽数组的直接寻址。两级目录把“此前累计多少位”压成少量全局数和较小的局部数；类内微表则把解码工作限制在一个小块。空间节省和快速定位分别由这两步承担。

四个八位块的类别为0、8、4、1，偏移位宽为0、0、7、3，目录分别定位累计1数与负载起点 — 类别、偏移与两种前缀目录

例子与边界

四块怎样变成十位偏移

取 $b=8,t=2$ ，位串为

text

00000000 11111111 10101010 00010000

第三块的1在块内位置 $0,2,4,6$ ，故

z=\binom01+\binom22+\binom43+\binom64=0+1+4+15=20.

块下标	类别 $c_j$	偏移 $z_j$	位宽 $w_j$	$(A_j,O_j)$
0	0	0	0	(0,0)
1	8	0	0	(0,0)
2	4	20	7	(8,0)
3	1	3	3	(12,7)

偏移串是 0010100 011，共10位；类别另用 $4\times4=16$ 位。计算rank(21)时，前两块共有8个1，第三块的前五位 10101 有3个1，因此得到11。第11个1位于原串下标20；第14个1不存在。

这不是一份“总共10位”的文件。参考程序的头为正整数 $N+1,b,t$ 的gamma码，再加总1数和偏移总长。gamma码把一个正整数的二进制表示前置“位长减一”个零，因此长度为 $2\lfloor\log_2 x\rfloor+1$ 。本例头33位，类别16位，全局目录24位，局部目录40位，偏移10位，共123位；最后补五个零对齐到16字节。小例为了可手算，目录反而使总长超过原始32位。

端点不能从公式中漏掉

块宽8有九个可能类别，故需要四位类别码；写成 $\lceil\log_2 b\rceil=3$ 会无法表示全一块的类别8。相反，只有一种类内排列时偏移宽度就是零，不应为了“每块至少有一个字段”额外写一个零位。

若末块长度为3，类别2只有三种排列。两位偏移 11 表示数值3，必须拒绝；按整块宽8解码会错误地把它当成合法排列。修改位串长度而不重建末块类别、目录和偏移，也不能保持原编码有效。

这是静态表示。插入一位会改变后续分块，翻转一位可能改变类别与偏移宽度，后续位流和目录也随之移动。动态维护需要另一个更新结构，不能从静态rank的查询时间推出。

推论与应用

组合秩为什么恰好可逆

固定长度 $s$ 和1数 $c>0$ 。最大1位置为 $p$ 的集合，其余 $c-1$ 个位置来自 $[0,p)$ ，共有 $\binom p{c-1}$ 个。最大位置小于 $p$ 的集合共有 $\binom pc$ 个，因此当前组恰占从 $\binom pc$ 开始的连续区间。组内再按剩余位置递归排列，就得到前面的求和式。

逆过程从 $j=c$ 开始，找最大的 $p<s$ 使 $\binom pj\le z$ ，把位置 $p$ 置1，再用 $z-\binom pj$ 解长度 $p$ 、1数 $j-1$ 的问题。这样的 $p$ 存在，因为 $\binom{j-1}j=0$ ；由最大性和Pascal恒等式，余数满足

0\le z-\binom pj<\binom{p+1}j-\binom pj=\binom p{j-1}.

所以每次递归都进入下一层的合法范围，最后唯一到达空集合和偏移0。实现中让位置指针只向左移动，各轮合计检查 $O(s)$ 个二项式值，不必生成全部位型再搜索。

信息主项与导航冗余分别付账

令块数 $q=\lceil N/b\rceil$ 。固定各块的1数后，独立选择类内排列有 $\prod_j\binom{s_j}{c_j}$ 种；它们只是全体含 $m$ 个1的长位串的一部分。因此

\sum_j w_j\le\log_2\binom Nm+q.

这只界定偏移负载。类别和目录还需

q\lceil\log_2(b+1)\rceil +2\lceil q/t\rceil\lceil\log_2(N+1)\rceil +2q\lceil\log_2(bt+1)\rceil

位。头和字节对齐另计。对足够大的 $N$ 取 $b=\lfloor\tfrac12\log_2N\rfloor$ 、 $t=\lceil\log_2N\rceil$ ，这些开销连同 $q$ 都是 $O(N\log\log N/\log N)$ 。

在Word-RAM上，固定 $w=\Theta(\log N)$ 并提供字内移位、掩码、乘除和随机访存，每个目录字段及块偏移占常数个字。用微块查表为全部 $s\le b$ 的位型存类别、偏移、原块及局部前缀计数，表空间为 $O(2^b b\log(b+1))=o(N)$ ，也计入单实例。两级目录加一次微表查询便给出常数时间access/rank，总空间为

\log_2\binom Nm+O\!\left(\frac{N\log\log N}{\log N}\right)\text{ bit}.

表可按全部短位型构造，一个直接上界为 $O(2^b b^2)$ 次字操作；读入并编码位串另付 $O(N)$ 。小规模和空串单独处理，渐近式不要求对 $N=0$ 取对数。此界的低阶项相对于位串长度 $N$ ，不承诺在极稀疏时也是 $o(m)$ 。

查询实现的速度界不能混用

完整RRR的常数select还要加长短间隔索引。[1, §4.1] 旧静态select结构需要读取少量 $O(\log N)$ 位局部窗口；此处一个窗口跨常数个压缩块，经微表即可恢复，所以可以复用该索引，仍须计入它的 $o(N)$ 空间。这个组合与用rank二分是两种实现。

本页Python参考器选择可逐位核验的实现：文件仅存实际字节，装载时校验全目录、类内未用码和末字节零填充；查询时组合逆秩解一个块，select用rank二分。一次块解码检查 $O(b)$ 个二项式值；一次rank另读 $O(\log(N+1)+\log(bt+1)+b)$ 位，二项式求值及Python大整数运算的成本另外支付。select再乘 $O(\log(N+1))$ 次rank调用。这份程序没有构造常数查询微表，不能拿理论查表时间给它记账。

终点任务：重建上述123位文件，逐项核rank与select，再将1的位置交给分块Elias–Fano。比较时分别列负载、导航目录、文件头与字节填充，见分块压缩练习。

参考资料

Rajeev Raman、Venkatesh Raman、S. Srinivasa Rao，Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets，2007作者稿，§1.1.3、§4.1 Lemma4.1，PDF/印刷pp.12–13：完整位向量接口、类别/偏移和选择索引。本文用 $N$ 表示位串长度，避免与原文的元素数记号混淆。
Carl Kingsford，Indexable Compressed Bitvectors，CMU 02-714，PDF3–13页：分块、两个前缀目录及组合乘积计数；本文端点采用本库半开rank约定，并单独固定类别码宽和末块长度。

形式陈述 ​

类别和可逆偏移 ​

同时保存两种前缀 ​

四块怎样变成十位偏移 ​

端点不能从公式中漏掉 ​

组合秩为什么恰好可逆 ​

信息主项与导航冗余分别付账 ​

查询实现的速度界不能混用 ​

反向链接