FM-index

文本、端点与核心存储 ​

设文本

$$T[0..n-1]\in {\mathrm{\Sigma }}^{n-1}\mathrm{\$}$$

以唯一哨兵 $\mathrm{\$}$ 结束，且 $\mathrm{\$}$ 按字典序小于其他字符。令 $L=\mathrm{BWT}(T)$。FM-index 的核心不保存 suffix array 全表，而保存：

• $C[c]$：文本中严格小于字符 $c$ 的字符数；
• ${\mathrm{rank}}_c(L,i)$：半开前缀 $L[0..i)$ 中 $c$ 的出现次数；
• 支持上述 rank 的压缩位向量或 Wavelet Tree公理库Wavelet Treewavelet tree · 小波树递归划分有序字母表，并用节点位向量映射序列位置以支持 access、rank、select 与区间选择。。

所有公式采用半开端点。若把 rank 改成闭前缀，$C$ 和区间更新必须一起调整；只改一个端点会造成系统性的 off-by-one。

backward search 与 count ​

后缀数组中，以模式串 $P$ 为前缀的后缀形成连续区间 $[l,r)$。初始空模式对应 $[0,n)$。从 $P$ 的末字符向前处理，若当前区间表示后缀 $Q$，向左加入 $c$ 后

$$l^{\prime }=C[c]+{\mathrm{rank}}_c(L,l),r^{\prime }=C[c]+{\mathrm{rank}}_c(L,r).$$

first–last correspondence公理库LF 映射与反向搜索LF mapping · FM-index backward search借 BWT 的同字符稳定对应，把模式从右向左扩展为后缀数组区间。保证新区间正好对应前缀 $cQ$。若 $l^{\prime }\ge r^{\prime }$，模式不存在；处理完全部 $|P|$ 个字符后，出现次数为 $r-l$。

若一次 rank 花 $t_{\mathrm{rank}}$，count 时间为

$$O(|P|t_{\mathrm{rank}}),$$

与输出出现数无关。使用平衡 wavelet tree 时 $t_{\mathrm{rank}}=O(\log \sigma )$；小字母表的多位向量实现可达到常数 rank。必须让时间界与所选字母表表示配套。

具体例子：在 banana$ 中搜索 ana ​

$T=\mathtt{\text{banana\$}}$ 的 BWT 为

$$L=\mathtt{\text{annb\$aa}}.$$

字符累计数满足 $C[\mathtt{\text{a}}]=1,C[\mathtt{\text{b}}]=4,C[\mathtt{\text{n}}]=5$。从 $[0,7)$ 开始反向处理：

$$\begin{array}{rl}\mathtt{\text{a}}& :[1,4),\\ \mathtt{\text{n}}& :[5,7),\\ \mathtt{\text{a}}& :[2,4).\end{array}$$

最终区间长度为 $2$，所以 ana 出现两次。这个过程只访问 BWT 的 rank，没有扫描原文，也没有保存完整 suffix array。

locate 为什么还要采样 ​

Count 只返回 suffix-array 区间；要得到每一行对应的文本位置，需要 suffix array 值。选采样步长 $s\ge 1$，保存满足某个固定模条件的 SA 行及其 SA 值。LF 映射满足

$$\mathrm{SA}[\mathrm{LF}(i)]=\mathrm{SA}[i]-1(\mathrm{mod}n).$$

从待定位行反复做 LF，至多 $s$ 步命中采样行，再把步数加回即可恢复位置。因此定位一个 occurrence 的时间为

$$O(s{t}_{\mathrm{rank}}),$$

采样空间为 $O((n/s)\log n)$ bits；报告全部 occ 个位置还必须加上输出成本

$$O(\mathrm{occ}\cdot s{t}_{\mathrm{rank}}).$$

调大 $s$ 节省空间却减慢 locate。不能把 count 的 $O(|P|t_{\mathrm{rank}})$ 直接写成所有查询操作的时间。

extract 与自索引含义 ​

提取 $T[p..p+\ell )$ 通常再按步长 $s_{\mathrm{ISA}}$ 采样 inverse suffix array。先从离 $p$ 最近的采样位置取得 BWT 行，再用 $\mathrm{\Psi }={\mathrm{LF}}^{-1}$ 或等价 select 操作逐字符向前，时间包含至多一个采样间隔和输出长度：

$$O((s_{\mathrm{ISA}}+\ell )t_{\mathrm{step}}).$$

“自索引”表示原文可以由索引恢复，因此最终存储可不另放一份未经压缩的 $T$；它不表示任意文本位置都免费 $O(1)$ 随机访问。Locate 和 extract 的采样是自索引接口不可省略的空间—时间参数。

空间界的条件 ​

配合压缩 rank 结构，经典 FM-index 可达到形如

$$n{H}_k(T)+o(n\log \sigma )$$

bits 的 BWT 主体空间，再加 SA/ISA 采样和字母表元数据。这里 $H_k$ 是选定阶数的经验熵，$k$ 必须处在编码定理允许的范围；不同实现可能给 $n{H}_0(T)+o(n\log \sigma )$、run-length BWT 或其他界。不能同时引用一个版本的熵空间、另一个版本的 rank 时间，却省略实现条件。

高度可压缩文本会让主体显著小于 $n\log \sigma$，但随机文本的经验熵接近该上限。构建阶段常需 suffix array、BWT 工作区和外部排序，峰值内存可以远高于最终索引；最终空间界不是构建内存保证。

失败边界与近邻概念 ​

单次字符串匹配公理库字符串匹配String matching · Exact pattern matching在文本中定位模式串全部出现位置的问题。可用 KMP 在 $O(n+|P|)$ 扫描文本；FM-index 的价值在于固定文本上的大量模式查询和压缩存储。若只查询一次，建立索引未必划算。

哨兵必须唯一，字符序固定，rank 端点从建表到 backward search 保持一致。动态插入文本会整体改变 BWT 行次序，静态 FM-index 不能局部套用普通数组插入。近似匹配、通配符和正则查询还会分裂为许多区间，复杂度不再只是 $O(|P|t_{\mathrm{rank}})$。

参考资料

• Paolo Ferragina and Giovanni Manzini, “Opportunistic Data Structures with Applications,” FOCS, 2000.
• Paolo Ferragina and Giovanni Manzini, “Indexing Compressed Text,” Journal of the ACM 52(4), 2005, 552–581.
• Veli Mäkinen et al., Genome-Scale Algorithm Design, Cambridge University Press, 2015, compressed full-text indexes chapter.