简洁位向量

目标与端点 ​

对位串 $B[0..n)$，固定rank/select公理库Rank 与 Select 查询Rank and select在位串上计算前缀频数或定位第 j 次出现，并固定端点和索引约定。接口如下：

$${\mathrm{rank}}_1(i)=\sum _{j=0}^{i-1}B[j],{\mathrm{select}}_1(k)=min\{i:{\mathrm{rank}}_1(i+1)=k\}.$$

本文 rank 使用半开前缀、select 的 $k$ 从 1 开始。目标是在原始 $n$ 位之外只用 $o(n)$ 位索引，查询 $O(1)$。

两级索引与微表 ​

每 ${\log }^{2}n$ 位设 superblock，存从串首到该处的全局 rank，每项 $O(\log n)$ 位，总计 $O(n/\log n)$ 位。每个 superblock 内再按约 $\frac{1}{2}\log n$ 位分 block，存相对 rank，每项 $O(\log \log n)$ 位，总计 $O(n\log \log n/\log n)=o(n)$。块内答案按位型查表；类型数 $2^{(\log n)/2}=\sqrt{n}$，共享表也是 $o(n)$。

select 不能从 rank 的常数界自动得到，通常还要按每若干个 1 采样位置，并对稠密/稀疏区间分别查表或显式存储。

文本索引例子 ​

位串标记文档边界。rank${}_1(i)$ 给位置 $i$ 前已有多少文档，select${}_1(k)$ 给第 $k$ 个文档起点；不复制文档 ID 数组，就能在接近信息下界的空间里完成双向映射。

空间与动态边界 ​

$n+o(n)$ 是 dense 位串目标；若只有 $m\ll n$ 个 1，更自然的信息下界是 $\log (\genfrac{}{}{0ex}{}{n}{m})$，需 indexable dictionary。动态插删会移动后缀位位置，静态索引不直接适用。所有 $O(1)$ 假定 $w=\mathrm{\Omega }(\log n)$ 且表查/位操作为常数。

Select 的长短区间 ​

一种构造每 $s$ 个 1 存一次绝对位置。若相邻样本跨越很长位区间，就显式存这 $s$ 个 1 的位置；若区间短，则再分小块采样并用微表。长区间总数受位串总长限制，短区间表型受块长度限制，二者额外位数都可压到 $o(n)$。

信息论意义上的 succinct 是“表示长度等于对象最优编码加低阶冗余”，不是一般文件压缩。查询索引、全局共享表是否计入空间及 word size 都要在声称 $n+o(n)$ 时说明。

Rank 查询真正读取什么 ​

把位置 $i$ 写成“超块编号、块编号、块内偏移”。答案由三项相加：超块开始前的全局 1 数、该超块内当前块之前的局部 1 数，以及微块类型表对块内前缀的答案。三次索引都必须能装入 $O(1)$ 个机器字，才得到常数时间。

典型参数令超块长 ${\log }^{2}n$、微块长 $\frac{1}{2}\log n$。超块计数用 $O(n/\log n)$ 位，局部计数也为 $o(n)$，所有微块类型共享的表大小为 $2^{(\log n)/2}\mathrm{polylog}n=o(n)$。若为每个位串实例各复制一份表，空间账本会改变。

select 不能简单对 rank 做普通二分，否则时间为 $O(\log n)$。常数 select 需要按 1 的个数抽样，并把稠密短区间查表、稀疏长区间显式列位置；端点不存在时应返回统一哨兵而非越界下标。

参考资料

• Guy Jacobson, Space-Efficient Static Trees and Graphs, FOCS, 1989.
• Rajeev Raman, Venkatesh Raman, Srinivasa Rao, Succinct Indexable Dictionaries, TALG, 2007.