Boyer-Moore算法的C实现

     Boyer-Moore算法是一个文本字符串搜索算法。和暴力搜索算法相比，它充分利用待搜索字符串的一些特征，加快了搜索的步骤。

    首先来介绍基本概念。我们待搜素的文本称之为 text，我们想寻找的字符串叫pattern。显然文本text很长，我们从很长的文本搜索我们关心的关键字pattern。

    首先最容易想到的办法就是暴力搜索，从头到尾，挨个比较，如果和pattern字符串不一致，右移一位，再次比较。

int Naive_search(char text[],int textlen,char pattern[],int patternlen)
{
    int i ;
    int find = 0;
    for(i = 0;i<(textlen - patternlen);i++)
    {
         if(memcmp(&(text[i]),pattern,patternlen) == 0)
         {
                   find++;
                   FindThePattern(text,pattern,i);
         }

    }
        return find;
}

     暴力搜索最容易想到，但是它的效率太低。本文下面介绍Boyer-Moores算法。

     Boyer-Moore的思想是这样的，通过预处理，获取pattern字符串的一些特征，通过这些特征，来减少不必要的比较。Boyer-Moore主要有两个启发策略来减少不必要的比较。

     Boyer-Moore 算法扫描比较字符串是从右向左比较。和普通的从左到右的习惯有写不同，这种扫描有什么好处，大家理解了这个算法就明白了。

1   Bad Character  坏字符

    看下面的字符串搜索，在文本“abbadabacbmnpbac”中搜索babac，我们按照从右到左的比较，text为d，而pattern为c，不匹配，按照暴力搜索的思想，我们应该右移一位，继续比较，如下图中的naive。再次比较text中的a 和pattern中的c。

    但是我们注意观察下，就可以发现，上一轮比较中text中的d，在pattern字符串中根本就不存在，你右移一位，现在pattern中“babac”的倒数第二位a需要和text中的进行比较。很明显仍然不可能匹配，因为pattern中根本就没有d这个字符，无论那一位和d比较，都不会匹配，所以右移一位太保守，并没有充分利用pattern中的信息。看下图中BM哪一行，直接向右移动patternlen位。

   OK，根据BM算法，我们安全移动到了第九位。发现text 为b，pattern为 c，不匹配，很不幸，这次b这个字符在pattern中存在，我们是不是只能移动一位呢。不一定，我们看到必须试图寻找和文本中的9位置的b重合的位置，pattern中的存在两个b。安全的策略是pattern最右边b的和*位置的b匹配，

换句话说，可以右移两位，如果右移4为，那就太激进了，容易漏掉某些匹配的项。

----------------------------------------------------------------------------------------

  

             0 1 2 3 4 5 6 7 8 9 A B C D E F

text         a b b a d a b a c b m n p b a c  

pattern      b a b a c
naive          b a b a c                         (太保守，进行不必要的比较)

BM                     b a b a c 

BM                             b a b a c         (太激进，可能漏掉)

BM                         b a b a c 

                                      *             

text          x y a c d e f
pattern       a q b c d e f
bm                a q b c d e f

详解：

f e d c 都已经匹配，第一个不匹配的是a，寻找pattern最右边的a与text中的a对齐。

text            x y c c d e f

pattern         c a b c d e f

BM            c a b c d e f         错误的办法（走了回头路）

BM                c a b c d e f

详解：

f e d c都已经匹配，按照前面的方法，应该寻找pattern最右边的c和text的蓝色的ｃ对齐，但是pattern左移才能满足最右边的ｃ与text中ｃ对齐，这种情况下，肯定不能走回头路，简单的右移一位就可以了。

  

----------------------------------------------------------------------------------------

    通过上面的分析我们可以看出，要想利用坏字符的启发策略，我们需要几下每个字符最右边一次出现的位置。

   1  没出现过的字符一律定为pattern的长度。

   2  pattern中出现过的字符，最后一次出现该字符的位置 i。

    下面给出函数

#define __CHAR_MAX (255)

int preBM_bad(char* pattern ,int len,int rightmost_occur[])
{
    int i;
    for(i = 0;i<__CHAR_MAX;i++)
        rightmost_occur[i] = len;
    for(i = 0;i<len;i++)
    {
        rightmost_occur[pattern[i]] = i;
    }
    return 0;
}

2 好后缀启发策略 good suffix shift

    假如说，pattern的后u个字符和text都已经匹配了，但是接下来的一个字符不匹配，如下图所示，我需要移动才能匹配。如果说后u个字符在pattern其他位置也出现过，这种情况非常好，我们将pattern右移到前面的u个字符和最后的u个字符相同

text           a b w u t u q y x a b c d m n p q x

pattern        n w a b c d p m n a b c d 

BM                           n w a b c d p m n a b c d                                               

    另外一种情况是pattern 的最前r个字符和最后r个字符是一模一样的，这种情况也会给我们带来额外的信息。

             

                                               

                                                      *  

text           a b w u t u q m n a b c d m n p q x

pattern            a b c d p m n a b c d 

BM                               a b c d p m n a b c d

 为了利用good suffix，我们需要先计算suffix。

1  suffix[patternlen-1] = patternlen;

2  suffix[i] = k  

    for [ pattern[i-k+1] ....,pattern[i]] == [pattern[patternlen-1-k+1]，pattern[patternlen-1]] 

   如下图，

 

pattern        n w a b c d p m n a b c d
suffix  0 0 0 0 0 4 0 0 0 0 0 0 13

 

上代码

int calc_goodsuffix(char* pattern,int len,int suffix[])
{
    int i,j,k;
    int result;
    suffix[len-1] = len;

    for(i = len-2;i>=0;i--)
    {
        k = i;
        j=len-1;
        result = 0;
        while(pattern[k--]==pattern[j--])
        {
            result++;
        }
        suffix[i] = result;
    }
    return 0;
}

int preBM_good(char* pattern ,int len,int goodskip[])
{
    int i,j;
    int *suffix = malloc(len*sizeof(int));
    if(suffix == NULL)
    {
        printf("malloc failed for preBM_good\n ");
        return -1;
    }

    calc_goodsuffix(pattern,len,suffix);

    for(i = 0;i<len;i++)
    {
          goodskip[i] = len;
    }
    j = 0;
    /*最前和最后的i+1个字符一致*/
    for(i = len-2;i>=0;--i)
    {
        if(suffix[i] == i+1)  /*consider the pattern "ABCDMNPABCD"*/
        {
           for(;j<len-1-i;j++)
           {
                if(goodskip[j] == len) /*consider the pattern BBBBMNPBBBB*/
              {
                    goodskip[j] = len-1-i;
              }
            }
        }
    }

    for(i = 0;i<len-2;i++)
    {
          goodskip[len-1-suffix[i]] = len-1-i;
    }

    if(suffix)
       free(suffix);
    return 0;

}

最后给出boyer-moore算法的主函数

int BM_search(char* text,int textlen,char* pattern,int patternlen)
{
    int i,j;
    int ret;
    int rightmost[__CHAR_MAX];
    int find = 0;
    int badskip;

    int *goodskip = malloc(sizeof(int)*patternlen) ;
    if(goodskip == NULL)
    {
        printf("malloc for goodskip failed\n");
        return -1;
    }

    preBM_bad(pattern ,patternlen,rightmost);
    ret = preBM_good(pattern,patternlen,goodskip);
    if(ret != 0)
    {
        printf("preBM_good failed\n");
        return -2;
    }

    j = 0;
    while(j < textlen - patternlen)
    {
        for(i = patternlen-1;i>=0 && pattern[i] == text[j+i];i--)
        {
           ;
        }
        if(i<0)
        {
              FindThePattern(text,pattern,j);
              j += goodskip[0];
              find++;
        }
        else
        {
            if(i - rightmost[text[j+i]] >0)
                badskip = i - rightmost[text[j+i]];
            else
                badskip = 1;/*不走回头路*/

            j+=Max(goodskip[i],badskip);
        }
    }

    if(goodskip)
    {
          free(goodskip);
    }
    return find;
}

参考文献：

１　

２　Boyer-Moore 经典单模式匹配算法

３  Michael Abrash Graphics Programming Black Book