LF 映射与反向搜索

First–Last 对应 ​

令 $L$ 是BWT公理库Burrows–Wheeler 变换Burrows-Wheeler transform · BWT对带唯一终止符文本的循环移位排序，并取最后一列形成可逆排列。 最后一列，$F$ 是排序后第一列。$C[c]$ 为文本中严格小于字符 $c$ 的字符数，Occ$(c,i)$ 为 $L[0..i)$ 中 $c$ 的出现数。相同字符在 $F,L$ 中按其后缀次序稳定对应，因此对行 $i$，

$$\mathrm{LF}(i)=C[L_i]+\mathrm{Occ}(L_i,i).$$

本文全部区间半开、Occ 不含位置 $i$。

反向搜索 ​

若后缀数组区间 $[l,r)$ 中的后缀都以前缀 $P$ 开头，则在左侧加入字符 $c$ 后，新区间是

$$[C[c]+\mathrm{Occ}(c,l),C[c]+\mathrm{Occ}(c,r)).$$

从空模式的全区间开始，按模式字符从右向左迭代；区间长度最终就是出现次数。每步做两次 rank，时间 $O(|P|)$（假设常数 rank）。

banana$ 例子 ​

在文本 banana$ 的 BWT 上搜索 ana：先由字符 a 得到所有 a 开头后缀的区间，再用 n 收缩为 na，最后用 a 收缩为 ana。某一步左右端相等即为空区间，之后模式不存在；不能继续把负长度或闭区间端点代入。

边界与逆映射 ​

字符表次序决定 $C$，终止符必须唯一且最小。同一字符的第 $k$ 次出现必须稳定对应，否则 LF 不再沿文本向前一位。LF 与 $\mathrm{\Psi }$ 是方向相反的相关映射，不应混写公式。正文只给 count 区间；定位原文位置还需后缀数组采样及 LF 步进成本。

公式证明与定位 ​

$F$ 中字符 $c$ 占据从 $C[c]$ 开始的连续区间。$L[i]=c$ 若是 $L$ 中第 $k$ 次出现（按半开 rank，$k=Occ(c,i)$），first–last property 说明它对应 $F$ 中第 $k$ 个 $c$，位置正是 $C[c]+k$。反向区间公式只是把区间内所有 $c$ 出现的编号范围映到这段 $F$ 区间。

FM-index 每隔 $s$ 行存一次 suffix-array 值。定位某匹配行时反复 LF，直到命中样本，并按步数修正文本位置，最坏需 $O(s)$ 次 rank；采样越密，定位快但空间更大。Count、locate 与 extract 因而有不同成本。

区间收缩的数值核对 ​

假设当前区间 $[l,r)=[2,6)$，要向左扩展字符 a，且 $C[a]=1$、$Occ(a,2)=1$、$Occ(a,6)=3$。新区间是 $[2,4)$，长度 2 正好等于原区间对应 BWT 片段中 a 的出现数 $3-1$。这个长度守恒是排查端点错误最直接的断言。

逐字符搜索只得到 suffix-array 行区间；若要输出文本位置，需对每一行沿 LF 走到最近采样行。一个匹配很多的模式会产生 $occ$ 条定位路径，所以成本应写成 $O(|P|+occ\cdot s)$ 的朴素上界，而非把 count 的 $O(|P|)$ 误报为完整检索成本。

参考资料

• Paolo Ferragina, Giovanni Manzini, Opportunistic Data Structures with Applications, FOCS, 2000.
• Paolo Ferragina, Giovanni Manzini, Indexing Compressed Text, JACM, 2005.