KMP、BM算法(下)

继上篇KMP、BM算法(上),这篇中的BM算法比KMP算法的效率更高,构思精巧。但是算法实现起来也更困难,更难以理解。

可以先简单了解大概思想:阮一峰 http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

一:算法思想:

图片转载来自 Alexia http://www.cnblogs.com/lanxuezaipiao/p/3452579.html

前提:假设文本串text长度为n,模式串pattern长度为m,从右走往左匹配

1、

  • 第一步,将pattern 从右往左匹配,发现最后一个字符 c 与 d 不匹配。我们称这样不匹配的字符为“坏字符”(text 红色)。而且 pattern 中并没有 d ,于是我们知道需将 pattern 右移长度m 即 5 以重新匹配。(右移1、2、3、4也不会匹配,聪明的你肯定想到了)
  • 现在到达 BM 行位置,再从右往左匹配,发现最后一个字符 c 与 b 不匹配。对的,这个时候 b 就是“坏字符”。然而这pattern 中包含了 b ,我们就可以直接将pattern 移动到其中的 b与“坏字符”对应的位置(聪明的你肯定看出来了),但是pattern 中有两个 b,移动就需要选择近的那个避免漏掉。

2、在继续前面的移动后,可以看到在BM行中从右到左匹配,符合匹配的依次是c、a、b 但是之后发现pattern 中的a 并不匹配 b。如果这时依然使用之前的策略,将其移动到 之后对应的b 的位置,反而走了回头路,这样我们就需要将pattern  右移一步。这就是其中的“坏字符”算法思想

3、

  • 再接着看下面,在使用一次“坏字符”算法后,BM 行从右往左发现 pattern 中依次为 b、a是匹配的,之后  b不匹配 a时,运用上面的“坏字符”算法,我们可以右移一位。(这样当然也可以)
  • 但是这次,我们需要利用起已经匹配的 “ab” 两个字符,就叫它“好后缀”。在pattern 中发现在其中有和“好后缀”匹配的 “ab”,于是我们就可以将pattern 右移使得其对应的位置。这就是其中的“好后缀” 算法思想

4、

  • 接着看下面这个,在使用一次“坏字符”算法后,BM 行从右往左发现 pattern 中依次为 c、a、b是匹配的,之后  a 不匹配 b时,”bac” 是 “好后缀”,但是pattern 中并没有和其相匹配的其他串了,这时我们再用回“坏字符”算法”,但是又得注意不往左移动。(再怎么拼凑,左移注定没有意义的)

这便是BM算法中核心的两个算法思想:“坏字符”和“好后缀”算法。BM算法中,每一步的移动步数就是这两种算法中的最大值。

二:算法情况探讨:

(1)坏字符算法

当出现一个坏字符时, BM算法向右移动模式串, 让模式串中最靠右的对应字符与坏字符相对,然后继续匹配。坏字符算法有两种情况。(为什么是最靠右?往最靠右相对不是有左移的情况吗?是的,但这由第二个算法限制它不左移动,别急)

y 为文本串,x 为模式串,shift 为移动步数,u 有已匹配的串。

情况一:

情况二:

(2)好后缀算法

情况一:模式串中有子串和好后缀完全匹配,则将最靠右的那个子串移动到好后缀的位置继续进行匹配。

情况二:如果不存在和好后缀完全匹配的子串,则在好后缀中找到具有如下特征的最长子串,使得P[m-s…m]=P[0…s]。(P[]为pattern )

情况三:如果完全不存在和好后缀匹配的子串,则右移整个模式串。shift=m。

BM算法中,每一步的向右移动的步数都是这两种算法中的最大值。(不往左移动)

三:算法实现:

使用坏字符算法计算pattern需要右移的距离,存放在bmBc[],而按好后缀算法计算pattern右移的距离则要存放在bmGs[]。下面讲下怎么计算bmBc[]和bmGs[]这两个预处理数组。

(1)计算数组bmBc[ ]:

我们使用字符作为下标而不是位置数字作为下标。bmBc[字符] 对应的数组值即是该字符离pattern 最右端的距离,但如果是纯8位字符也只需要256个空间大小,而且对于大模式,可能本身长度就超过了256,所以这样做是值得的(这也是为什么数据越大,BM算法越高效的原因之一)。

bmBc[]的计算分两种情况,与前一一对应。

情况一:字符在模式串中有出现,bmBc[‘v’]表示字符v在模式串中最后一次出现的位置,距离模式串串尾的长度,如上图所示。

情况二:字符在模式串中没有出现,如模式串中没有字符v,则bmBc[‘v’] = strlen(pattern)。

写成代码也非常简单:

图中v是text中的坏字符(对应位置i+j),在pattern中对应不匹配的位置为i,那么pattern实际要右移的距离就是:bmBc[‘v’] – m + 1 + i。(没错可能为负数)

(2)计算bmGs[ ]数组

这里的bmGs[]的下标,是数字而不是字符了,是字符在pattern中位置,bmGs[ i ]应表示在 pattern 中当“好后缀”前不匹配位置在i 时,模式串应移动的距离。假设好后缀长度用数组suff[ ]表示。我们需要先把这个辅助数组suff[ ]求出。

数组suff[ i ]表示pattern中以 i 位置字符为后缀和以最后一个字符为后缀的公共后缀串的长度。(好吧,需要举一个栗子)

i     :            0 1   2 3 4  5  6 7
pattern: b c  a b a  b  a  b

  • 当i=7时,按定义suff[7] = strlen(pattern) = 8
  • 当i=6时,以pattern[6]为后缀的后缀串为bcababa,以最后一个字符b为后缀的后缀串为bcababab,两者没有公共后缀串,所以suff[6] = 0
  • 当i=5时,以pattern[5]为后缀的后缀串为bcabab,以最后一个字符b为后缀的后缀串为bcababab,两者的公共后缀串为abab,所以suff[5] = 4
  • 以此类推,当i=0时,以pattern[0]为后缀的后缀串为b,以最后一个字符b为后缀的后缀串为bcababab,两者的公共后缀串为b,所以suff[0] = 1

另一种改进算法就是利用了已经得到的suff[ ]值,计算现在正在计算的suff[]值。

i 是当前正准备计算suff[]值的那个位置。f 是上一个成功进行匹配的起始位置。g 是上一次进行成功匹配的失配位置。

若 i 在 g 和 f 之间,那么一定有P[i]=P[m-1-f+i](P[ ]为pattern);并且如果suff[m-1-f+i] < i-g, 则suff[i] = suff[m-1-f+i],这不就利用了前面的suff了吗。(难以理解需中再熟悉suff[ ]定义)

求出辅助数组suff[ ]后,再来讨论号后缀的几种情况中bmGs[ ]的值。

情况一:

情况二:

情况三:

再举一个栗子:

 

参考资料:

Boyer-Moore algorithm http://igm.univ-mlv.fr/~lecroq/string/node14.html

Alexia(minmin)    http://www.cnblogs.com/lanxuezaipiao/p/3452579.html

阮一峰 http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*