Rank 与 Select 查询 | Codeboy's Blog

形式陈述

定义

作为简洁数据结构的基础接口，对由 0/1 组成的有限序列（位串） $B[0..n)$ ，

\operatorname{rank}_b(i) =|\{j:0\le j<i,\ B[j]=b\}|,

采用半开前缀； $\operatorname{select}_b(k)$ 返回第 $k$ 个 $b$ 的零基下标， $k$ 从 1 起，不存在则返回 $\bot$ 。于是 $B[i]=1$ 当且仅当 $\operatorname{rank}_1(i+1)-\operatorname{rank}_1(i)=1$ 。

Rank 的合法参数为 $0\le i\le n$ ，包括表示整个串的 $i=n$ ；select 的有效出现次数为 $1\le k\le\operatorname{rank}_b(n)$ 。这些查询即使在线性扫描实现中也有同样含义，简洁索引只是同时追求低空间和快速查询的一种实现要求，不是接口定义的前提。

位串 $101100$ 的 rank-one 前缀为

(0,1,1,2,3,3,3).

因此 $\operatorname{rank}_1(4)=3$ ，第三个 1 位于零基位置 3。若把 rank 改成含端点 $[0,i]$ ，同一查询会错一位，库级约定不能隐含。

rank 的分层索引

把位串分成长度 $L=(\log n)^2$ 的 superblock，再分成长度 $\ell=\tfrac12\log n$ 的 block。每个 superblock 保存全局 1 数，每个 block 保存相对本 superblock 起点的计数，剩余微块由共享位型表回答。

两级目录分别占

O\!\left(\frac{n}{L}\log n\right) \quad\text{与}\quad O\!\left(\frac{n}{\ell}\log L\right)

bit，均为 $o(n)$ 。取 $\ell=\lfloor\tfrac12\log_2n\rfloor$ ，全部微块位型只有 $2^\ell\le\sqrt n$ 种；为每种位型保存所有前缀的计数，表大小为 $O(2^\ell\ell\log(\ell+1))=o(n)$ bit。因此即使把完整表计入一个实例，辅助空间仍为 $o(n)$ 。在字长 $w=\Theta(\log n)$ 、支持常数次字操作与查表的 word-RAM 上，查询把两级目录与局部计数相加即可在常数时间完成。小规模输入可直接保存答案，不影响渐近界。

查询 $\operatorname{rank}_1(5)$ 时，先由目录计入位置 $5$ 所在微块之前的 $1$ ，再查询该微块内截至位置 $5$ 的前缀，两部分合计为 $3$ 。它不要求前五位都在同一微块，也不为每个位置存一个 $\Theta(\log n)$ -bit 整数；后者会使用 $\Theta(n\log n)$ bit，不再简洁。

select 的长短间隔

Select 可每隔固定数量的 1 采样一个绝对位置，再按采样间隔的跨度分类。跨越很长位段的间隔数量很少，可显式存其中 1 的位置；短间隔落在少量机器字内，由更细采样或微块表恢复第 $k$ 个 1。

当原位串改由RRR类内偏移保存时，索引要读取的短位窗口可先从少量压缩块恢复。理论微表与实际组合逆秩具有不同代价；若参考实现用rank二分select，应保留二分增加的对数因子，不能仅凭输出接口相同就宣称常数时间。

这类“长间隔少、短间隔可查表”的计数负责把 select 的辅助空间压到 $o(n)$ 。它不是对 rank 做普通二分；若只用二分调用 rank，时间会多出 $\Theta(\log n)$ 因子。

直觉

Rank 把位位置映到此前出现次数，select 则沿相反方向把 occurrence 编号映回位置。分层目录只为稀疏边界存绝对计数，微块用共享表恢复局部答案；辅助索引因此可以是 $o(n)$ 位，而原位串仍保留完整信息。

它们不是整个定义域上的互逆函数：若连续几个位置都是 $0$ ， $\operatorname{rank}_1$ 在这些位置不变，已经丢掉了位置差异。准确的互逆关系要限定到出现点：若 $p=\operatorname{select}_b(k)$ ，则 $\operatorname{rank}_b(p)=k-1$ 且 $\operatorname{rank}_b(p+1)=k$ 。半开前缀解释了为什么必须在后一式把位置加一。

例子与边界

接口与边界

对 $B=101100$ ，查询第三个 $1$ 得到 $p=3$ ，而此前的前缀 $B[0..3)=101$ 只有两个 $1$ 。区间 $[2,5)$ 中 $1$ 的个数可用 $\operatorname{rank}_1(5)-\operatorname{rank}_1(2)=3-1=2$ 求得。若要求“从位置 $2$ 起的第二个 $1$ ”，先取得起点之前的计数 $1$ ，再调用 $\operatorname{select}_1(1+2)=3$ ；若结果落到区间右端之外，就说明指定区间内没有足够出现次数。这正是压缩索引把局部查询换算为全局编号的步骤。

上述静态简洁位向量实现把原位串与目录合计控制在 $n+o(n)$ bit；这不是“零辅助空间”。Access 可由两次 rank 得到，但常数因子与可更新性并不等价。第 $k$ 个 1 不存在时必须返回 $\bot$ ，否则上层 FM-index 可能把空区间误当成位置 0。

动态插入一位会改变其后许多 rank 值与 select 位置，静态目录不能局部照搬。常数查询时间依赖上述字长和字操作模型，并不免除预处理成本；微块表可以共享，也可以按前面的大小计入单实例空间。

Select 不是数组中选择第 $k$ 小，rank 也不是比较排序里的秩；名称相邻，输入与返回语义不同。

推论与应用

Rank/select 是压缩索引与简洁表示的共同导航原语。Wavelet Tree 用每层位向量的 rank 把查询映到子序列；FM-index 用 BWT 上的 rank 推进 backward search；Elias–Fano 编码借助 select 定位高位一元码。平衡括号树表示则在括号位串上组合 rank/select 与匹配操作恢复树导航。

参考资料

Guy Jacobson, Succinct Static Data Structures, PhD thesis, Carnegie Mellon University, 1989.
David R. Clark and J. Ian Munro, “Efficient Suffix Trees on Secondary Storage,” in Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’96), 1996, pp. 383–391.
Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao, “Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets,” ACM Transactions on Algorithms 3(4), 2007, Article 43.

形式陈述 ​

定义 ​

rank 的分层索引 ​

select 的长短间隔 ​

接口与边界 ​

反向链接

形式陈述

定义

rank 的分层索引

select 的长短间隔

接口与边界