Boyer-Moore 算法
本章节内容需要以 《前缀函数与 KMP 算法》 作为前置章节。
之前的 KMP 算法将前缀匹配的信息用到了极致,
而 BM 算法背后的基本思想是通过后缀匹配获得比前缀匹配更多的信息来实现更快的字符跳转。
基础介绍
想象一下,如果我们的的模式字符串 ,被放在文本字符串 的左手起头部,使它们的第一个字符对齐。
在这里做定义,往后不赘述:
的长度为 ,特别地对于从 0 开始的串来说,规定 为 串最后一个字符的位置;
的长度 ,。
假如我们知道了 的第 个字符 (与 的最后一个字符对齐)考虑我们能得到什么信息:
观察 1:
如果我们知道 这个字符不在 中,我们就不用考虑 从 的第 个、第 个……第 个字符起出现的情况,,而可以直接将 向下滑动 个字符。
观察 2:
更一般地,如果出现在 最末尾(也就是最右边)的那一个 字符的位置是离末尾端差了 个字符,
那么就可以不用匹配,直接将 向后滑动 个字符:如果滑动距离少于 ,那么仅就 这个字符就无法被匹配,当然模式字符串 也就不会被匹配。
因此除非 字符可以和 末尾的那个字符匹配,否则 要跳过 个字符(相当于 向后滑动了 个字符)。并且我们可以得到一个计算 的函数 :
注意:显然这个表只需计算到 的位置
现在假设 和 最后一个字符匹配到了,那我们就看看 前一个字符和 的倒数第二个字符是否匹配:
如果是,就继续回退直到整个模式串 完成匹配(这时我们就在 上成功得到了一个 的匹配);
或者,我们也可能会在匹配完 的倒数第 个字符后,在倒数第 个字符上失配,这时我们就希望把 向后滑动到下一个可能会实现匹配的位置,当然我们希望滑动得越远越好。
观察 3(a):
在 观察 2 中提到,当匹配完 的倒数 个字符后,如果在倒数第 个字符失配,为了使得 中的失配字符与 上对应字符对齐,
需要把 向后滑动 个字符,也就是说我们应该把注意力看向之后的 个字符(也就是看向 滑动 k 之后,末段与 对齐的那个字符)。
而 ,
所以我们的注意力应该沿着 向后跳 个字符。
然而,我们有机会跳过更多的字符,请继续看下去。
观察 3(b):
如果我们知道 接下来的 个字符和 的最后 个字符匹配,假设这个子串为 ,
我们还知道在 失配字符 后面是与 相匹配的子串,而假如 对应失配字符前面存在 ,我们可以将 向下滑动一段距离,
使得失配字符 在 上对应的字符前面出现的 (合理重现,plausible reoccurrence,以下也简称 pr)与 的 对齐。如果 上有多个 ,按照从右到左的后缀匹配顺序,取第一个(rightmost plausible reoccurrence,以下也简称 rpr)。
假设此时 向下滑动的 个字符(也即 末尾端的 与其最右边的合理重现的距离),这样我们的注意力应该沿着 向后滑动 个字符,这段距离我们称之为 :
假定 为 在 上失配时的最右边合理重现的位置,(这里只给出简单定义,在下文的算法设计章节里会有更精确的讨论),那么显然 。
所以有:
于是我们在失配时,可以把把 上的注意力往后跳过 个字符
实例说明:
箭头指向失配字符 :
没有出现 中,根据 观察 1, 直接向下移动 个字符,也就是 7 个字符:
根据 观察 2,我们需要将 向下移动 4 个字符使得短横线字符对齐:
现在char: 匹配了,把 上的指针左移一步继续匹配:
根据 观察 3(a), 失配,因为 不在 中,所以 向下移动 个字符,而 上指针向下移动 个字符:
这时 又一次匹配到了 的最后一个字符 , 上的指针向左匹配,匹配到了 ,继续向左匹配,发现在字符 失配:
显然直观上看,此时根据 观察 3(b),将 向下移动 个字符,使得后缀 对齐,这种滑动可以获得 指针最大的滑动距离,此时 ,即 上指针向下滑动 7 个字符。
而从形式化逻辑看,此时,, 这样从形式逻辑上支持了进行 观察 3(b) 的跳转:
现在我们发现了 上每一个字符都和 上对应的字符相等,我们在 上找到了一个 的匹配。而我们只花费了 14 次对 的引用,其中 7 次是完成一个成功的匹配所必需的比较次数(),另外 7 次让我们跳过了 22 个字符,Amazing(浮夸口气)!
算法设计
最初的匹配算法
现在看这样一个利用 和 进行字符串匹配的算法:
如果上面的算法 ,表明 不在 中;如果返回一个数字,表示 在 左起第一次出现的位置。
然后让我们更精细地描述下计算 ,所依靠的 函数。
根据前文定义, 表示在 失配时,子串 在 最右边合理重现的位置。
也就是说需要找到一个最好的 , 使得 ,另外要考虑两种特殊情况:
- 当 时,相当于在 前面补充了一段虚拟的前缀,实际上也符合 跳转的原理。
- 当 时,如果 ,则这个 不能作为 的合理重现。 原因是 本身是失配字符,所以 向下滑动 个字符后,在后缀匹配过程中仍然会在 处失配。
还要注意两个限制条件:
- 。因为当 时,有 ,在 上失配的字符也会在 上失配。
- 考虑到 ,所以规定 。
由于理解 是实现 BoyerMoore 算法的核心,所以我们使用如下两个例子进行详细说明:
对于 , 为 ,在 之前的最右边合理重现只能是 ,也就是最右边合理重现位置为 -5,即 ;
对于 , 为 ,在 之前的最右边的合理重现是 ,所以 ;
对于 , 为 ,在 之前的最右边的合理重现是 ,所以 ;
对于 , 为 ,在 之前的最右边的合理重现是 ,所以 ;
对于 , 为 ,在 之前的最右边的合理重现是 ,所以