BM算法原理与优化实践(二)
扫描二维码
随时随地手机看文章
三、BM 算法实现与代码解析
（一）预处理阶段
坏字符表构建：坏字符表（Bad Character Table）的构建是预处理阶段的关键任务之一。其目的是为了在匹配过程中，当遇到不匹配的字符（即坏字符）时，能够快速确定模式串应该向右滑动的距离。在 Python 中，我们可以使用哈希表（字典）来实现这一功能 。
def build_bad_char_table(pattern):
bad_char = {}
for i in range(len(pattern) - 1):
bad_char[pattern[i]] = i
return bad_char
这段代码通过遍历模式串，将每个字符作为键，其在模式串中的位置作为值，存储在哈希表bad_char中。例如，对于模式串 "ABABC"，哈希表中会记录'A': 0, 'B': 1, 'C': 4（这里只记录到倒数第二个字符，因为最后一个字符在匹配时用于判断是否完全匹配，不需要单独记录其位置）。这种方式使得在匹配过程中查询坏字符的位置时间复杂度为\(O(1)\)，极大地提高了匹配效率。
除了哈希表，也可以使用数组来存储坏字符的位置信息。如果字符集是有限且已知的，例如 ASCII 字符集（共 128 个字符），可以创建一个大小为 128 的数组bc，初始值全部设为 -1 。然后遍历模式串，对于每个字符pattern[i]，将bc[ord(pattern[i])]设置为i。这样在查询时，通过bc[ord(bad_character)]即可获取坏字符在模式串中的位置，同样支持\(O(1)\)时间复杂度的字符查询。
好后缀表构建：好后缀表（Good Suffix Table）的构建相对复杂，它需要考虑模式串中后缀与前缀的匹配关系，以及后缀在模式串中的其他匹配位置。构建好后缀表的核心逻辑在于通过后缀匹配和前缀检查，生成每个位置对应的滑动距离。
def build_good_suffix_table(pattern):
m = len(pattern)
suffix = [-1] * m
prefix = [False] * m
for i in range(m - 1):
j = i
while j >= 0 and pattern[j] == pattern[m - 1 - i + j]:
j -= 1
suffix[m - 1 - i] = j + 1
for i in range(m - 1):
if suffix[i] == 0:
prefix[m - 1 - i] = True
for i in range(1, m):
j = m - 1 - suffix[i]
prefix[j] = True
good_suffix = [m] * m
for i in range(m - 2, -1, -1):
if prefix[i]:
good_suffix[i] = m - 1 - i
else:
good_suffix[i] = good_suffix[m - 1 - suffix[i]]
return good_suffix
在这段代码中，首先通过一个双重循环计算suffix数组，suffix[i]表示从模式串末尾开始长度为i + 1的后缀，其最长匹配后缀的长度（即从模式串开头开始的相同子串长度）。例如，对于模式串 "ABABC"，当i = 0时，后缀为 "C"，其最长匹配后缀长度为 0；当i = 1时，后缀为 "BC"，其最长匹配后缀长度为 0；当i = 2时，后缀为 "ABC"，其最长匹配后缀长度为 3（因为模式串开头的 "ABC" 与之匹配），所以suffix[2] = 3 。
然后，通过检查suffix数组，标记出哪些位置的后缀是模式串的前缀，存储在prefix数组中。最后，根据suffix和prefix数组生成good_suffix数组，good_suffix[i]表示当在位置i匹配失败时，根据好后缀规则模式串应该向右滑动的距离。如果prefix[i]为True，说明从位置i开始的后缀是模式串的前缀，此时滑动距离为模式串长度减去i；否则，滑动距离为good_suffix[m - 1 - suffix[i]]，即根据之前计算的相同后缀的滑动距离来确定。
（二）匹配阶段
匹配阶段是 BM 算法的核心执行部分，它从主串的起始位置开始，将模式串与主串进行对齐，并从模式串的末尾字符开始向前比较。
def boyer_moore_search(text, pattern):
n = len(text)
m = len(pattern)
bad_char = build_bad_char_table(pattern)
good_suffix = build_good_suffix_table(pattern)
s = 0
while s <= n - m:
j = m - 1
while j >= 0 and text[s + j] == pattern[j]:
j -= 1
if j < 0:
print(f"Pattern found at position {s}")
s += good_suffix[0]
else:
bad_char_shift = j - bad_char.get(text[s + j], -1)
good_suffix_shift = good_suffix[j]
s += max(bad_char_shift, good_suffix_shift)
在上述代码中，外层循环控制模式串在主串中的滑动位置s。每次循环开始时，将模式串的末尾字符与主串中对应的字符进行比较（通过内层循环实现）。如果从模式串末尾开始的所有字符都与主串中对应的字符匹配（即j < 0），则说明找到了一个匹配位置，打印出匹配位置，并根据好后缀表中的第一个值（good_suffix[0]）滑动模式串，因为此时整个模式串都匹配，按照好后缀规则移动可以继续寻找下一个可能的匹配位置 。
如果在比较过程中发现不匹配的字符，即坏字符，根据坏字符规则计算滑动距离bad_char_shift，同时根据好后缀规则计算滑动距离good_suffix_shift。然后取这两个滑动距离中的较大值，将模式串向右滑动相应的距离，继续下一轮匹配。这样，通过不断地利用坏字符规则和好后缀规则，BM 算法能够在主串中快速定位模式串的所有匹配位置，避免了大量不必要的字符比较操作，从而实现高效的字符串匹配。
下载文档
