7.1. Boyer-Moore 字符串搜索算法¶

与 KMP 算法类似，Boyer 和 Moore 于 1977 年开发的字符串搜索算法最初会检查字符串 \(sub\) 的结构，以查看在发生不匹配时是否可以将其向右重新对齐相当大的距离。与 KMP 算法不同，Boyer‑Moore 算法以从右到左的方式比较字符串 \(sub\) 的字符与 \(master\) 字符串的字符。希望的是，当 \(sub\) 与 \(master\) 的一部分进行比较的早期发生不匹配时，这将允许进行大幅度的重新对齐。例如，假设在对齐到 \(master\) 一部分的 \(sub\) 进行从右到左扫描的开始时，我们在 \(master\) 中找到字符"L"，而在 \(sub\) 的最右侧索引中找到某个其他不匹配的字符。那么，如果"L"没有出现在 \(sub\) 的任何其他地方，则可以重新对齐 \(sub\) ，使得 \(sub\) 索引 0 处的字符与 \(master\) 中"L"右侧紧邻的字符对齐。（为什么？）类似地，如果 \(sub\) 最终位置左侧的第一个"L"出现在 \(sub\) 的索引 \(i\) 处，则可以重新对齐 \(sub\) ，使得 \(sub\) 中的索引 \(i\) 与 \(master\) 中的"L"对齐。（为什么？）因此，当不匹配发生在 \(sub\) 的最右侧（即第一个被检查的）位置时， \(master\) 中导致不匹配的字符可用于告诉我们 \(sub\) 可以向右重新对齐多少。可以通过对 \(sub\) 进行一次预处理遍历，来确定 \(master\) 中可能出现的任何字符的重新对齐量。此信息称为“不匹配字符启发式”，并存储在一个我们将命名为 \(MMC\) 的数组中。

为了补充这个不匹配字符启发式方法，Boyer-Moore 算法使用了另一个 \(align\) 数组，其中包含如下定义的重对齐信息。

其中 \(suffix\_length\) 是字符串从位置 \(p + 1\) 开始的 suffix_length，而 \(offset\) 是该 suffix_length 必须向左移动的最小距离，以便在 \(sub\) 中匹配其另一次出现，同时不与 \(p\) 位置的字符匹配。这种向左的移动可能涉及最左侧的字符“滑出主字符串的末端”。当这种情况发生时，那些已滑出主字符串末端的字符被视为与它们本应比较的不存在字符相匹配。 \(align\) 数组的计算可能比较棘手。它在某种程度上类似于 KMP \(align\) 数组的计算，但由于 Boyer-Moore 算法采用从右到左的扫描方式，因此是“反向”进行的。我们将在本模块的后续部分进一步研究 \(align\) 数组的计算。不过，让我们先观看整个 Boyer-Moore 算法的幻灯片演示，假设不匹配字符启发式和这个“反向 KMP" \(align\) 数组都已计算完毕。

现在您已经了解了 Boyer-Moore 算法在预计算了不匹配字符和反向 KMP 对齐后的工作原理，请使用接下来的两个幻灯片演示更详细地研究这两个对齐表的预计算方法。

Boyer-Moore 不匹配字符表构建的幻灯片

Boyer-Moore“反向 KMP"对齐表构建的幻灯片

从上面的幻灯片我们可以看到，Boyer-Moore 算法中实际上涉及三种算法：

使用两个预计算重对齐表的主要算法::

m = Sub.length - 1 while m < Master.length:
  s = Sub.length - 1 while s >= 0 and Master[m] = Sub[s]: m = m-1, s = s-1 if s < 0: return m+1 else: m = m + larger_of(MMC[master[m]], Align[s])
return -1

计算不匹配字符表的算法：

p = 字母表中的当前字符，如果 alphabet[p] 不存在于字符串中，则：MMC[p] = string.length；否则：MMC[p] = 从字符串右端到 alphabet[p] 在字符串中最右侧出现位置的距离。

以及计算反向 KMP 对齐表的算法::

p = current_index suffix_length = 从 p+1 开始的字符串后缀的长度 offset = 为使该后缀与其另一出现位置匹配而必须向左移动的最小距离
                    且该另一出现位置的前驱字符不同于 string[p] 处的字符
若 p = string.length()-1，则：
  align[p] = 1
否则
  align[p] = suffix_length + offset

牢记这些算法的伪代码，通过完成以下四个练习来测试自己对 Boyer-Moore 算法的掌握情况。

1. 练习追踪 Boyer-Moore 算法的一个步骤

2. 练习追踪 Boyer-Moore 不匹配字符表构造的一个步骤

3. 练习追踪 Boyer-Moore 对齐表构造的一个步骤