Boyer–Moore–Horspool 算法
| 博伊尔–摩尔算法 | |
|---|---|
| 术语名称 | 博伊尔–摩尔算法 |
| 英语名称 | Boyer–Moore–Horspool algorithm |
| 别名 | BMH算法, BMH algorithm, Horspool's algorithm |
BMH 算法(Boyer–Moore–Horspool algorithm, BMH algorithm)是一种高效的字符串匹配算法，用于在长字符串中匹配短字符串的出现。是 BM 算法的改进版，名称加入了改进者姓氏。
在 BM 算法的“坏字符”“好后缀”策略基础上， BMH 算法认为统计中好后缀在实际场景中起作用场景比例极低，且其初始化及使用均较为复杂，是一个并不划算的启发式条件，即使只使用坏字符规则也能取得较好效率。因此 BMH 算法只使用坏字符规则，并且对其进行了改进，避免了 BM 算法中坏字符规则给出偏移量未必是正值的问题。
原理
首先参考 BM 算法中的坏字符规则。 BM 算法从右向左匹配字符串，当第一次出现不匹配字符时，其作为坏字符会给出一个偏移量，使得匹配位置重新将当前不匹配字符与该字符在模式串中的最后一次出现对齐。 这一位置只和字符相关，不限制其具体出现在不匹配位置前后，可能会出现在当前字符后。 BMH 算法中，坏字符规则中起作用的不是失去匹配的字符，而是匹配位置的最后一个字符。 也就是说， BMH 算法在不匹配时，按照文本串中当前最后一个字符给出一个偏移量，这个偏移量就是模式串去掉最后一个字符后，这个字符最后一次出现的位置。当然，如果没有出现，中间全部位置都一定不匹配最后一个字符，此时移动整个模式串长度。 也就是说 BMH 算法中偏移量总是通过正向移动方式保证最后一个字符与模式串中不会不匹配的位置对齐。
ABCDABCDAADABCDABDE ABCDABD ABCDABD ABCDABD ABCDABD
这一表通常称为 shift 数组。
规则使用
对每一次不匹配， BMH 算法查询当前最后一个位置上文本在模式串中的上一次出现所指定的偏移，通过这一偏移量将最后一个字符对齐。由于小于“坏字符”给出距离的位置，模式串中的最后一个字符一定与长字符串中的字符不同导致匹配失败。因此跳过这两个距离最大值的做法总是不会发生匹配的遗漏。
伪代码
过程 BMH构建偏移量表
别名 boyer_moore_horspool_shift
参数 pattern : 字符串 // 模式串
返回 : 整数的数组 // bad_char 数组
令 m ← |pattern|
创建数组 bad_char[256] // 假设是单字节字符集
循环 c 从 0 到 255
bad_char[c] ← m // 默认初始化为“移动整个模式串”
继续循环 c
循环 j 从 0 到 m-2 // 注意：没有最后一个字符 m-1
bad_char[patternⱼ] ← j // 记录最后出现位置
继续循环 j
返回 bad_char
过程 BMH匹配
别名 boyer_moore_horspool_match
参数 text : 字符串 // 主文本
参数 pattern : 字符串 // 模式串
返回 : 整数的可选值 // 匹配位置
令 n ← |text|, m ← |pattern|
令 bad_char ← KMP构建坏字符表 pattern
令 i ← 0 // 文本指针
循环 i
当 i ≤ n - m 时
执行
令 j ← m-1 // 模式串指针（从右向左）
循环 j
当 j ≥ 0 且 patternⱼ == textᵢ₊ⱼ 时
j ← j-1
继续循环
如果 j < 0 那么 // 完全匹配
返回 i
否则
如果 j = m 那么
令 i ← i + shift[textᵢ₊ₘ]
继续循环 i
返回 空可选值时间复杂度
可以确认，如果全部字符都是同一个字符，由于只会依次移动比较，最坏情况下的时间复杂度可以高达 [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(k) }[/math] 。