【算法分析】ACBM算法分析

时间:2022-11-22 11:13:16

转自:http://blog.csdn.net/joylnwang/article/details/6785743

1977年,Robert S.Boyer和J Strother Moore提出了另一种在O(n)时间复杂度内,完成字符串匹配的算法,其在绝大多数场合的性能表现,比KMP算法还要出色,下面我们就来详细了解一下这一出色的单模式匹配算法,在此之前推荐读者读一下我的另一篇文章《KMP算法详解》,对于透彻理解BM算法大有裨益。

在讲解Boyer-Moore算法之前,我们还是要提一提KMP算法的老例子,当模式串与目标串匹配至如下位置时:

 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
b a b c b a b c a b c a a b c a b c a b c a c a b c
          a b c a b c a c a b                      
我们发现target[13]!=pattern[7],此时根据KMP算法的next值,我们将target[13]与pattern[5]对齐,再依次执行匹配。这里target[13]='a'。如果target[13]='d',因为'd'不是模式串pattern中的字符,所以无论将target[13]与pattern中任何一个字符对齐都会匹配失败,所以当我们在匹配过程中发现target[i]是不属于模式串的字符,则我们可以直接将target[i+1],与pattern[1]对齐,再向后执行匹配。这样就获得了更大的跳转幅度,同时也能保证匹配的正确性。这便是BM算法相较于KMP算法的一个重要改进。

BM算法之所以能够在单模式匹配中有更加出色的表现,主要是其使用了两个跳转表,一个是坏字符表(论文中称为delta1),一个是好后缀表(论文中称为delta2),下面我们以BM算法对目标串的一次匹配操作,来讲解这两个表的具体跳转策略,这里模式串为"AT-THAT",目标串为"WHICH-FINALLY-HALTS.--AT-THAT-POINT"。

   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
  W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T
 1 A T - T H A T                                                        
 2               A T - T H A T                                          
 3                       A T - T H A T                                  
 4                                   A T - T H A T                      
 5                                             A T - T H A T            
BM算法与KMP算法的最大的不同之处在于,当目标串与模式串在某个位置对齐之后,KMP算法是从对齐位置向后依次执行匹配(不一定是模式串的第一个元素)。而BM算法是从模式串的末尾位置(一定是模式串的最后一个元素)向前与目标串依次执行匹配。上面的例子,在4次模式串移动之后,就发现了匹配模式。

第一次,pattern[1]与target[1]对齐,从pattern[7]向前依次与target执行比较,但是第1次比较就发现,target[7]='F',而'F'不是pattern串中的字符,所以target中包含target[7]的任何子串都不可能与pattern匹配,此时我们可以直接将pattern串滑动到target[7]之后,让pattern[1]与target[8]对齐,然后再由target[14]依次向前执行比较。

第二次,target[14]='-',虽然'-'是模式串中的字符,但是如果要target串中包含target[14]的字串与pattern串匹配,则至少target[14]需与pattern中最后一个'-'对齐。而pattern中只有一个'-'pattern[3],所以将target[14],与pattern[3]对齐,然后再由target[18]向前依次执行比较。

第三次,虽然target[18]=pattern[7]='T',但是target[17]='L','L'不是pattern中的字符,所以包含target[17]的任何字串都不可能与pattern匹配,所以pattern[1]直接与target[18]对齐再执行匹配。

第四次,target[23...24]=pattern[6...7],target[22]!=pattern[5],我们注意到,pattern[6...7]=pattern[1...2]所以pattern[1...2]也是模式串的一个自包含后缀(下文详述),所以我们可以令pattern[1]与target[23]对齐再向后执行匹配,此时我们就发现了满足条件的匹配串target[23...29]。

该示例使用到了BM算法中的所有跳转优化,大幅加速了模式串的向后滑动过程,实现了模式的快速匹配,其中第1,2,3次滑动使用的是算法中的坏字符移动规则,第4次滑动使用的是好后缀移动规则,那么什么是所谓的坏字符和好后缀规则呢。

所谓的坏字符移动规则,就是一个表,其以输入字符集的所有字符作为索引,每个输入字符c对应着一个值,表示如果目标串的当前位置字符c与模式串匹配失败,那么目标串当前位置应该可以向前滑动的步数。假设字符集为"ABCDEFGHIJKLMNOPQRSTUVWXYZ-",那么他对应模式串"AT-THAT"的坏字符表为。

  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z -
delta1 1 7 7 7 7 7 7 2 7 7 7 7 7 7 7 7 7 7 7 0 7 7 7 7 7 7 4

坏字符表的定义为,对于输入字符集合中的字符c,如果c不在模式串中,则delta1[c]= patlen(模式串的长度),如果c在模式串中,则delta1[c]=j-i,其中,j是模式串最末元素的索引值,i是字符c在模式串中最右出现的位置(这里与Boyer-Morre两人的论文略有差别,主要是因为BM的论文中,字符串的索引从1开始,其最末元素的索引值,就等于模式串的长度,而在实际计算模式串中含有字符的坏字符滑动值时,使用到的是模式串最末元素的索引值,这个值与模式串的长度不一定相等)。下面就是用于生成坏字符表的代码,为了简单起见,这里没有使用字典结构,而是假设输入的字符只能是A-Z,然后将这26个字符映射到一个数组中。

  1. inline void BuildBadC(const char* pattern, size_t pattern_length, unsigned int* badc, size_t alphabet_size)  
  2. {  
  3.     unsigned int i;  
  4.   
  5.     for(i = 0; i < alphabet_size; ++i)  
  6.     {  
  7.         badc[i] = pattern_length;  
  8.     }  
  9.   
  10.     for(i = 0; i < pattern_length; ++i)  
  11.     {  
  12.         badc[pattern[i] - 'A'] = pattern_length - 1 - i;  
  13.     }  
  14. }  

所谓的好后缀移动规则,是BM算法的核心部分,下面详细说明。在KMP算法中,我们知道了所谓的前缀自包含问题,也就是模式串的前缀也可能是模式串的非前缀子串。在BM算法中,有一个与其非常相似的概念,叫后缀自包含。对于pattern[1...j],存在长度为k的子串,满足pattern[m+1...m+k]=pattern[j-k+1...j],其中k<j,0<m<j-k。以字符串"BCDBCDABCDABCD"为例,pattern[7...10]就是一个包含后缀,因为pattern[7...10]=pattern[11...14]。      

我们定义数组pre[],与pattern中的元素一一对应,对于pattern中的元素,pattern[i],pre[i]是使得pattern[k+1...j-i]=pattern[i+1...j],且pattern[k]!=pattern[i]的k的最大值,如果不存在这样的k,pre[i]=patlen。对于对于模式串的后缀k pattern[j-k+1...j],满足条件的包含后缀可能不止一个,这里我们需要关注所有满足条件的pattern[m+1...m+k]中,满足pattern[m] != pattern[j-k]的m的最大值。对于上例的模式串,其后缀3 pattern[12...14],其包含后缀有pattern[8...10],pattern[4...6],pattern[1...3],在这3个包含后缀中,pattern[7]=pattern[11],所以pattern[8...10]不是我们想要的包含后缀。pattern[0] != pattern[11](这里面我们假设pattern[0]不等于任何可输入字符),pattern[3]!=pattern[11],在这两个备选子串中,pattern[4...6]的m值(3)大于pattern[1...3]的m值(0),所以pattern[4...6]就是我们需要的pre值。对于为什么要满足pattern[m]!=pattern[j-k],请参考我的《KMP算法详解》一文中对于next[j]与f(j)不同之处的解释,以及本文后面算法正确性方面的说明。

现在我们发现了pattern[12...14]在模式串中的包含后缀pattern[4...6],此时如果我们发现目标串target[n]与模式串pattern[11]比较失败,我们就直接可以将pattern[3]与target[n]对齐,然后再从target[n+11]处向前依次与模式串进行匹配。目标串当前位置的跳转距离goods[i]=j-pre[i]。

这里我们需要解释一下如此大幅跳转的正确性。还是以上述模式串为例,当target[n]与pattern[11]匹配失败时,我们需要找到一个适当的位置,令target[n+1...n+3]与pattern[k+1...k+3]相同,才有可能找到匹配结果,这里target[n+1...n+3]=pattern[12...14]。根据pre[i]的定义,只有当k=3时,才能保证pattern[12...14] = pattern[4...6],对于任何k>3都有pattern[12...14] != pattern[k+1...k+3],因为如果存在k>3使得pattern[12...14] = pattern[k+1...k+3],那么pre[11]必然大于3。所以这一对齐方式不会漏过中间可能的匹配。

这里读者可能会有疑问,你说的实际是错的,对于k=7,有target[n+1...n+3]=pattern[8...10],为什么不让target[n]与pattern[7]对齐,然后从target[n+7]位置开始依次向前比较呢?这个问题和KMP算法中next[j]和f(j)的不同之处一样。虽然有pattern[8...10]=pattern[12...14],但是pattern[7]=pattern[11]。因为target[n] != target[11],所以target[n]!=pattern[7]所以将target[n]与pattern[7]对齐所执行匹配尝试必然失败,所以target[n]可以直接跳过pattern[7]直接与pattern[3]对齐。

另一方面,如果target[n]与pattern[k]对齐,但是pattern[k+1...j]在模式串中不存在包含后缀,我们该如何决定模式串向后的滑动距离呢。此时target[n+1...n+j-k] = pattern[k+1...j],因为pattern[k+1...j]不存在包含后缀,所以对于任何m(0<=m<k),pattern[m+1...m+j-k]!=pattern[k+1...j](m<k+1),所以将target[n]与pattern[m]对齐,相当于执行pattern[k+1...j]与pattern[m+1...m+j-k]的匹配,结果必然失败。

此时可以考虑pattern[1]与target[n+1]对齐。pattern[1]与target[n+1]对齐后,pattern[1...j-k]是模式的前缀j-k,target[n+1...n+j-k]相当于pattern[k+1...j],因为pattern[k+1...j]不存在包含子串,所以此次匹配也会失败。继续移动pattern[1],pattern[1]与target[n+2]对齐,此时target[n+2...n+j-k]相当于pattern[1...j-k-1],与pattern[k+2...j]比较,此时两者是否相等依赖于我们之前计算pre表的结果,能够使这个匹配成立的是使pattern[1...m]=pattern[j-m+1...j]的m的最大值,将pattern[1]与target[n+j-k-m+1]对齐,如果这样的m不存在,则pattern[1]可以直接与target[n+j-k+1]对齐,再执行匹配。如下例,当在target[4]处发生匹配失败,根据之前的介绍,pattern[1]与2,3,4,5,6对齐也都会失败,这里j=9,k=4,m=3,n=4。

   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
target A B C D X X A B C . . . . . .
  A B C X X X A B C            
        A B C D X X A B C      
              A B C D X X A B C
根据上面的介绍,我们就可以得出根据pre[i]计算goods[i]的方法,在计算pre值之前,我们先将所有pre[i]初始化为patlen,对于pattern[i],如果不存在m,使得pattern[m+1...m+j-i]=pattern[i+1...j](m<i),且pattern[m]!=pattern[i],则我们不去修改pre[i]的值。计算完所有元素的pre值之后,对于pre[i]!=patlen的情况,goods[i] = j - pre[i],否则,对于pattern[i](j-i<c)的情况goods[i] = patlen+j-i,对于pattern[i](j-i>=c),goods[i]=patlen+j-i-c,其中c是满足pattern[1...c]=pattern[j-c+1...j](c>0)的c的最大值,如果不存在这样的c,c=0。模式中最末元素的goods值固定为1。

   1  2  3  4  5  6  7  8  9 10 11 12 13 14
  B C D B C D A B C D A B C D
pre[i] 14 14 14 14 14 14 14 14 14 14 3 14 14  
goods[i] 24 23 22 21 20 19 18 17 16 15 11 13 12 1
很遗憾,在Boyer-Moore两人的论文中,并没有给出像KMP算法中计算next表那么犀利的算法,所以这里用穷举法给出了一个时间复杂度为O(n^2)的笨法。如果读者有更漂亮的求好后缀表的算法,请指教。

  1. inline void BuildGoodS(const char* pattern, size_t pattern_length, unsigned int* goods)  
  2. {  
  3.     unsigned int i, j, c;  
  4.   
  5.     for(i = 0; i < pattern_length - 1; ++i)  
  6.     {  
  7.         goods[i] = pattern_length;  
  8.     }  
  9.   
  10.     //初始化pattern最末元素的好后缀值  
  11.     goods[pattern_length - 1] = 1;  
  12.   
  13.     //此循环找出pattern中各元素的pre值,这里goods数组先当作pre数组使用  
  14.     for(i = pattern_length -1, c = 0; i != 0; --i)  
  15.     {  
  16.         for(j = 0; j < i; ++j)  
  17.         {  
  18.             if(memcmp(pattern + i, pattern + j, (pattern_length - i) * sizeof(char)) == 0)  
  19.             {  
  20.                 if(j == 0)  
  21.                 {  
  22.                     c = pattern_length - i;  
  23.                 }  
  24.                 else  
  25.                 {  
  26.                     if(pattern[i - 1] != pattern[j - 1])  
  27.                     {  
  28.                         goods[i - 1] = j - 1;  
  29.                     }  
  30.                 }  
  31.             }  
  32.         }  
  33.     }  
  34.   
  35.     //根据pattern中个元素的pre值,计算goods值  
  36.     for(i = 0; i < pattern_length - 1; ++i)  
  37.     {  
  38.         if(goods[i] != pattern_length)  
  39.         {  
  40.             goods[i] = pattern_length - 1 - goods[i];  
  41.         }  
  42.         else  
  43.         {  
  44.             goods[i] = pattern_length - 1 - i + goods[i];  
  45.   
  46.             if(c != 0 && pattern_length - 1 - i >= c)  
  47.             {  
  48.                 goods[i] -= c;  
  49.             }  
  50.         }  
  51.     }  
  52. }  

现在BM算法的两个基本工具坏字符,好后缀都已具备,我们如何在目标串target[1...n]中飞快的找到我们想要的模式pattern[1..j]呢。

首先,我们将pattern[1]与target[1]对齐,然后从target[j]向前依次执行匹配操作。如果在pattern[i]位置发现匹配失败,则在好前缀表里用i查找滑动距离goods[i],在坏字符表中用target[i]做索引,查找滑动距离badc[target[i]],假设前者返回的值为p,后者返回的值为q,这时我们取其中的较大者(假设为p),然后将pattern[j]与target[i+p]对齐,然后依次向前匹配,直到发现匹配,或者遍历整个target串没有找到目标模式为止。下面是BM算法的实现代码,该算法与之前KMP算法一样,都进行了扩展,可以找到目标串中的所有匹配模式,相比之下,BM扩展为找到目标序列中的所有匹配模式串要比KMP简单,不需要引入任何新的东西,只需要在发现匹配模式之后,仍然按照goods[0]移动目标串游标即可。

  1. unsigned int BM(const char* text, size_t text_length, const char* pattern, size_t pattern_length, unsigned int* matches)  
  2. {  
  3.     unsigned int i, j, m;  
  4.   
  5.     unsigned int badc[ALPHABET_SIZE];  
  6.     unsigned int goods[pattern_length];  
  7.   
  8.     i = j = pattern_length - 1;  
  9.     m = 0;  
  10.       
  11.     //构建好后缀和坏字符表  
  12.     BuildBadC(pattern, pattern_length, badc, ALPHABET_SIZE);  
  13.     BuildGoodS(pattern, pattern_length, goods);  
  14.   
  15.     while(j < text_length)  
  16.     {  
  17.         //发现目标传与模式传从后向前第1个不匹配的位置  
  18.         while((i != 0) && (pattern[i] == text[j]))  
  19.         {  
  20.             --i;  
  21.             --j;  
  22.         }  
  23.   
  24.         //找到一个匹配的情况  
  25.         if(i == 0 && pattern[i] == text[j])  
  26.         {  
  27.             matches[m++] = j;  
  28.             j += goods[0];  
  29.         }  
  30.         else  
  31.         {  
  32.             //坏字符表用字典构建比较合适  
  33.             j += goods[i] > badc[text[j]-'A'] ? goods[i] : badc[text[j]-'A'];  
  34.         }  
  35.   
  36.         i = pattern_length - 1;  
  37.     }  
  38.   
  39.     return m;  
  40. }  

后记:

  • 对于进阶的单模式匹配算法而言,子串(前缀/后缀)的自包含,是至关重要的概念,是加速模式匹配效率的金钥匙,而将其发扬光大的无疑是KMP算法,BM算法使用后缀自包含,从后向前匹配模式串的灵感,也源于此,只有透彻理解KMP算法,才可能透彻理解BM算法。
  • 坏字符表,可以用于加速任何的单模式匹配算法,而不仅限于BM算法,对于KMP算法,坏字符表同样可以起到大幅增加匹配速度的效果。对于大字符集的文字,我们需要改变坏字符表的使用思路,用字典来保存模式串中的字符的跳转步数,对于在字典中没有查到的字符,说明其不在模式串中,目标串当前字符直接滑动patlen个字符。