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$ 。

位串 $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)$ 。查询把 superblock 基数、block 偏移和微块局部计数相加，在 word-RAM 与共享表计费约定下为常数时间。

查询 $\operatorname{rank}_1(5)$ 时，目录最终读取微块前五位的局部计数，得到 3。概念上仍等于上面的前缀数组，但不为每个位置存一个 $\Theta(\log n)$ -bit 整数；后者会使用 $\Theta(n\log n)$ bit，不再简洁。

select 的长短间隔

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

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

直觉

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

例子与边界

接口与边界

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

动态插入一位会改变其后许多 rank 值与 select 位置，静态目录不能局部照搬。常数时间也依赖字长 $w=\Theta(\log n)$ 、固定位串和共享小表不按每个实例重复计费。

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 的长短间隔

接口与边界