Boyer-Moore算法

本章节内容需要以 《前缀函数与 KMP 算法》 作为前置章节。

之前的 KMP 算法将前缀匹配的信息用到了极致，

而 BM 算法背后的基本思想是通过后缀匹配获得比前缀匹配更多的信息来实现更快的字符跳转。

基础介绍

想象一下，如果我们的的模式字符串 pat ，被放在文本字符串 string 的左手起头部，使它们的第一个字符对齐。

\begin{aligned} \textit{pat}:\qquad\qquad &\texttt{EXAMPLE} \\ \textit{string}:\qquad\quad &\texttt{HERE IS A SIMPLE EXAMPLE} \dots \\ &\qquad\ \ \ \, \, \Uparrow \end{aligned}

在这里做定义，往后不赘述：

pat 的长度为 patlen ，特别地对于从 0 开始的串来说，规定 patlastpos=patlen-1 为 pat 串最后一个字符的位置；

string 的长度 stringlen ， stringlastpos = stringlen-1 。

假如我们知道了 string 的第 patlen 个字符 char （与 pat 的最后一个字符对齐）考虑我们能得到什么信息：

观察 1：

如果我们知道 char 这个字符不在 pat 中，我们就不用考虑 pat 从 string 的第 1 个、第 2 个……第 patlen 个字符起出现的情况，，而可以直接将 pat 向下滑动 patlen 个字符。

观察 2：

更一般地，如果出现在 pat 最末尾（也就是最右边）的那一个 char 字符的位置是离末尾端差了 delta_1 个字符，

那么就可以不用匹配，直接将 pat 向后滑动 delta_1 个字符：如果滑动距离少于 delta_1 ，那么仅就 char 这个字符就无法被匹配，当然模式字符串 pat 也就不会被匹配。

因此除非 char 字符可以和 pat 末尾的那个字符匹配，否则 string 要跳过 delta_1 个字符（相当于 pat 向后滑动了 delta_1 个字符）。并且我们可以得到一个计算 delta_1 的函数 delta_1(char) ：

\begin{array}{ll} \textbf{int}\ delta1(\textbf{char}\ char) \\ \qquad \textbf{if}\ \text{char不在pat中 || char是pat上最后一个字符} \\ \qquad\qquad\textbf{return}\ patlen \\ \qquad \textbf{else} \\ \qquad\qquad\textbf{return}\ patlastpos-i\quad\textbf{//}\ \text{i为出现在pat最末尾的那一个char出现的位置，即pat[i]=char} \end{array}

注意：显然这个表只需计算到 patlastpos-1 的位置

现在假设 char 和 pat 最后一个字符匹配到了，那我们就看看 char 前一个字符和 pat 的倒数第二个字符是否匹配：

如果是，就继续回退直到整个模式串 pat 完成匹配（这时我们就在 string 上成功得到了一个 pat 的匹配）；

或者，我们也可能会在匹配完 pat 的倒数第 m 个字符后，在倒数第 m+1 个字符上失配，这时我们就希望把 pat 向后滑动到下一个可能会实现匹配的位置，当然我们希望滑动得越远越好。

观察 3(a)：

在 观察 2 中提到，当匹配完 pat 的倒数 m 个字符后，如果在倒数第 m+1 个字符失配，为了使得 string 中的失配字符与 pat 上对应字符对齐，

需要把 pat 向后滑动 k 个字符，也就是说我们应该把注意力看向之后的 k+m 个字符（也就是看向 pat 滑动 k 之后，末段与 string 对齐的那个字符）。

而 k=delta_1-m ，

所以我们的注意力应该沿着 string 向后跳 delta_1-m+m = delta_1 个字符。

然而，我们有机会跳过更多的字符，请继续看下去。

观察 3(b)：

如果我们知道 string 接下来的 m 个字符和 pat 的最后 m 个字符匹配，假设这个子串为 subpat ，

我们还知道在 string 失配字符 char 后面是与 subpat 相匹配的子串，而假如 pat 对应失配字符前面存在 subpat ，我们可以将 pat 向下滑动一段距离，

使得失配字符 char 在 pat 上对应的字符前面出现的 subpat （合理重现，plausible reoccurrence，以下也简称 pr）与 string 的 subpat 对齐。如果 pat 上有多个 subpat ，按照从右到左的后缀匹配顺序，取第一个（rightmost plausible reoccurrence，以下也简称 rpr）。

假设此时 pat 向下滑动的 k 个字符（也即 pat 末尾端的 subpat 与其最右边的合理重现的距离），这样我们的注意力应该沿着 string 向后滑动 k+m 个字符，这段距离我们称之为 delta_2(j) ：

假定 rpr(j) 为 subpat=pat[j+1\dots patlastpos] 在 pat[j] 上失配时的最右边合理重现的位置， rpr(j) < j （这里只给出简单定义，在下文的算法设计章节里会有更精确的讨论），那么显然 k=j-rpr(j),\ m=patlastpos-j 。

所以有：

\begin{array}{ll} \textbf{int}\ delta2(\textbf{int}\ j) \quad\textbf{//}\ \text{j为失配字符在pat上对应字符的位置} \\ \qquad\qquad\textbf{return}\ patlastpos-rpr(j) \\ \end{array}

于是我们在失配时，可以把把 string 上的注意力往后跳过 \max(delta_1,delta_2) 个字符

实例说明：

箭头指向失配字符 char ：

\begin{aligned} \textit{pat}:\qquad\qquad &\texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \, \, \Uparrow \end{aligned}

\texttt{F} 没有出现 pat 中，根据 观察 1， pat 直接向下移动 patlen 个字符，也就是 7 个字符：

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\quad\ \ \, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \, \, \qquad\quad\ \ \ \Uparrow \end{aligned}

根据 观察 2，我们需要将 pat 向下移动 4 个字符使得短横线字符对齐：

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\quad\ \ \, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad \Uparrow \end{aligned}

现在char: \texttt{T} 匹配了，把 string 上的指针左移一步继续匹配：

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\quad\ \ \, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\quad\ \, \Uparrow \end{aligned}

根据 观察 3(a)， \texttt{L} 失配，因为 \texttt{L} 不在 pat 中，所以 pat 向下移动 k=delta_1-m=7-1=6 个字符，而 string 上指针向下移动 delta_1=7 个字符：

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\qquad\qquad\ \ \,\, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad\qquad\ \ \ \, \, \Uparrow \end{aligned}

这时 char 又一次匹配到了 pat 的最后一个字符 \texttt{T} ， string 上的指针向左匹配，匹配到了 \texttt{A} ，继续向左匹配，发现在字符 \texttt{-} 失配：

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\qquad\qquad\ \ \,\, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad\quad\ \ \ \,\, \Uparrow \end{aligned}

显然直观上看，此时根据 观察 3(b)，将 pat 向下移动 k=5 个字符，使得后缀 \texttt{AT} 对齐，这种滑动可以获得 string 指针最大的滑动距离，此时 delta_2=k+patlastpos-j=5+6-4=7 ，即 string 上指针向下滑动 7 个字符。

而从形式化逻辑看，此时， delta_1=7-1-2=4,\ delta_2=7, \max(delta_1,delta_2)= 7 ， 这样从形式逻辑上支持了进行 观察 3(b) 的跳转：

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\qquad\qquad\qquad\quad \;\, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad\qquad\qquad\quad \ \ \; \Uparrow \end{aligned}

现在我们发现了 pat 上每一个字符都和 string 上对应的字符相等，我们在 string 上找到了一个 pat 的匹配。而我们只花费了 14 次对 string 的引用，其中 7 次是完成一个成功的匹配所必需的比较次数（ patlen=7 ），另外 7 次让我们跳过了 22 个字符，Amazing（浮夸口气）！

算法设计

最初的匹配算法

现在看这样一个利用 delta_1 和 delta_2 进行字符串匹配的算法：

\begin{array}{ll} i \gets patlastpos. \\ j \gets patlastpos. \\ \textbf{loop}\\ \qquad \textbf{if}\ j < 0 \\ \qquad \qquad \textbf{return}\ i+1 \\ \\ \qquad \textbf{if}\ string[i]=pat[j] \\ \qquad \qquad j \gets j-1 \\ \qquad \qquad i \gets i-1 \\ \qquad \qquad \textbf{continue} \\ \\ \qquad i \gets i+max(delta_1(string[i]), delta_2(j)) \\ \\ \qquad \textbf{if}\ i > stringlastpos \\ \qquad \qquad \textbf{return}\ false \\ \qquad j \gets patlastpos \\ \end{array}

如果上面的算法 \textbf{return}\ false ，表明 pat 不在 string 中；如果返回一个数字，表示 pat 在 string 左起第一次出现的位置。

然后让我们更精细地描述下计算 delta_2 ，所依靠的 rpr(j) 函数。

根据前文定义， rpr(j) 表示在 pat(j) 失配时，子串 subpat=pat[j+1\dots patlastpos] 在 pat[j] 最右边合理重现的位置。

也就是说需要找到一个最好的 k , 使得 pat[k\dots k+patlastpos-j-1]=pat[j+1\dots patlastpos] ，另外要考虑两种特殊情况：

  1. 当 k<0 时，相当于在 pat 前面补充了一段虚拟的前缀，实际上也符合 delta_2 跳转的原理。
  2. 当 k>0 时，如果 pat[k-1]=pat[j] ，则这个 pat[k\dots k+patlastpos-j-1] 不能作为 subpat 的合理重现。 原因是 pat[j] 本身是失配字符，所以 pat 向下滑动 k 个字符后，在后缀匹配过程中仍然会在 pat[k-1] 处失配。

还要注意两个限制条件：

  1. k < j 。因为当 k=j 时，有 pat[k]=pat[j] ，在 pat[j] 上失配的字符也会在 pat[k] 上失配。
  2. 考虑到 delta_2(patlastpos)= 0 ，所以规定 rpr(patlastpos) = patlastpos 。

由于理解 rpr(j) 是实现 BoyerMoore 算法的核心，所以我们使用如下两个例子进行详细说明：

\begin{aligned} \textit{j}:\qquad\qquad\quad\ \ &\texttt{0 1 2 3 4 5 6 7 8} \\ \textit{pat}:\qquad\qquad\ \ &\texttt{A B C X X X A B C} \\ \textit{rpr(j)}:\qquad\quad\ \ &\texttt{5 4 3 2 1 0 2 1 8} \\ \textit{sgn}:\qquad\qquad\ \ &\texttt{- - - - - - - - +} \end{aligned}

对于 rpr(0) ， subpat 为 \texttt{BCXXXABC} ，在 pat[0] 之前的最右边合理重现只能是 \texttt{[(BCXXX)ABC]XXXABC} ，也就是最右边合理重现位置为 -5，即 rpr(j)=-5 ；

对于 rpr(1) ， subpat 为 \texttt{CXXXABC} ，在 pat[1] 之前的最右边的合理重现是 \texttt{[(CXXX)ABC]XXXABC} ，所以 rpr(j)=-4 ；

对于 rpr(2) ， subpat 为 \texttt{XXXABC} ，在 pat[2] 之前的最右边的合理重现是 \texttt{[(XXX)ABC]XXXABC} ，所以 rpr(j)=-3 ；

对于 rpr(3) ， subpat 为 \texttt{XXABC} ，在 pat[3] 之前的最右边的合理重现是 \texttt{[(XX)ABC]XXXABC} ，所以 rpr(j)=-2 ；

对于 rpr(4) ， subpat 为 \texttt{XABC} ，在 pat[4] 之前的最右边的合理重现是 \texttt{[(X)ABC]XXXABC} ，所以