BM和KMP模式匹配算法原理.doc

BM模式匹配算法原理（图解）首先，先简单说明一下有关BM算法的一些基本概念。BM算法是一种精确字符串匹配算法（区别于模糊匹配）。BM算法采用从右向左比较 的方法，同时应用到了两种启发式规则，即坏字符规则 和好后缀规则 ，来决定向右跳跃的距离。BM算法的基本流程: 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较 ，如下图所示: 若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则 和好后缀规则 ，来计算模式串向右移动的距离，直到整个匹配过程的结束。 下面，来详细介绍一下坏字符规则 和好后缀规则 。 首先，诠释一下坏字符和好后缀的概念。 请看下图： 图中，第一个不匹配的字符（红色部分）为坏字符，已匹配部分（绿色）为好后缀。 1）坏字符规则（Bad Character）： 在BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论： i. 如果字符x在模式P中没有出现，那么从字符x开始的m个文本显然不可能与P匹配成功，直接全部跳过该区域即可。 ii. 如果x在模式P中出现，则以该字符进行对齐。 用数学公式表示，设Skip(x)为P右移的距离，m为模式串P的长度，max(x)为字符x在P中最右位置。 例1： 下图红色部分，发生了一次不匹配。 计算移动距离Skip(c) = 5 - 3 = 2，则P向右移动2位。 移动后如下图： 2）好后缀规则（Good Suffix）： 若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论： i. 如果在P中位置t处已匹配部分P在P中的某位置t也出现，且位置t的前一个字符与位置t的前一个字符不相同，则将P右移使t对应t方才的所在的位置。 ii. 如果在P中任何位置已匹配部分P都没有再出现，则找到与P的后缀P相同的P的最长前缀x，向右移动P，使x对应方才P后缀所在的位置。 用数学公式表示，设Shift(j)为P右移的距离，m为模式串P的长度，j 为当前所匹配的字符位置，s为t与t的距离（以上情况i）或者x与P的距离（以上情况ii）。 以上过程有点抽象，所以我们继续图解。例2： 下图中，已匹配部分cab（绿色）在P中再没出现。 再看下图，其后缀T（蓝色）与P中前缀P（红色）匹配，则将P移动到T的位置。 移动后如下图： 自此，两个规则讲解完毕。 在BM算法匹配的过程中，取SKip(x)与Shift(j)中的较大者作为跳跃的距离。 BM算法预处理时间复杂度为O（m+s），空间复杂度为O(s)，s是与P, T相关的有限字符集长度，搜索阶段时间复杂度为O(mn)。最好情况下的时间复杂度为O(n/m)，最坏情况下时间复杂度为O(mn)。(二)所谓精确字符串匹配问题，是在文本 T 中找到所有与查询P 精确匹配的子串。而 BM 算法可以非常有效地解决这个问题，让时间复杂度降到低于线形的水平。 BM 算法主要用了三种巧妙而有效的方法，即从右到左扫描，坏字符规则和好后缀规则。 从右到左扫描的意思是从最后一个字符开始向前匹配，而不是习惯上的从开头向后匹配。 坏字符规则是，从右到左的扫描过程中，发现 Ti 与 Pj 不同，如果P 中存在一个字符 Pk 与 Ti 相同，且 ki 那么就将直接将 P 向右移使 Pk 与 Ti 对齐，然后再从右到左进行匹配。如果 P 中不存在任何与 Ti 相同的字符，则直接将 P 的第一个字符与 Ti 的下一个字符对齐，再从右到左进行比较。 如图： T： a b c b a d f t a t e P： c b a x a d P： c b a x a d 用 R(x) 表示字符 x 在 P 中出现的最右位置，此例中 R(b)=2。 可以看出使用从右到左扫描和坏字符规则可以跳过 T 中的很多位置不去检查，从而使时间复杂度低于线性。 好后缀规则是，从右到左的扫描过程中，发现 Ti 与 Pj 不同，检查一下相同的部分t 是否在 P 中的其他位置 t 出现，a) 如果 t 与 t 的前一个字母不相同，就将 P 向右移，使t 与 T 中的 t 对齐。b) 如果t 没有出现，则找到与t 的后缀相同的 P 的最长前缀 x，向右移动P ，使x 与 T 中t 的后缀相对应。 如图a)：N： 1N： 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 T： a b c b a d f tbcf a q v t b c e. P： c b c a b c e a b c P：c bc a b c e a b c f 可见，并不是将 P 向右移让 P5 与 T9 对齐，而是让 P2 与 T9 对齐，因为 P1 与 P8 不相同。用 L(i) 表示 t 的最大位置，此例中， L(9)= 3。 如图b)：N： 1N： 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 T： a b c b a d f tbcf a q v t b c e. P：bc c a b c et b c P： bc c a b c et b c 可见，当 P 向左找不到 “tbc”时，就找到 “tbc”的最长与 P 的前缀匹配的后缀，并将 P 向右移。用l(i) 表示这个最长后缀的长度，这个例子中 i=8。 整个算法是这样的：预处理 输入查询字符串 P， 计算 P 中每个位置的 L(i) 和 l(i)，并计算 R(i)。查询 k:=n; / n 是 T 中字符的总数 while k0 and P(i)=T(i) do begin i:=i-1; h:=h-1; end; if i=0 then begin 输出 T 的这个位置上的字符串； k:= k+n-l(2);end else 移动 P(增加 k)，k 取 好后缀规则和坏字符规则决定的最大值 end; 预处理阶段可以根据上一篇文章提到的 Zbox 方法进行处理，时间复杂度为线性。 整个算法的时间复杂度最坏的情况是 O(m)，m 是 T 的长度。(三)BM算法的基本思想是从右向左进行比较。开始时仍是P(Pattern)的最左边与S(String)的最左边对齐，但首先进行Pm与Tm的比较。当某趟比较中出现不匹配时，BM算法采用两条启发性规则计算模式串右移的距离，即坏字符规则和好后缀规则。 1) 坏字符规则（Bad Character） P中的某个字符与T中的某个字符不相同时使用坏字符规则右移模式串P， P右移的距离可以通过delta1函数计算出来。delta1函数的定义如下: delta1(x) = - m; xPj (1 = j = m)，即x在P中未出现 | - m - maxk|Pk = x, 1 = k s)在匹配过程中，取delta1和delta2中的大者。BM算法的最坏时间复杂度为O(m*n)，但实际比较次数只有文本串长度的20%30%。*BM字符串匹配算法从snort2.2的mstring.c中整理而来*#include #include * 生成skip数组，即delta1数组*int *make_skip(char *ptrn, int plen)int *skip = (int *)malloc(256 * sizeof(int);int *sptr = skip + 256;if (skip = NULL) fprintf(stderr, malloc failed!);while (sptr- != skip) *sptr = plen + 1;while (plen != 0) skip(unsigned char)*ptrn+ = plen-;return skip;* 生成shift数组，即delta2数组*int *make_shift(char *ptrn, int plen)int *shift = (int *)malloc(plen * sizeof(int);int *sptr = shift + plen - 1;char *pptr = ptrn + plen - 1;char c;if (shift = NULL) fprintf(stderr, malloc failed!);c = ptrnplen - 1;*sptr = 1;while (sptr - != shift) char *p1 = ptrn + plen - 2, *p2, *p3; do while (p1 = ptrn & *p1- != c); p2 = ptrn + plen - 2; p3 = p1; while (p3 = ptrn & *p3- = *p2- & p2 =pptr); while (p3 = ptrn & p2 = pptr); *sptr = shift + plen - sptr + p2 - p3; pptr-;return shift;* 搜索函数*int mSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)int b_idx = plen;if (plen = 0) return 1;while (b_idx = blen) int p_idx = plen, skip_stride, shift_stride; while (buf-b_idx = ptrn-p_idx) if (b_idx shift_stride) ? skip_stride : shift_stride;return 0;int main()char str100 = faecabcxxdefeabcxxxabcdwaw;char pattern10 = abcxxxabc;int *skip, *shift, i;skip = make_skip(pattern, strlen(pattern);shift = make_shift(pattern, strlen(pattern);if (!mSearch(str, strlen(str), pattern, strlen(pattern), skip, shift) printf(The string %s doesnt contain string %sn, str, pattern);else printf(The string %s does contain string %sn, str, pattern);return 0; KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。一.简单匹配算法先来看一个简单匹配算法的函数：int Index_BF ( char S , char T , int pos ) /* 若串 S 中从第pos(S 的下标0posS0!= S1,S1 != S2,所以S1!= T0,S2 != T0.还是从理论上间接比较了。有人疑问又来了，你分析的是不是特殊轻况啊。假设S不变，在S中搜索T=“abaabd”呢？答：这种情况，当比较到S2和T2时，发现不等，就去看next2的值，next2=-1，意思是S2已经和T0 间接比较过了，不相等，接下来去比较S3和T0吧。假设S不变，在S中搜索T=“abbabd”呢？答：这种情况当比较到S2和T2时，发现不等，就去看next2的值，next2=0，意思是S2已经和T2比较过了，不相等，接下来去比较S2和T0吧。假设S=”abaabcabdabba”在S中搜索T=“abaabd”呢？答：这种情况当比较到S5和T5时，发现不等，就去看next5的值，next5=2，意思是前面的比较过了，其中，S5的前面有两个字符和T的开始两个相等，接下来去比较S5和T2吧。总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值nextn呢？（本文中next值、模式函数值、模式值是一个意思。）三. 怎么求串的模式值nextn定义：（1）next0= -1意义：任何串的第一个字符的模式值规定为-1。（2）nextj= -1 意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1k个字符与开头的1k个字符不等（或者相等但Tk=Tj）（1kj）。如：T=”abCabCad” 则 next6=-1，因T3=T6 （3）nextj=k 意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且Tj != Tk （1kj）。 即T0T1T2。Tk-1=Tj-kTj-k+1Tj-k+2Tj-1 且Tj != Tk.（1kj）;(4) nextj=0 意义：除（1）（2）（3）的其他情况。举例：01）求T=“abcac”的模式函数的值。 next0= -1根据（1） next1=0 根据 (4) 因（3）有1=kj;不能说，j=1,Tj-1=T0 next2=0 根据 (4) 因（3）有1=k0 但kn, 表示,Sm的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较Sm和Tk相等吗？4. 其他值，不可能。四. 求串T的模式值nextn的函数说了这么多，是不是觉得求串T的模式值nextn很复杂呢？要叫我写个函数出来，目前来说，我宁愿去登天。好在有现成的函数，当初发明KMP算法，写出这个函数的先辈，令我佩服得六体投地。我等后生小子，理解起来，都要反复琢磨。下面是这个函数:void get_nextval(const char *T, int next) / 求模式串T的next函数值并存入数组 next。 int j = 0, k = -1; next0 = -1; while ( Tj/*+1*/ != 0 ) if (k = -1 | Tj = Tk) +j; +k; if (Tj!=Tk) nextj = k; else nextj = nextk; / if else k = nextk; / while /这里是我加的显示部分 / for(inti=0;ij;i+) / / coutnexti; / /coutendl;/ get_nextval另一种写法，也差不多。void getNext(const char* pattern,int next) next0= -1; int k=-1,j=0; while(patternj!=0) if(k!=-1&patternk!=patternj ) k=nextk; +j;+k; if(patternk=patternj) nextj=nextk; else nextj=k; /这里是我加的显示部分 / for(inti=0;ij;i+) / / coutnexti; / /coutendl; 下面是KMP模式匹配程序，各位可以用他验证。记得加入上面的函数#include #include int KMP(const char *Text,const char* Pattern) /const 表示函数内部不会改变这个参数的值。 if( !Text|!Pattern|Pattern0=0|Text0=0 )/ return -1;/空指针或空串，返回-1。 int len=0; const char * c=Pattern; while(*c+!=0)/移动指针比移动下标快。 +len;/字符串长度。 int *next=new intlen+1; get_nextval(Pattern,next);/求Pattern的next函数值 int index=0,i=0,j=0; while(Texti!=0& Patternj!=0 ) if(Texti= Patternj) +i;/ 继续比较后继字符 +j; else index += j-nextj; if(nextj!=-1) j=nextj;/ 模式串向右移动 else j=0; +i; /while delete next; if(Patternj=0) return index;/ 匹配成功 else return -1; int main()/abCabCad char* text=bababCabCadcaabcaababcbaaaabaaacababcaabc; char*pattern=adCadCad; /getNext(pattern,n); /get_nextval(pattern,n); coutKMP(text,pattern)endl; return 0; 五其他表示模式值的方法上面那种串的模式值表示方法是最优秀的表示方法，从串的模式值我们可以得到很多信息，以下称为第一种表示方法。第二种表示方法，虽然也定义next0= -1,但后面绝不会出现-1，除了next0，其他模式值nextj=k(0kj)的意义可以简单看成是：下标为j的字符的前面最多k个字符与开始的k个字符相同，这里并不要求Tj != Tk。其实next0也可以定义为0（后面给出的求串的模式值的函数和串的模式匹配的函数，是next0=0的），这样，nextj=k(0kj)的意义都可以简单看成是：下标为j的字符的前面最多k个字符与开始的k个字符相同。第三种表示方法是第一种表示方法的变形，即按第一种方法得到的模式值，每个值分别加1，就得到第三种表示方法。第三种表示方法，我是从论坛上看到的，没看到详细解释，我估计是为那些这样的编程语言准备的：数组的下标从1开始而不是0。下面给出几种方法的例子： 表一。下标012345678Tababcaabc(1) next-10-102-1102(2) next -1 0 0 1 2 0 1 1 2 (3) next 0 1 0 1 3 0 2 1 3 第三种表示方法,在我看来，意义不是那么明了，不再讨论。 表二。 下标01234TabcAc(1)next-100-11(2)next -1 0 0 0 1 表三。下标01234567TadCadCad(1)next-100-100-10(2)next -1 0 0 0 1 2 3 4 对比串的模式值第一种表示方法和第二种表示方法，看表一：第一种表示方法next2= -1,表示T2=T0，且T2-1 !=T0 第二种表示方法next2= 0,表示T2-1 !=T0,但并不管T0 和T2相不相等。第一种表示方法next3= 0,表示虽然T2=T0，但T1 =T3 第二种表示方法next3= 1,表示T2 =T0,他并不管T1 和T3相不相等。第一种表示方法next5= -1,表示T5=T0，且T4 !=T0，T3T4 !=T0T1，T2T3T4 !=T0T1T2 第二种表示方法next5= 0,表示T4 !=T0，T3T4 !=T0T1 ，T2T3T4 !=T0T1T2，但并不管T0 和T5相不相等。换句话说：就算T5=x,或 T5=y,T5=9,也有next5= 0 。从这里我们可以看到：串的模式值第一种表示方法能表示更多的信息，第二种表示方法更单纯，不容易搞错。当然，用第一种表示方法写出的模式匹配函数效率更高。比如说，在串S=“adCadCBdadCadCad 9876543”中匹配串T=“adCadCad”, 用第一种表示方法写出的模式匹配函数,当比较到S6 != T6 时，取next6= -1（表三）,它可以表示这样许多信息： S3S4S5=T3T4T5=T0T1T2，而S6 != T6，T6=T3=T0，所以S6 != T0,接下来比较S7和T0吧。如果用第二种表示方法写出的模式匹配函数,当比较到S6 != T6 时，取next6= 3（表三）,它只能表示：S3S4S5= T3T4T5=T0T1T2，但不能确定T6与T3相不相等，所以，接下来比较S6和T3;又不相等，取next3= 0，它表示S3S4S5= T0T1T2，但不会确定T3与T0相不相等，即S6和T0 相不相等，所以接下来比较S6和T0，确定它们不相等，然后才会比较S7和T0。是不是比用第一种表示方法写出的模式匹配函数多绕了几个弯。为什么，在讲明第一种表示方法后，还要讲没有第一种表示方法好的第二种表示方法？原因是：最开始，我看严蔚敏的一个讲座，她给出的模式值表示方法是我这里的第二种表示方法，如图：她说：“next 函数值的含义是：当出现Si !=Tj时，下一次的比较应该在Si和Tnextj之间进行。”虽简洁，但不明了，反复几遍也没明白为什么。而她给出的算法求出的模式值是我这里说的第一种表示方法next值，就是前面的get_nextval()函数。匹配算法也是有瑕疵的。于是我在这里发帖说她错了：/Expert/topic/4413/4413398.xml?temp=.2027246 现在看来，她没有错，不过有张冠李戴之嫌。我不知道，是否有人第一次学到这里，不参考其他资料和明白人讲解的情况下，就能搞懂这个算法（我的意思是不仅是算法的大致思想，而是为什么定义和例子中nextj=k(0kj)，而算法中nextj=k(-1kj)）。凭良心说：光看这个讲座，我就对这个教受十分敬佩，不仅讲课讲得好，声音悦耳，而且这门课讲得层次分明，恰到好处。在KMP这个问题上出了点小差错，可能是编书的时候，在这本书上抄下了例子，在那本书上抄下了算法，结果不怎么对得上号。因为我没找到原书，而据有的网友说，书上已不是这样，也许吧。说起来，教授们研究的问题比这个高深不知多少倍，哪有时间推演这个小算法呢。总之，瑕不掩玉。书归正传，下面给出我写的求第二种表示方法表示的模式值的函数,为了从S的任何位置开始匹配T，“当出现Si !=Tj时，下一次的比较应该