Boyer–Moore 算法
| 博伊尔–摩尔算法 | |
|---|---|
| 术语名称 | 博伊尔–摩尔算法 |
| 英语名称 | Boyer–Moore algorithm |
| 别名 | BM算法, BM algorithm |
BM 算法(Boyer–Moore algorithm, BM algorithm)是一种高效的字符串匹配算法，用于在长字符串中匹配短字符串的出现。名称来自发明人姓氏。常用于文本编辑器中，比如在 GNU 的 grep 命令中实际使用。
暴力搜索中每个位置尝试匹配相对。 BP 的核心思想是在进行匹配时，进行被称为“坏字符”“好后缀”的策略，从而在判断匹配失败时，快速跳过无序匹配的情况。这一策略依赖字符的分布情况，当字符越随机，效率就越高。
记号
字符串匹配问题中，目标是在长字符串中寻找一个短字符串的第一次出现。称短字符串为“模式(pattern)”串，长度记为 [math]\displaystyle{ m }[/math] ，长字符串长度记为 [math]\displaystyle{ n }[/math] 。以下用长字符串为 ABABCDABCDABDE ，短字符串为 ABC 举例。
原理
字符串匹配问题的暴力算法要在每个位置尝试从头开始匹配模式，也就是需要最多 [math]\displaystyle{ (n-m)m = O(mn) }[/math] 次将每一个位置开始的字符串和模式串依次逐字符匹配。
AABCDABCDABDE ABCDABD ABCDABD ABCDABD ABCDABD ABCDABD ABCDABDE
BM 算法中，为了获得匹配位置尽可能大地向右前进，模式串被从右向左比较，且使用“坏字符(the bad-character rule)”和“好后缀(the good-suffix rule)”两种启发式的规则进行匹配位置跳过。
坏字符规则
坏字符指当遇到不匹配字符，也就是“坏字符”时，移动字符串位置使得该字符最后一次出现在模式串中的位置与这一字符的出现对齐。如果模式串中实际没有这一字符存在，则可以直接跳过整个模式串长度，所以也可以表达为模式串中的最后一个不会与该字符不匹配的位置。因为这是这一字符的最后一次出现，两个位置之间的可能匹配位置都不会匹配上这个字符。
在原始 BM 算法中，由于坏字符在模式串中可能在当前不匹配字符之后还有出现，这一偏移量可能是负数。对这一点的优化参考 Boyer–Moore–Horspool 算法。
ABCDABCDABDE ABCDABD ABCDABDE
因此，对字符集中的每一个字符需要记录其在模式串中最后一次出现位置，对应的偏移量也称为 bad_char 数组。
好后缀规则
好后缀指当遇到不匹配字符时，由于其后方的后缀部分已经匹配，也就是一个“好后缀”，移动字符串位置对齐时，可以对齐该后缀最后一次在模式串中出现且有不同前缀的位置。这个位置解释较为复杂，可以认为是满足以下几条规则的最后一次出现：
- 该后缀在模式串中的一次出现，且前一个字符与不匹配的模式字符不同。比如
abcdabcabcab中，后缀ab符合条件的出现是dab中的，而不是第一个cab中的。这是以为后者和后缀ab前的字符同时为c，在后一个cab匹配失败时前一个cab一定也不匹配，因此不是备选位置。 - 该后缀的某个后缀作为整个模式串的前缀出现。比如
bcab中，后缀ab复合条件的出现是最开头的b，因为这是一个可能的匹配位置，尽管只用到了b，但是不涉及a不匹配的问题，仍然是备选位置。 - 如果以上两种都不存在，则选择将整个模式串移动到已匹配部分之后。逻辑上就是不可能存在不匹配，所以成为了一个备选位置。也可以看成是上一条规则里重复出现的部分只有空串。
由于移动方向是相对的，移动到长字符串中第一个使得后缀已匹配部分不会匹配失败的位置，也就是找到模式串中最后一个使得这部分不会匹配失败的位置。以上三个条件实际上就是说寻找“不失败”位置的方法。
如果完整出现过（且排除前面的字符一致的）就是其中最后一个，如果没有备选位置，就看其一个后缀是否出现在开头，进入 2 和 3 分支。
因此，对模式串中的每个位置需要记录其不匹配时，后续后缀在模式串中的上一个不失败位置，对应地偏移量称为 good_suffix 数组。
规则使用
对每一个字符上的不匹配，总是能根据长字符串中当前位置字符和模式串中后续位置的后缀给出两个不同的移动距离。小于“坏字符”给出距离的位置，模式串中的字符一定与长字符串中的字符不同导致匹配失败；小于“好后缀”给出距离的位置，长字符串中已经和后缀匹配的部分一定和模式串中的部分不同。因此跳过这两个距离最大值的做法总是不会发生匹配的遗漏。
伪代码
过程 BM构建坏字符表
别名 boyer_moore_bad_char
参数 pattern : 字符串 // 模式串
返回 : 整数的数组 // bad_char 数组
令 m ← |pattern|
创建数组 bad_char[256] // 假设是单字节字符集
循环 c 从 0 到 255
bad_char[c] ← -1 // 默认初始化为特殊值“不存在”
继续循环 c
循环 j 从 0 到 m-1
bad_char[patternⱼ] ← j // 记录最后出现位置
继续循环 j
过程 BM构建好后缀表
别名 boyer_moore_good_suffix
参数 pattern : 字符串 // 模式串
返回 : 整数的数组 // bad_char 数组
令 m ← |pattern|
创建数组 suffix[m] // 后缀数组
创建数组 good_suffix[m] // 好后缀移动表
循环 i 从 0 到 m-1
执行
good_suffixᵢ ← m // 默认初始化为“移动整个模式串”
suffixᵢ ← 0
继续循环 i
循环 i 从 m-1 到 0 递减
执行
令 j ← i, k ← 0 // k 循环尾部， j 循环到当前 i 为止的索引，取 j..i 中间的子串
循环
当 j ≥ 0 且 patternⱼ == patternₘ₋₁₋ₖ 时
执行
k ← k+1
suffixₖ ← j // 记录后缀匹配的最长靠右子串的起始位置
j ← j-1
继续循环 j
继续循环 i
令 j ← 0
循环 i 从 m-1 到 0 递减
执行
如果 suffixᵢ == i+1 那么
循环
当 j < m-1-i 时
执行
good_suffixⱼ ← m-1-i
j ← j+1
继续循环 j
继续循环 i
循环 i 从 0 到 m-2
good_suffixₘ₋₁₋suffixᵢ ← m-1-i
继续循环 i
过程 BM匹配
别名 boyer_moore_match
参数 text : 字符串 // 主文本
参数 pattern : 字符串 // 模式串
返回 : 整数的可选值 // 匹配位置
令 n ← |text|, m ← |pattern|
令 bad_char ← KMP构建坏字符表 pattern
令 good_suffix ← KMP构建部分匹配表 pattern ❶
令 i ← 0 // 文本指针
当 i ≤ n - m 时
令 j ← m-1 // 模式串指针（从右向左）
// 从右向左比较
当 j ≥ 0 且 patternⱼ == textᵢ₊ⱼ 时
j ← j-1
若 j < 0 则 // 完全匹配
返回 i
i ← i + good_suffix₀ // 继续搜索
否则
// 计算坏字符移动
令 bc_shift ← j - bad_char[textᵢ₊ⱼ]
如果 j = m 那么
令 i ← i + bc_shift
否则
令 gs_shift ← good_suffixⱼ ❶
令 i ← i + max(bc_shift, gs_shift)
返回 -1❶ 尽管写了好字符的整个构造方式，但是由于概率上大多数不匹配都是最后一个字符就已经不匹配了，而且搜索时是在模式串里寻找模式串的后缀，本身也有一定的复杂度，所以一般会做懒惰初始化，先按照跳过整个的情况，然后按照位置依次做部分更新，在需要的时候才取指定位置的值并记录。
时间复杂度
可以确认，如果全部字符都是同一个字符，由于两种规则都只会依次移动比较，最坏情况下的时间复杂度可以高达 [math]\displaystyle{ O(mn) }[/math] 。但平均情况下，由于随机字符串中出现重复字符的概率较小，几乎可以认为每次比较都几乎会前进模式串长度 [math]\displaystyle{ m }[/math] ，但是如果记字符集大小为 [math]\displaystyle{ k }[/math] ，会有 [math]\displaystyle{ \tfrac{1}{k}-\tfrac{1}{k^2} }[/math] 概率只有 [math]\displaystyle{ m-1 }[/math] ， [math]\displaystyle{ \tfrac{1}{k^2} - \tfrac{1}{k^3} }[/math] 概率只有 [math]\displaystyle{ m-2 }[/math] ,以此类推，因此认为平均复杂度为 [math]\displaystyle{ O(\frac{n \log_k m}{m}) }[/math] 。
空间复杂度
算法的空间复杂度在于需要额外空间处理两个数组，因此为 [math]\displaystyle{ O(m+k) }[/math] 。
变体
- 大字符集：需要调整坏字符表大小。但是对前缀编码，因为不存在为正常字符匹配到后半字符的情况，仍可以使用同一方法只匹配 256 。
- Boyer–Moore–Horspool 算法：只使用优化版的坏字符规则，不使用好后缀规则。
- Galil 规则：额外处理字符串周期性，避免重复字符引起每次移动过少。
- 查找时结合哈希的方法。