c

cqqqwq

V1

2022/05/14阅读:16主题:默认主题

BM算法

Boyer Moore 算法(一):原理

Boyer Moore 算法是比较常见、通用的字符串匹配算法。它于 1977 年在Boyer 等人的论文[1] 被提出。目前,C++ 语言的标准库实现的就是 BM 字符串匹配算法。

问题

给定字符串 ,分别作为目标和模式串,求 中的出现位置(下文称出现位置为 shift,即模式串第一个字符所处位置在目标串的下标)。

记从 下标开始的长度为 的字符串 的子串为 ,记从 下标开始到 下标结束的字符串 的子串为

算法原理

BM 算法基于的 Brute Force 思路如下:

对于所有的 shift 是否和 相同。

从 shift 开始;对于每一个 shift ,我们从最右侧 开始,向左逐字符匹配。直到匹配完成或在某一位置失配,进入 的 shift。

注意,很大的不同:对每一个 shift,从右往左匹配模式串。

这样的 Brute Force 算法的复杂度是 的,最坏情况是在每个位置都匹配成功。

优化的整体思路,是从最坏的情况,即每个 shift 都能匹配上很多的时候,因此优化方向就是:

  1. 减少需要考虑的 shift 数量。
  2. 减少在考虑某个 shift 时,需要进行的比较。

以下的两个优化聚焦在如何减少需要考虑的 shift 的数量,具体方法是增大可能的 。换句话说,在一次 shift 为 的匹配结束(成功或在某个位置失配)之后,让 shift 能够多往后移动一些,而不是仅仅从 移动到

Bad Character 优化

在模式串的 位置失配的时候,我们在目标串的 位置会遇到一个“Bad Character”。因为这个字符在目标串中出现,但在模式串这个位置没有出现,所以我们认为这个字符可能在模式串中比较少。

极端情况是,这个字符根本没有在模式串中出现。这样的话,不可能在目标串包含 的区间内匹配上模式串。因此,我们可以将新的 直接设置成

一般情况是,这个字符在模式串中出现了,出现在 。我们希望能把 对齐,这样的话 ,也就是 。我们要选择所有这样的优化中 最小的,防止跳过可能能够匹配的 shift位置。这样的话,我们希望找到最右侧的字符

我们记 ,其中

意义就是:如果在模式串匹配到 时失配,且 ,那么

值得注意的是,这样的 有可能小于 0 。

在实际实现中,由于只有在匹配运行时才会知道 的取值,所以实现中 的计算实际上是计算字符 对应的 ,在匹配时算出

Good Suffix 优化

思路仍然是:试图减少需要考虑的 shift 的数量。假如我们在 shift 为 的时候进行了匹配较多之后才失配,虽然我们耗费了很多时间而且一无所获,但是匹配的过程让我们对于目标串有了较多的了解。直觉上来说,利用好对于模式串预处理的机会,我们是有可能排除掉一些对 shift 位置的考虑的。对我们来说,只和模式串有关的性质是更好的。

假如此时 shift 为 ,在 处与 失配。此时可以知道, ,两串中长度为 的子串完全一致。

黑色的是目标串,蓝色的是模式串,红色的是已经匹配上的部分。
黑色的是目标串,蓝色的是模式串,红色的是已经匹配上的部分。

假如我们接下来将 shift 增大 ,即 ,那么:

在 shift 为 时能够匹配成功,也就是 ;在 处截断后部,得到其必要条件是:

如果 ,那么结合之前在 shift 为 时候的匹配,并对以上的必要条件截断一部分(仍然保留必要性!),可以得到仅与模式串有关的条件:

除此之外,因为在目标串在 失配,新的 shift 位置想要匹配上还必须有 。这意味着这是从 向左侧延伸的,和从 向左侧延伸的,两个字符串的最长匹配

如果 ,同理可以得到必要条件:

我们发现,由于模式从 向左侧延伸的串已经到了头,下面的这条依然成立。这是很重要的性质,将被我们用来高效实现这个算法。

"这是模式串从 向左侧延伸的,和从 向左侧延伸的,两个子串的最长匹配。"

我们要保证不能跳得太多,以至于跳过了可能匹配上的 shift,因此我们要在由上述的必要条件确定的一个可能匹配的 shift 的超集上选取一个最小值,作为我们这一次对 shift 的改变。

形式化地来说,我们构造 ,其中 ,定义为:

事实上,如果 有元素,一定会比 里面的任意元素都要小。

在实现上,我们并不会直接使用形式化的定义,而是会使用

"这是模式串从 向左侧延伸的,和从 向左侧延伸的,两个子串的最长匹配。"

的方法计算。我们以后再谈实现。


综上所述,当 shift 为 时,我们在 失配, ,此时:

细心的读者可能已经发现,这样的算法的复杂度并不尽如人意:在匹配数量 很多的时候,这个算法的复杂度并不佳。可以证明,这个算法的复杂度为

该复杂度的证明并不平凡,首先在 这篇论文[2] 中由 Kunth 等证明(没错,这就是 KMP 算法的论文),我们在这里大概说明思路:

我们考虑复杂度为

  1. 首先, 。(这并非紧界,Cole 的研究[3]给出了 的结果)
  2. 其次, 当 时,假设模式串第一次出现,结束在 位置,那么 ,通过归纳可以得到:

Galil 优化

之所以复杂度还有难看的 因子,是因为我们上面的优化都只优化了上面提到的优化方式的第一条:”减少需要考虑的 shift 数量。“其实,我们只需要一个 "trivial"(Galil, 1979)的,针对第二条”减少在考虑某个 shift 时,需要进行的比较。“的优化,匹配(不包括 的预处理)的时间复杂度就可以被优化到

我们称 周期(Period) ,当且仅当存在 满足 ,使得 的前缀。

我们称 周期的(Periodic) ,当且仅当它存在周期 。容易知道 ,其中

显然,非”周期的“模式串,因为它没有”重复性质“,其在目标串中的出现位置不会离的很近,因此也就目标串中出现很多次,具体来说是 。所以,对于非周期的模式串,匹配的复杂度降到了

对于“周期的”模式串 ,我们试图进行第二类优化。假设 最小的周期 ,满足 ,那么我们断言:在某个 shift 进行匹配的时候,除了“第一次”(上一次在某个 shift 的匹配没有匹配到模式串)需要匹配到完整的模式串,随后的紧接匹配都只需要从右往左匹配到一个长度为 的“周期”长度,即可断言这样的匹配必然是完整的。

感性理解:前面已知存在一个完整匹配,包含一堆周期,下面再找,就只需要把最后一个周期补全。

如果后面没有出现立即周期,那么模式串下一次出现会很远(大致是一个模式串的距离),因此出现次数一定不会很多。

这个优化的实现只需要在原始算法中增加一个变量 替换到循环的下界即可。周期的计算也是在预处理中可以解决的。我们可以证明,BM 算法经过这样的优化后,匹配的复杂度只有

该复杂度的证明不在本文讨论的范畴,可以去寻找 Galil 原始论文查看。基本方法和上述证明归纳过程相同。


匹配过程的伪代码大致如下:

j = 0, l = -1
while s <= n - m:
    i = m - 1
    while i != l and p[i] == t[s + i]:
      i = i - 1
    if i == l:
      print(match at j)
      l = m - k
      i = 0
    else:
      l = -1
    s = s + max(delta1(i, t[s + i]),
                delta2(i))

本文阐述了 BM 算法的基本优化(Bad Character 和 Good Suffix 优化),还介绍了 Galil 优化,最终将字符串匹配的复杂度降低到

但是,具体实现 BM 算法还是相当的困难,尤其是 的预处理,这会在第二部分介绍。

参考资料

[1]

Boyer 等人的论文: https://dl.acm.org/doi/10.1145/359842.359859

[2]

这篇论文中: https://epubs.siam.org/doi/10.1137/0206024

[3]

Cole 的研究: https://dl.acm.org/doi/10.5555/127787.127830

分类:

后端

标签:

后端

作者介绍

c
cqqqwq
V1