简洁位向量 | Codeboy's Blog

形式陈述

目标与端点

对位串 $B[0..n)$ ，固定rank/select接口如下：

\operatorname{rank}_1(i)=\sum_{j=0}^{i-1}B[j],\qquad \operatorname{select}_1(k)=\min\{i:\operatorname{rank}_1(i+1)=k\}.

本文 rank 使用半开前缀，合法位置为 $0\le i\le n$ ；select 的合法序号为 $1\le k\le\operatorname{rank}_1(n)$ ，不存在的序号统一返回 $\bot$ 。目标是在原始 $n$ 位之外只用 $o(n)$ 位索引，查询 $O(1)$ 。对零位有 $rank_0(i)=i-rank_1(i)$ ；给位补串建立同类 select 索引即可支持 select-zero，查询微块时按位取反即可，不必再存一份完整位串。两份低阶索引相加仍为 $o(n)$ 。

两级索引与微表

每 $\log^2 n$ 位设 superblock，存从串首到该处的全局 rank，每项 $O(\log n)$ 位，总计 $O(n/\log n)$ 位。每个 superblock 内再按约 $\frac12\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 采样位置，并对稠密/稀疏区间分别查表或显式存储。

直觉

位串本体已经用了最直接的 $n$ 位表示，索引只能把少量绝对计数放在稀疏边界，再用相对计数与共享微表填补块内细节。Rank 顺着位置累加这些层次，select 则按 1 的 occurrence 反向采样；两者需要不同但都为低阶的导航信息。

例子与边界

文本索引例子

用位串标记一组按顺序连接的非空文档起点，首位标为 $1$ 。 $rank_1(i)$ 数的是位置 $i$ 严格之前的起点；位置 $i<n$ 所属文档的零基编号应为 $rank_1(i+1)-1$ 。第 $k$ 个文档的起点则由 $select_1(k)$ 给出。这样无需为每个字符保存一个文档编号；若允许空文档共享起点，必须另存它们的重数。

空间与动态边界

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

RRR类别与偏移编码进一步改变位串本体：每块先存1数，再用组合秩指定类内排列。导航同时记录累计1数和可变负载起点；含 $m$ 个1的 $N$ 位串可把负载界到 $\log_2\binom Nm$ 加块数，类别、目录与微表另计。低阶冗余相对于 $N$ ，不能在极稀疏时自动改写成 $o(m)$ 。

推论与应用

rank/select 把位串分成大块、小块和微块，微块查询由四俄罗斯方法与字级并行预计算或字内操作完成；表大小必须是 o(n)，否则常数查询会牺牲简洁空间。

Select 的长短区间

对 rank 做二分可以找到第 $k$ 个 1，但需 $O(\log n)$ 时间。常数时间 select 改为按 1 的个数采样：每 $s$ 个 1 存一次绝对位置。若相邻样本跨越很长位区间，就显式存这 $s$ 个 1 的位置；若区间短，则再分小块采样并用微表。长区间总数受位串总长限制，短区间表型受块长度限制，配合各级采样参数，额外位数可压到 $o(n)$ 。

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

Rank 查询真正读取什么

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

共享微表还要包含各位型的所有块内偏移，因此其总大小为 $2^{(\log n)/2}\operatorname{polylog}n=o(n)$ 。即使把这份表计入单个位串的空间，仍满足低阶冗余要求。

参考资料

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

形式陈述 ​

目标与端点 ​

两级索引与微表 ​

文本索引例子 ​

空间与动态边界 ​

Select 的长短区间 ​

Rank 查询真正读取什么 ​