好，这个我给你讲到真正听懂为止 👇
FM-index 其实没那么神秘。

一句话理解

FM-index 是一种“压缩了的全文索引”，可以在不解压文本的情况下，快速查找任意子串。

它是：

• 基于 Michael Burrows 和 David Wheeler 提出的 BWT
• 再由 Paolo Ferragina 和 Giovanni Manzini 设计成可搜索结构

所以叫 FM-index（Ferragina–Manzini）。

先用一个比喻理解

假设：

• 你有一本 30 亿字符的书（人类基因组）
• 你想查找一个 150bp 的 read

普通方法：

从头扫一遍书

太慢。

FM-index 方法：

先把书变形（BWT）
建立一个压缩索引
以后查找只在索引上操作

而且：

查找时间只和 read 长度有关
不和基因组大小有关

这就是它恐怖的地方。

二、FM-index 背后的三块核心思想

理解它只需要三步：

1️⃣ BWT（Burrows–Wheeler Transform）

BWT 做的事情是：

把字符串的所有“旋转版本”排序
然后取最后一列

举个小例子：

banana$

排序所有旋转：

$banana
a$banan
ana$ban
anana$b
banana$
na$bana
nana$ba

取最后一列：

annb$aa

这就是 BWT 结果。

2️⃣ 神奇性质：可逆 + 可搜索

BWT 有两个关键特性：

✔ 可逆（能还原原文）

✔ 相同字符会聚在一起（利于压缩）

比如：

aaaaa
bbbb
cccc

压缩效果很好。

3️⃣ Backward Search（核心魔法）

FM-index 不正向找字符串。

它：

从模式串的最后一个字符开始反向查找。

比如找：

ana

它做的是：

1. 先找所有 'a'
2. 再找前面是 'n' 的
3. 再找前面是 'a' 的

一步一步缩小区间。

关键公式：

new_range = C[c] + Occ(c, range)

不用扫描原文本。

只操作：

• 字符计数表 C
• 前缀出现次数表 Occ

三、它为什么快？

假设：

• 基因组 3GB
• read 150bp

普通搜索：

O(n × m)

FM-index：

O(m)

因为：

每次只是区间缩小，不扫描文本

四、为什么 BWA 用它？

像 BWA 这种比对工具需要：

• 存整个人类基因组
• 内存尽量小
• 快速查找子串

FM-index：

✔ 内存接近文本大小
✔ 搜索极快
✔ 不用存所有 k-mer

比 hash 表更省空间。

五、和 Hash 表对比

你最近在研究 k-mer 和 hash，对比一下：

FM-index 相当于：

“把整本书当作一个整体索引”

而不是：

“拆成无数 k-mer 再存 hash 表”

六、用一句最直白的话总结

FM-index 是：

一个基于 BWT 的压缩全文索引
可以在压缩状态下快速查找任意子串
搜索复杂度只和模式串长度有关

七、如果你愿意更深入

我可以继续讲：

• LF-mapping 是什么
• C 表和 Occ 表怎么实现
• Rank / Select 位运算实现
• 为什么空间接近 nH_k（信息论下界）
• 为什么 Kraken 不用 FM-index
• FM-index 和 suffix array 的关系

你想往哪个方向深挖？