字符串模式匹配

快速概览

字符串模式匹配是序列比对、motif 搜索和数据库检索的算法基础。这一页从朴素匹配出发，介绍 KMP、Boyer-Moore 等经典算法的核心思想。

• 先理解朴素匹配为什么慢，再看 KMP 和 Boyer-Moore 如何优化会更顺。
• 这些算法的思想也体现在现代 BLAST 等工具的 seed-and-extend 策略中。

前置知识

• 算法与复杂度
• 动态规划基础
• 序列表示与索引

所属板块 基础与数学

对象层、坐标系统、coverage 与概率图模型的共同语言。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

是什么

字符串模式匹配（string pattern matching）的目标是：在一个长文本（text）中查找一个模式串（pattern）的所有出现位置。

给定：

• 文本串 $T = t_1t_2...t_n$
• 模式串 $P = p_1p_2...p_m$（$m \leq n$）

找到所有位置 $i$ 使得 $T[i...i+m-1] = P$。

要解决什么生物信息学问题

在生物信息学中，模式匹配是许多任务的基础：

• 序列比对：在参考基因组中定位 reads
• Motif 搜索：在序列中查找保守的转录因子结合位点
• 数据库检索：在序列数据库中搜索相似序列
• 引物设计：验证引物在基因组中的唯一性
• 限制性酶切位点识别：查找特定的酶切模式

1. 朴素匹配算法

朴素匹配（naive matching）是最直观的方法：对文本的每个位置，尝试匹配模式串。

算法思路

从文本位置 1 开始，逐字符比较模式串，失败则移动到下一个位置。

时间复杂度

最坏情况 $O(nm)$，平均情况 $O(n)$。

问题

每次失败后只移动一位，浪费了已匹配的信息。

示例

文本：ABABABC 模式：ABC

朴素匹配过程：

位置 1: ABABABC
        ABC    → 失败（第3个字符不匹配）
位置 2: ABABABC
         ABC   → 失败（第2个字符不匹配）
位置 3: ABABABC
          ABC  → 失败（第1个字符不匹配）
位置 4: ABABABC
           ABC → 成功！
位置 5: ABABABC
            ABC→ 失败（越界）

共进行了 10 次字符比较。注意每次失败后只移动一位，没有利用已匹配的信息。

为什么朴素算法慢

考虑最坏情况：

• 文本：AAAAAAAAAB
• 模式：AAAAB

每次匹配到第 4 个字符才失败，然后只移动一位，重复这个过程。复杂度接近 $O(nm)$。

2. KMP 算法

KMP（Knuth-Morris-Pratt）算法的核心思想：利用已匹配的信息，跳过不可能成功的位置。

核心创新

预处理模式串，计算每个位置的最长真前缀同时也是后缀的长度（LPS 数组）。

LPS 数组

Longest Proper Prefix which is also Suffix，记录模式串自身的重复结构。

时间复杂度

预处理 $O(m)$，匹配 $O(n)$，总体 $O(n + m)$。

空间复杂度

$O(m)$ 存储 LPS 数组。

LPS 数组计算

LPS[i] 表示模式串 $P[0...i]$ 的最长相等真前缀和后缀的长度。

对于模式串 ABABC：

i	P[i]	LPS[i]	解释
0	A	0	单字符无真前缀
1	B	0	AB 无相等前缀后缀
2	A	1	ABA 的 “A” 既是前缀也是后缀
3	B	2	ABAB 的 “AB” 既是前缀也是后缀
4	C	0	ABABC 无相等前缀后缀

示例

文本：ABABABC 模式：ABC

LPS 数组：[0, 0, 0]

匹配过程：

位置 1: ABABABC
        ABC    → 失败（C ≠ A），LPS=0，移动到位置2
位置 2: ABABABC
         ABC   → 失败（B ≠ A），LPS=0，移动到位置3
位置 3: ABABABC
          ABC  → 失败（A ≠ A 匹配，但 B ≠ B 不匹配），LPS=0，移动到位置4
位置 4: ABABABC
           ABC → 成功！

虽然这个例子中 KMP 没有明显优势，但在有重复结构的模式中，KMP 能大幅减少比较次数。

KMP 的优势

考虑模式 ABABABC 的 LPS：[0, 0, 1, 2, 3, 0, 0]

当匹配到位置 5 失败时，LPS[5]=3，说明前 3 个字符 ABA 已经匹配，可以直接跳到利用这个信息的位置。

在生物信息学中的应用

• Motif 搜索：快速查找保守的重复模式
• 序列数据库索引：加速数据库检索
• 引物特异性检查：验证引物的唯一匹配

3. Boyer-Moore 算法

Boyer-Moore 算法采用从右向左匹配，利用坏字符规则和好后缀规则实现大跨度跳跃。

核心创新

从右向左匹配，失败时根据字符出现位置和已匹配后缀决定跳过距离。

坏字符规则

根据不匹配字符在模式中的位置决定跳过距离。

好后缀规则

根据已匹配的后缀在模式中的其他出现位置决定跳过距离。

时间复杂度

最坏 $O(nm)$，平均 $O(n/m)$，实际中往往比 KMP 快。

坏字符规则

预处理坏字符表：记录每个字符在模式中最右出现的位置。

对于模式 ABCAB：

字符	最右位置
A	3
B	4
C	2
其他	-1

当匹配失败时，如果失败字符在模式中出现，跳过使该字符对齐；否则跳过整个模式长度。

示例

文本：ABABABC 模式：ABC

坏字符表：A:2, B:1, C:0, 其他:-1

匹配过程（从右向左）：

位置 1: ABABABC
        ABC    → 从右向左：C=C, B=B, A=A → 成功！
位置 2: ABABABC
         ABC   → 从右向左：C≠B，坏字符B在模式位置1，跳过 2-1=1 位
位置 3: ABABABC
          ABC  → 从右向左：C≠A，坏字符A在模式位置2，跳过 3-2=1 位
位置 4: ABABABC
           ABC → 从右向左：越界，结束

Boyer-Moore 的优势

当字符集较大且模式较长时，Boyer-Moore 的平均性能非常好，因为：

• 从右向左匹配更快发现不匹配
• 坏字符规则允许大跨度跳跃
• 在 DNA/RNA 序列（4 字符）中仍有优势

在生物信息学中的应用

• BLAST 的启发式：seed-and-extend 策略借鉴了 Boyer-Moore 的思想
• 快速序列搜索：在大规模数据库中快速定位候选匹配
• k-mer 索引：结合 k-mer 和跳跃策略加速搜索

4. Rabin-Karp 算法

Rabin-Karp 使用哈希将字符串匹配转化为整数比较。

核心思想

计算文本窗口和模式串的哈希值，相等则进行精确比较。

滚动哈希

利用前一个窗口的哈希值快速计算下一个窗口的哈希值。

时间复杂度

平均 $O(n + m)$，最坏 $O(nm)$（哈希冲突时）。

优势

容易扩展到多模式匹配。

滚动哈希

对于长度为 $m$ 的窗口，哈希值计算：

$$H = \sum_\{i=0\}^\{m-1\} s_i \cdot d^\{m-1-i\} \mod q$$

滚动更新：

$$H_\{new\} = (H_\{old\} - s_\{old\} \cdot d^\{m-1\}) \cdot d + s_\{new\} \mod q$$

其中 $d$ 是基数（如 4 对应 DNA），$q$ 是大质数。

示例

文本：ABABABC 模式：ABC

使用简单的哈希（ASCII 码和）：

模式 ABC 哈希：65+66+67 = 198

窗口 1-3 (ABA)：65+66+65 = 196 ≠ 198 窗口 2-4 (BAB)：66+65+66 = 197 ≠ 198 窗口 3-5 (ABA)：65+66+65 = 196 ≠ 198 窗口 4-6 (ABC)：65+66+67 = 198 = 模式哈希，精确比较：成功！

在生物信息学中的应用

• 多模式搜索：同时搜索多个 motif 或引物
• 序列相似性初筛：快速过滤不相似的序列
• k-mer 计数：高效统计 k-mer 频率

5. 算法比较

算法	预处理	匹配时间	最坏情况	适用场景
朴素	$O(1)$	$O(nm)$	$O(nm)$	短模式，简单场景
KMP	$O(m)$	$O(n)$	$O(n)$	模式有重复结构
Boyer-Moore	$O(m +	\Sigma	)$	平均 $O(n/m)$
Rabin-Karp	$O(m)$	平均 $O(n)$	$O(nm)$	多模式匹配

6. 与生物信息学工具的连接

BLAST 的 seed-and-extend

BLAST 并不直接使用上述算法，但借鉴了思想：

1. Seed：用 k-mer 作为种子快速定位候选位置（类似 Boyer-Moore 的跳跃）
2. Extend：在候选位置进行局部扩展和精确比对（类似 KMP 的精确匹配）

现代序列索引

• FM-index：基于 BWT 的后向搜索，本质上是高效的模式匹配
• Minimizer sketch：用采样代替完整匹配，加速大规模搜索
• k-mer hash table：类似 Rabin-Karp 的哈希思想

常见误区

• KMP 总是最优的：
• 不是。在实际应用中：
• Boyer-Moore 在长模式和自然文本中往往更快
• 现代工具更多使用索引结构（如 FM-index）而非经典匹配算法
• 选择算法要考虑字符集大小、模式长度、数据特征
• 模式匹配就是序列比对：

与其他算法的连接

• 动态规划：序列比对在模式匹配基础上加入 gap 和打分
• 后缀数组/树：更高级的字符串索引结构，支持更复杂的查询
• 哈希技术：Rabin-Karp 的哈希思想在 k-mer 计数、sketching 中广泛应用

参考资料

• Introduction to Algorithms (CLRS), 第 32 章
• Dan Gusfield, Algorithms on Strings, Trees, and Sequences
• Pattern Matching Algorithms (各种教材和论文)

序列表示与索引

后缀数组、FM-index 等高级索引结构是模式匹配的延伸。

延伸阅读

近似模式匹配

在允许错配的情况下进行模式匹配，更贴近真实生物信息学场景。

延伸阅读

序列比对

序列比对在模式匹配基础上引入 gap 和打分系统。

延伸阅读

BLAST

BLAST 的 seed-and-extend 策略借鉴了 Boyer-Moore 等匹配算法的思想。

延伸阅读

Motif 寻找

Motif 搜索是模式匹配在转录因子结合位点发现中的具体应用。

延伸阅读