FM-index

模式的所有出现对应后缀数组中的一个连续区间。BWT 的 first–last 对应让“在模式左边再接一个字符”变成两次 rank 更新，因此查询可以从模式末尾向前逐字符收紧区间；采样 SA/ISA 则为区间中的行补回文本坐标，形成 count、locate 与 extract 的不同成本。

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

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

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

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

locate 为什么还要采样 ​

Count 只返回 suffix-array 区间；要得到每一行对应的文本位置，需要 suffix array 值。选整数采样步长 $1\le s\le n$，保存所有 $SA[i]\equiv 0(\mathrm{mod}s)$ 的行及其 SA 值。这里按文本位置采样，不是按每第 $s$ 个后缀行采样。LF 映射满足

以标记位向量指出哪些行有样本，并用该标记上的 rank 定位紧凑样本数组。从待定位行反复做 LF，至多 $s-1$ 步命中样本，再把步数加回并模 $n$ 即可恢复位置。令 $t_{LF}\ge 1$ 包括读取 $L[i]$、字符 rank、$C$ 访问与样本查询，则定位一个 occurrence 的时间为

样本值占 $O(\lceil n/s\rceil \log (n+1))$ bits，另计样本标记索引。稠密标记可用 $n+o(n)$ 位，稀疏压缩标记则有不同的空间式；这部分不能藏进样本值的界里。报告全部 occ 个位置的定位成本为

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

extract 与自索引含义 ​

提取合法区间 $0\le p\le p+\ell \le n$ 时，空区间直接返回；非空区间通常再按步长 $s_{\mathrm{ISA}}$ 采样 inverse suffix array。固定 $1\le s_{\mathrm{ISA}}\le n$，先从不超过 $p$ 的最近采样位置 $q=s_{\mathrm{ISA}}\lfloor p/s_{\mathrm{ISA}}\rfloor$ 取得 BWT 行，再用 $\mathrm{\Psi }={\mathrm{LF}}^{-1}$ 或等价 select 操作逐字符向前，时间包含至多一个采样间隔和输出长度：

“自索引”表示原文可以由索引恢复，因此最终存储可不另放一份未经压缩的 $T$；它不表示任意文本位置都免费 $O(1)$ 随机访问。若用上述采样取得快速 locate 与 extract，就须把两张样本表及各自间隔一并报告；仅能逐步恢复整个原文的表示，并不自动具有这些访问时间。

空间界的条件 ​

空间界依赖具体的 BWT 编码。一个明确例子是 Alphabet-Friendly FM-index：固定字母表大小 $\sigma \ge 2$ 和常数 $0<\alpha <1$，对整数 $0\le k\le \alpha {\log }_{\sigma }n$，通过上下文分块与压缩 wavelet 结构，可把 BWT 导航部分保存在

位内，并支持常数时间字符 rank。这里 $H_k$ 使用该定理的有限文本、后继上下文约定；普通全局零阶压缩只保证相应的 $H_0$ 界。上面的任意 SA/ISA 采样方案还须另加样本值、标记索引和字母表元数据，尤其稠密样本标记的 $n$ 位不能计作 $o(n)$。要取得完整自索引的同阶熵空间，须同时采用定理中的稀疏采样与标记表示。

高度可压缩文本会让主体显著小于 $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}})$。