图解BWT FM-Index算法
FM-Index(Full-text Minute Index)是一种用于高效搜索和压缩全文数据的索引结构, 广泛应用于生物信息学和文本检索领域.
它基于 Burrows-Wheeler Transform (BWT) 和辅助数据结构, 能够在压缩存储的同时支持快速的子串搜索, 计数和定位操作.
算法核心
LF 变换是 BWT 算法的核心. FM-Index 使用巧妙的办法来实现 LF 变换.
BWM(Burrows Wheeler Matrix)
BWM 是由源字符串不断循环移位产生的. 可以参考我之前的博客: 图解 BWT(Burrows-Wheeler Transform) 算法.
以"mississippi$"为例, 它的 BWM 矩阵如图所示:
FM-Index 查询字符串
示例 1: 查询字符串"ssi"
在 BWT 字符串中, 查询是倒序进行的. 也就是匹配是从字符'i'开始
-
第一步: 在 F 行找出所有的以
'i'开头的行, 如图所有, 有 4 行. 我们知道这个 BW 矩阵是由S的循环移位产生的, 因此L行的字符出现在对应F行的字符的左边. 具体来说就是这四个'i'与其左侧元素构成的字符串为:- p 0 i 0 \textrm{p}_0\textrm{i}_0 p0i0
- s 0 i 1 \textrm{s}_0\textrm{i}_1 s0i1
- s 1 i 2 \textrm{s}_1\textrm{i}_2 s1i2
- m 0 i 3 \textrm{m}_0\textrm{i}_3 m0i