【模式匹配】更快的Boyer-Moore算法

jopen 9年前

1. 引言

前一篇中介绍了字符串KMP算法,其利用失配时已匹配的字符信息,以确定下一次匹配时模式串的起始位置。本文所要介绍的Boyer-Moore算法是一种比KMP更快的字符串匹配算法,它到底是怎么快的呢?且听下面分解。

不同于KMP从 左右至右 与主串字符做比较,Boyer-Moore算法是从模式串的尾字符开始 从右至左 做比较,接下来讨论的一些递推式都与这个特性有关。

思想

首先,我们一般化匹配失败的情况,设主串 \(y\) 、模式串 \(x\) 的失配位置为 i+j 与 i ,且主串、模式串的长度各为 \(n\) 与 \(m\) ,如下图:

已匹配上的字符结构:

\[ y[i+j+1 \dots j+m-1] = x[i+1 \dots m-1] \]

失配后下一次匹配时,模式串的指针应移动到哪个位置呢(主串的指针依然在失配位置)?从上图中看出,我们可以利用两方面的信息:

  1. 已经匹配上的字符结构,
  2. 主串失配位置的字符

前一篇中所介绍的KMP只利用第一条信息,而Boyer-Moore算法则是已匹配、失配信息都利用到了,故主串的指针移动更为高效。同时,根据这两方面信息(已匹配、失配信息),在Boyer-Moore算法引申出来两条移动规则:好后缀移动(good-suffix shift)与坏字符移动(bad-character shift)。

实例

Moore教授在 这里 给出BM算法一个实例,比如主串= HERE IS A SIMPLE EXAMPLE ,模式串= EXAMPLE 。第一次匹配如下图:

在第一次匹配中,模式串在尾字符发生失配,而主串的失配字符为 S ,且 S 不属于模式串的字符;因此下一次匹配时模式串指针应向右移动 7 位(坏字符移动)。第二次匹配如下图:

第二次匹配也是在模式串尾字符发生失配,但不同的是主串的失配字符为 P 属于模式串的字符;因此下一次匹配时模式串的 P (从右开始第一次出现)应对齐于主串的失配字符 P (坏字符移动)。第三次匹配如下图:

在第三次匹配中,模式串的后缀 MPLE 完全匹配上主串,主串的失配字符为 I ,不属于模式串的字符;那么下一次匹配是模式串指针应怎么移动呢(是坏字符移动,还是好后缀移动?)?BM算法采取的办法:移动步数= \(\max\{坏字符移动步数,\ 好后缀移动步数\}\) 。(具体移动步数的计算会在下面给出),这里是按好后缀移动;第四次匹配如下图:

第四次匹配的情况与第二次类似,应按坏字符移动,第五次匹配(模式串与主串完全匹配)如下图:

2. BM算法详述

好后缀移动

因已匹配上的字符结构正好为模式串的后缀,故名之为 好后缀 。好后缀移动一般分为两种情况:

  1. 移动后,模式串有子串能 完全匹配 上好后缀;
  2. 移动后,模式串只有能 部分匹配 上好后缀的子串

我们用数组 bmGs[i] 表示模式串的失配位置为 i 时好后缀移动的步数。第一类情况如下图:

第二类情况如下图:

接下来的问题是应如何计算 bmGs[i] 呢?我们引入 suff 函数,其定义如下:

\[ suff[i]=\max \{k:\ x[i-k+1\dots i]=x[m-k\dots m-1\},1\le m \]

表示了模式串中末字符为 x[i] 的子串能匹配模式串后缀的 最大长度 。其中, suff[i]=m 。

对于第一类情况,令 i+1=m-suff[a] ,则 x[i+1..m-1]=x[m-suff[a]..m-1] ;根据 suff 函数的定义,有 x[m-suff[a]..m-1]=x[a-suff[a]-1..a] ;则 x[i+1..m-1]=x[a-suff[a]-1..a] ,即可得到 bmGs[i]=bmGs[m-suff[a]-1]=m-1-a 。

对于第二类情况,由字符的部分匹配可得 x[0..m-1-bmGs[i]]=x[bmGs[i]..m-1] ,即 suff[m-1-bmGs[i]]=m-bmGs[i] 。令 m-bmGs[i]=a ,有 suff[a-1]=a 。因为是部分匹配,故 bmGs[i] = m-a > i+1 ,则 i < m-a-1 。综上,当 i < m-a-1 且 suff[a-1]=a 时, bmGs[i]=m-a 。

有可能上述两种情况都没能被匹配上,则 bmGs[i]=m 。综合上述三类情况, bmGs 数组计算的实现代码(参看[2]):

void preBmGs(char *x, int m, int bmGs[]) {     int i, j, suff[XSIZE];        suffixes(x, m, suff);        // case 3, default value     for (i = 0; i < m; ++i)        bmGs[i] = m;     j = 0;     // case 2     for (i = m - 1; i >= 0; --i)        if (suff[i] == i + 1)           for (; j < m - 1 - i; ++j)              if (bmGs[j] == m)                 bmGs[j] = m - 1 - i;     // case 1     for (i = 0; i <= m - 2; ++i)        bmGs[m - 1 - suff[i]] = m - 1 - i;  }

坏字符移动

坏字符移动是根据主串失配位置的字符 y[i+j] 而进行的移动。同样地,我们用数组 bmBc[c] 表示主串失配位置字符为 c 时坏字符移动的步数。坏字符移动一般分为两种情况:

  1. 模式串 x[0..i-1] 有字符 y[i+j] 且第一次出现,如下图:

  2. 整个模式串都不包含该字符串,如下图:

据此,可以将 bmBc[c] 定义如下:

\[ bmBc[c]=\min \{i: 1\le i < m \ and \ x[m-1-i]=c \} \]

表示距模式串末字符最近的 c 字符;若 c 字符未出现在模式串中,则 bmBc[c]=m 。C实现代码:

void preBmBc(char *x, int m, int bmBc[]) {     int i;        for (i = 0; i < ASIZE; ++i)        bmBc[i] = m;     for (i = 0; i < m - 1; ++i)        bmBc[x[i]] = m - i - 1;  }

suff函数计算

bmGs[i] 的计算依赖于 suff 函数;如何更为高效的计算 suff 函数成为了接下来需要考虑的问题。符号标记的定义如下:

  • i 表示当前位置;
  • f 记录上一轮匹配的起始位置;
  • g 记录上一轮匹配的失配位置。

这里所说的 匹配 指的是与模式串后缀的匹配。同样地,一般化匹配过程,如下图:

当 g < i < f 则必有 x[i]=x[m-1-(f-i)]=x[m-1-f+i] ;

  • 若 suff[m-1-f+i] < i-g ,则 suff[i]=suff[m-1-f+i] ;
  • 否则, suff[i] 与 suff[m-1-f+i] 没有关系,要根据定义进行计算。

C实现代码:

void suffixes(char *x, int m, int *suff) {     int f, g, i;        suff[m - 1] = m;     g = m - 1;     for (i = m - 2; i >= 0; --i) {        if (i > g && suff[i + m - 1 - f] < i - g)           suff[i] = suff[i + m - 1 - f];        else {           if (i < g)              g = i;           f = i;           while (g >= 0 && x[g] == x[g + m - 1 - f])              --g;           suff[i] = f - g;        }     }  }

复杂度分析

3. 参考资料

[1] Moore, Boyer-Moore algorithm example .

[2] Thierry Lecroq, Boyer-Moore algorithm .

[3] sealyao, Boyer-Moore算法学习 .

</div>

来自: http://www.cnblogs.com/en-heng/p/5095542.html