Boyer-Moore算法

快速概览

Boyer-Moore算法通过从右向左匹配和智能跳跃规则，在实际应用中往往是最快的字符串匹配算法，平均时间复杂度接近O(n/m)。

• 核心思想：从右向左匹配，利用失配信息实现大跨度跳跃
• Bad Character Rule：根据失配字符决定跳跃距离
• Good Suffix Rule：利用已匹配后缀信息优化跳跃
• 实际性能：最坏O(nm)，平均接近O(n/m)，实践中通常最快

前置知识

所属板块 核心方法

索引、比对、组装与概率模型构成的核心算法主轴。

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

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

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

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

算法历史

Boyer-Moore算法由 Robert S. Boyer 和 J Strother Moore 于1977年发表，是第一个在实践中实现亚线性平均时间复杂度的字符串匹配算法。

发表背景：

• 发表于 “A fast string searching algorithm”（Communications of the ACM）
• 与 KMP 同年发表，但采用了完全不同的优化策略
• 在大型字母表（如英文文本）上表现尤为出色

核心创新：

• 从右向左扫描，与直觉相反但效率更高
• 双重跳跃规则（bad character + good suffix）
• 利用字母表信息实现远超模式串长度的跳跃

问题描述

Boyer-Moore解决与KMP相同的精确字符串匹配问题：

给定文本 $T$（长度 $n$）和模式串 $P$（长度 $m$），在 $T$ 中找出所有 $P$ 的出现位置。

但采用了完全不同的策略：

• KMP：从左向右，利用已匹配前缀信息
• Boyer-Moore：从右向左，利用失配字符信息

关键洞察：如果模式串末尾字符都不匹配，中间字符必然也不匹配，可以直接跳过整个模式串长度。

为什么重要

在生物信息学中，Boyer-Moore的价值体现在：

• 实际性能：在实践中往往比KMP更快，特别是在模式串较长时
• 启发式思想：展示了如何利用”坏字符”和”好后缀”信息进行优化
• 工具影响：现代read mapper的seed-and-extend策略中，跳跃思想有类似之处

虽然现代生物信息学工具主要使用基于索引的方法，但Boyer-Moore的核心思想——利用失配信息进行跳跃——在很多启发式算法中都有体现。

核心思想

从右向左匹配

考虑在文本 T 中匹配模式串 P = "EXAMPLE"：

T: ... H E R E I S A N E X A M P L E ...
P:             E X A M P L E
                         ^ 从右向左比较

Boyer-Moore先比较模式串的最后一个字符 E，如果失配，就根据规则决定跳跃距离。

为什么从右向左

直觉是：如果模式串末尾字符都不匹配，那么整个模式串肯定不匹配，可以直接跳过很多位置。

两个跳跃规则

Boyer-Moore使用两个独立的跳跃规则，取较大的跳跃距离：

1. Bad Character Rule：根据失配字符在模式串中的位置
2. Good Suffix Rule：根据已匹配的后缀信息

Bad Character Rule

bad character

文本中导致失配的字符，该字符不在模式串的对应位置。

跳跃策略

将模式串向右移动，使得模式串中最近的该字符与文本中的bad character对齐。

最坏情况

如果bad character不在模式串中，则跳过整个模式串长度。

算法描述

当在位置 j 失配，且文本字符 T[i] 不等于 P[j] 时：

1. 在模式串 P[0:j] 中查找字符 T[i]
2. 如果找到，将模式串向右移动，使得 T[i] 与模式串中最右边的该字符对齐
3. 如果没找到，将模式串向右移动 j+1 位（跳过整个模式串）

示例

T: ... A B C D E F G ...
P:     X Y Z D E F
               ^ 失配，T[i] = 'G'

字符 'G' 不在模式串 P 中，因此将模式串向右移动整个长度：

T: ... A B C D E F G ...
P:             X Y Z D E F

预处理：bad character table

算法1：构建bad character table

输入：模式串 P = p_0p_1...p_\{m-1\}，字母表 Σ
输出：bad character table BC[|Σ| × m]

1. 初始化 BC 为全 -1
2. for j = 0 to m-1:
   a. BC[P[j]][j] = j  // 记录每个字符在模式串中的最右位置
3. return BC

时间复杂度：$O(m + |\Sigma|)$

空间复杂度：$O(|\Sigma| \times m)$

Good Suffix Rule

good suffix

模式串中已经成功匹配的后缀部分。

跳跃策略

寻找模式串中是否存在与good suffix匹配的子串，将模式串移动到该位置。

两种情况

模式串内部有匹配子串，或模式串前缀与good suffix后缀匹配。

算法描述

当模式串的后缀 P[j+1:m] 与文本匹配，但在位置 j 失配时：

1. 在模式串中查找是否存在另一个子串等于 P[j+1:m]
2. 如果找到，将模式串移动到该位置
3. 如果没找到，查找模式串的前缀是否等于 P[j+1:m] 的后缀
4. 根据匹配情况决定跳跃距离

示例

T: ... A B C D E F G H ...
P:     X Y Z D E F
             ^^^^^ 匹配
           ^ 失配

已匹配后缀为 "DEF"，在模式串中查找是否有其他 "DEF"：

• 如果没有，查找前缀是否与 "DEF" 的后缀匹配
• 根据匹配情况决定跳跃

预处理：good suffix table

算法2：构建good suffix table

输入：模式串 P = p_0p_1...p_\{m-1\}
输出：good suffix table GS[0:m]

1. 初始化 GS 为全 m
2. // 情况1：模式串内部有匹配子串
3. for j = 0 to m-1:
   a. 寻找最大的 k < j，使得 P[k+1:j+1] = P[m-j:m]
   b. 如果找到，GS[j] = m - k - 1
4. // 情况2：前缀与后缀匹配
5. for j = 0 to m-1:
   a. 寻找最大的 k，使得 P[0:k] = P[m-k:m]
   b. 对于所有 j >= m - k - 1，GS[j] = m - k - 1
6. return GS

时间复杂度：$O(m)$

空间复杂度：$O(m)$

Boyer-Moore匹配算法

算法3：Boyer-Moore字符串匹配

输入：文本 T = t_0t_1...t_\{n-1\}，模式串 P = p_0p_1...p_\{m-1\}
输出：所有匹配位置

1. 预处理：构建bad character table BC和good suffix table GS
2. i = 0  // 文本中的当前对齐位置
3. while i <= n - m:
   a. j = m - 1  // 从模式串末尾开始比较
   b. while j >= 0 and P[j] == T[i + j]:
      j = j - 1
   c. if j < 0:
      // 找到完整匹配
      输出匹配位置 i
      i = i + GS[0]  // 使用good suffix rule跳跃
   d. else:
      // 失配，计算跳跃距离
      bad_char_shift = j - BC[T[i + j]][j]
      good_suffix_shift = GS[j]
      i = i + max(bad_char_shift, good_suffix_shift)

时间复杂度：最坏情况 $O(nm)$，平均情况 $O(n/m)$ 到 $O(n)$

空间复杂度：$O(|\Sigma| \times m)$

复杂度分析

理论复杂度

阶段	时间复杂度	空间复杂度
预处理（Bad Character）	$O(m +	\Sigma
预处理（Good Suffix）	$O(m)$	$O(m)$
匹配（最坏情况）	$O(nm)$	$O(1)$ 额外
匹配（平均情况）	$O(n/m)$	$O(1)$ 额外
匹配（最好情况）	$O(n/m)$	$O(1)$ 额外

为什么实际中很快

Boyer-Moore 在实践中通常是最快的字符串匹配算法：

1. 从右向左匹配：大部分情况下末尾字符就会失配，避免检查模式串其余部分
2. 大跨度跳跃：Bad Character Rule 在大型字母表上经常能跳过整个模式串长度
3. 双重保险：两个规则取最大值，确保每次跳跃尽可能大
4. 字母表效应：蛋白质序列（20字符）比DNA（4字符）更有利于跳跃

实际表现：

• 英文文本（256字符）：通常检查 $< n/10$ 个字符
• DNA序列（4字符）：性能不如英文，但仍优于KMP
• 蛋白质序列（20字符）：性能介于两者之间

示例

在文本 T = "HERE_IS_A_SIMPLE_EXAMPLE" 中匹配 P = "EXAMPLE"：

T: H E R E _ I S _ A _ S I M P L E _ E X A M P L E
P: E X A M P L E
               ^ 从右向左比较，'E' == 'E'
             ^ 'L' == 'L'
           ^ 'P' == 'P'
         ^ 'M' == 'M'
       ^ 'A' == 'A'
     ^ 'X' == 'X'
   ^ 'E' != 'S'，失配

失配字符为 'S'，在模式串中查找 'S'：

• 不存在，使用bad character rule跳过整个模式串长度

T: H E R E _ I S _ A _ S I M P L E _ E X A M P L E
P:                       E X A M P L E

继续匹配…

与其他算法的比较

算法	预处理时间	匹配时间（最坏）	匹配时间（平均）	空间	特点
朴素扫描	$O(1)$	$O(mn)$	$O(mn)$	$O(1)$	简单但慢
KMP	$O(m)$	$O(n+m)$	$O(n+m)$	$O(m)$	最坏情况线性
Boyer-Moore	$O(m+	\Sigma	)$	$O(nm)$	$O(n/m)$
Rabin-Karp	$O(m)$	$O(n+m)$	$O(n+m)$	$O(1)$	哈希方法

在生物信息学中的位置

Boyer-Moore本身在现代生物信息学工具中不常直接使用，但：

• 跳跃思想：现代mapper的seed-and-extend策略中，extend阶段的启发式跳跃有类似思想
• 启发式优化：展示了如何利用失配信息进行优化，这是很多算法的共同主题
• 实际性能：在某些简单模式匹配场景下，Boyer-Moore仍然有实用价值

在实际的生物序列搜索中，更常见的是：

• 基于k-mer的索引（如BWA、minimap2）
• 基于后缀的索引（如FM-index）
• 这些方法通过预处理建立索引，查询时达到亚线性时间

常见误区

• Boyer-Moore总是比KMP快：
• 不一定。Boyer-Moore在最坏情况下可能比KMP慢，但在实际应用中往往更快。选择哪种算法取决于具体场景。
• Boyer-Moore需要两个规则都实现：
• 实际上，简化版的Boyer-Moore可以只实现bad character rule，在很多情况下已经足够快。完整的Boyer-Moore同时使用两个规则以获得更好的性能。
• Boyer-Moore适合小字母表：
• Boyer-Moore在大字母表（如蛋白质序列）上效果更好，因为bad character rule更容易实现大跨度跳跃。在小字母表（如DNA）上，优势可能不明显。

历史注记

Boyer-Moore算法的发表标志着字符串算法从”最坏情况优化”向”实际性能优化”的转变。与KMP追求最坏情况线性时间不同，Boyer-Moore追求平均情况下的亚线性时间。

有趣的是，原始论文只描述了Bad Character Rule。Good Suffix Rule是后来在改进版本中（Boyer-Moore-Horspool）加入的。现在通常将两者结合称为”完整Boyer-Moore算法”。

Horspool变体：Nigel Horspool于1980年提出了简化版本，只使用Bad Character Rule的简化形式，实现更简单，在许多场景下性能接近完整算法。

参考文献

1. Boyer, R. S., & Moore, J. S. (1977). A fast string searching algorithm. Commun. ACM, 20(10), 762-772.
2. Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapter 32. MIT Press.
3. Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences. Cambridge University Press.
4. Horspool, R. N. (1980). Practical fast searching in strings. Software: Practice and Experience, 10(6), 501-506.

相关页面

• 精确字符串匹配
• KMP算法
• Trie与多模式匹配
• 索引结构概览

KMP 算法

同样解决精确匹配但采用完全不同的从左向右策略

延伸阅读

精确字符串匹配

字符串匹配问题的整体概览与算法分类

延伸阅读

Trie 与多模式匹配

Boyer-Moore 的单模式匹配与多模式匹配的对比

延伸阅读

哈希表

另一种高效查找的数据结构，在序列处理中广泛使用

延伸阅读

索引结构概览

现代生物序列搜索所依赖的索引技术总览

延伸阅读