Rank 与 Select 查询

定义 ​

作为简洁数据结构公理库简洁数据结构Succinct data structure以接近对象族信息论下界的 bit 数保存对象，同时直接支持查询。的基础接口，对位串 (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)) 因子。

接口与边界 ​

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

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

Rank/select 是 wavelet tree 与 FM-index 的导航原语。Select 不是数组中选择第 (k) 小，rank 也不是比较排序里的秩；名称相邻，输入与返回语义不同。

参考资料

• Guy Jacobson, PhD thesis, 1989.
• Clark, Munro, “Efficient Suffix Trees on Secondary Storage,” SODA 1996.
• Raman, Raman, Rao, 2007.