注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

widebright的个人空间

// 编程和生活

 
 
 

日志

 
 

我的猪脑袋是怎么理解KMP字符串匹配算法的  

2011-07-19 17:15:46|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
以前也在数据结构的书上大概看过KMP字符串匹配算法,不过不怎么认真看。最近又在网上看到了,就认真去看了一下,结果发现我的猪脑袋,怎么都理解不了。于是就到网上搜索了相关资料,看了很多篇文章好像都不得要领阿,写的都不好, 直到看到这篇 “MP/KMP 算法详解 [草稿]” http://www.if-yu.info/2010/08/21/mp-and-kmp.html 然后又去看了作者引用的一篇英文的“Introduction to String Searching Algorithms Rabin-Karp and Knuth-Morris-Pratt Algorithms ” http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching   这外国人写的明显比中国人写的好理解啊!我这猪脑袋也终于可以看的懂理解了。随便说一下,“MP/KMP 算法详解 ”里面写的函数明显没有英文那篇写的代码容易理解,像我一样智商的同学还是看的英文的容易理解一些呵呵!   下面把我的理解说一下,希望以后忘记了的时候可以来这里看一下:-) 我尝试着按照自己理解用代码实现出来,然后简单测试了一下,下次应该不那么容易忘记了吧?  首先写了个暴力的匹配函数,估计每个人都可以写的出来吧。 int naive_match (char s[], char p[], int m , int n) {      int i=0,j=0;      for (i = 0; i< m - n + 1; i++) {                   int ii = i;           for ( j = 0; j< n;j++) {                 if (s[ii] == p[j]) {                       printf("s[%d] == p[%d]\n",ii,j);                             ii++;                                                if (j + 1 == n) {                          return i;                       }                                } else {                     printf("s[%d] != p[%d]\n",ii,j);                          break;                 }              }             }               return -1; }   然后去看KMP的资料,像前面说的一样,书上讲的好像都不那么容易理解啊。  KMP算法说是在某个牛人证明“自动状态机”的某个上面定理说是匹配都可以在线性时间完成之后才诞生的。然后几个牛人就用这个状态机的理论弄出了这么一个KMP 字符串算法。 “麻省理工学院-算法导论.Introduction.to.Algorithms" 一书在前面也先举了“自动状态机”的匹配例子,但好像也不怎么容易理解啊,反正我是理解不了啦。  其实这东西可以这么理解:  比如在字符串中abadbabc 查找字符串ababac ------------- s[i]  abadbabc p[j]  ababac          ^ -------------   像上面字符串查找时,字符串比较到 s[3] = 'd' 和 p[3] = ‘b' 不匹配的时候,如果是上面写的暴力匹配函数,将移动字符串进行继续比较 像下面这样比较 s[1] 与 p[0] ------------- s[i]  abadbabc p[j]   ababac        ^ ----------------        但KMP的算法高级的地方就是他跳过暴力匹配的几个步骤,直接比较 s[3]  = 'd'与 p[1] = ‘b'  。像下面这样。  ------------- s[i]  abadbabc p[j]    ababac          ^ ----------------     整个匹配过程p 不断向右边滑动。因为KMP 高明的地方就是他有一个滑动指针数组F【】,可以在 p[3] 比较失败的时候,调整j 为 F[3],因为F[3] = 1 ,所以比较失败的下一步就是 比较s[i]与p[3].  用代码写出来就是  next: if (s[i] != p[j] ) {       j = F[j]       goto next;        }  所有我预先知道 这个数组F[] 是这样的 F[0] =0 F[1] =0 F[2] =0 F[3] =1 F[4] =2 F[5] =3 F[6] =0  然后我就可以自己写乎KMP算法的匹配过程了   int kmp (char s[], char p[], int m , int n) {          int i=0,j=0;            for ( ; ;) {                 if ( i>=m) break;  //到了字符串末尾了                                  if (s[i] == p[j]) {                                   printf("s[%d] == p[%d]\n",i,j);                                                       i++;                         j++;                                               if (j == n) {                          return i - n;  //匹配整个长度了, 返回匹配的位置                       }                                } else if( j > 0){  /// 当 j 为 0的时候, s[i] 与 p[0]都比较失败了,这时就需要调整i了,作下一个匹配尝试                       printf("s[%d] != p[%d]\n",i,j);                           j = F[j];    ///这个时候 j 是不匹配的                                                  } else {                        printf("s[%d] != p[%d]\n",i,j);                           i++;                 }                }                             return -1; }   这个神奇的数组F[n]是怎么计算出来的呢? 其实就是只和p[n】相关的一个属性,可以在kmp算法的前面预先计算出来。  其实这个F[n] 对应的值就是 p[0] 到p[n] 这个字符串的 前缀字符串中和后缀字符串中相等的最长的长度就是F[n]的值。  -------------- ababaddddd ababac      ^ -------------- 像上面比较最后一个字符c的比较失败了,KMP调整下一个指针的过程,其实就是在已经匹配的长度“ababa”这个字符串 自己匹配自己的过程,可以尝试自己理解一下。 关于前缀与后缀的定义可以参考“麻省理工学院-算法导论.Introduction.to.Algorithms" 一书。  列出 ababa 的所有前缀字符串(prefix)有: a              p[0] ab             p[0,1] aba            p[0,1,2] abab           p[0,1,2,3] ababa          p[0,1,2,3,4]  列出 ababa 的所有后缀字符串(suffix)有: a            p[4] ba           p[3,4] aba          p[2,3,4] baba         p[1,2,3,4] ababa        p[0,1,2,3,4]   在所有的子串里面有 abab    p[0,1,2,3] 不等于 abab p[0,1,2,3]   "aba   p[0,1,2]"  等于 "aba  p[2,3,4]"  这个相等的长度是是最长的所以有 F[strlen("ababa")] = strlen("aba") = 3  ----------------- ababaddddddddddd ababac      ^            所以 上面匹配失败的时候,下面这些都不需要尝试了 ababaddddddddddd  ababac  ^^^^  我们事先知道 'abab" 这个前缀和 “baba”这个后缀是不匹配了的了   ababaddddddddddd     ababac     ^^          我们事先知道 'ab" 这个前缀和 "ba”这个后缀是不匹配了的了       我们应该尝试的是这个匹配,因为我们比较过所有的后缀和前缀,“aba” 这个长度是最长的   ababaddddddddddd     ababac     ^^^        ^       --------------------  我们同样的办法来处理ababac 就可以得到整个F[n]数组了  比如 F[3] 有  aba  a    长度等于1的 后缀与前缀相等 ab   长度等于2的 后缀与前缀不等 aba  a ba aba  所以 F[3] = 1  再如F[4]  abab  a ab   长度等于1的 后缀与前缀相等 aba abab  b    不等 ab   长度等于2的 后缀与前缀相等 bab  不等 abab  所以F[4]= 2  ---------------   只要理解 这个计算F[n]的过程就是寻找所有后缀和前缀相等的最长字符串的过程,那么你也就可以把代码写出来了。 值的注意的KMP算法中的F【n】的尝试过程:  比如 ababaddddddddddd ababac      ^            失败我们去尝试       ababaddddddddddd   ababac   ^^^      ^    j= F[strlen(‘ababad“)= 3      然后再次失败了       ababaddddddddddd   ababac     ^^^      ^      j= F[strlen(‘ababad“)= 3     ababac     ^      ^      j= F[strlen(‘aba“) = 1         ---------------------------  我们的整个尝试过程是 先试 j= F[5]  这个是最长 然后 在尝试 j=F[F[5]]  如果j=F[F[5]] 不等于0的话 就还要继续j= F[F[F[5]]] 的尝试。    ===================================== 好了来看看最后完成的计算F[n]  数组的函数吧。  //寻找一个字符串的 所有的前缀字符串所有后缀中 前缀和后缀相等的最大长度 static  int  F[1000]; void caculate_jump( char p[],  int n) {                F[0] = F[1] =0;                  int i =0,j=0;         for (i = 1; i <= n; i++){                              if ( i > n) break;                                                       j = F[i];                              for (;;) {                     if ( p[i] == p[j]){                             F[i+1] = j+1;  // 这里的F[i+1]   是为了kmp函数里不用写F[j-1]   直接写  F[j]                            break;                     }                                            if(j == 0) { F[i+1] = 0; break; }   // 这里的F[i+1]   是为了kmp函数里不用写F[j-1]   直接写  F[j]                       j = F[j];                }                                                       }                  }        是不是很容易理解?  如果最后一个字符相等就能够让前缀后缀匹配的长度增加,那么F【n]就加1 abab   ^    i = 2       ababac  ^  j = F[2] = 0        因为 p[i] == p[j] ,所以F[3]= j+1 = 1  ----- abab    ^    i = 3          ababac   ^    j = F[3] = 1      因为 p[i] == p[j] ,所以 F[4]= j+1 = 2     ========================================================   KMP的继续改进 按照KMP算法,如果下面这个匹配失败 ababdddddddd ababac     ^ 那么 就要尝试     ababdddddddd   ababac     ^  但这个可能也是失败的了,因为我们上一步就是比较 ‘d' 和 ’a‘字符,这次又继续比较‘d' 和 ’a‘    显然不用再进行这个测试了! 所以我们如果知道p[2] ==p[4] ='a' 的情况下 ab[a]b[a] ,我们就可以跳过这个  j=F[4]=2的比较,而是直接移动到下一个j =F[F[4]]=0    可以直接跳到这个比较来进行了 ababdddddddd     ababac     ^           根据这个思想,我们在改进一下我们计算F[n] 的函数,可以得到       void caculate_jump_enhance( char p[],  int n) {                F[0] = F[1] =0;                  int i =0,j=0;         for (i = 1; i <= n; i++){                              if ( i > n) break;                                                               j = F[i];                                              for (;;) {                     if ( p[i] == p[j]){                                                      if (p[i+1] == p[j+1] ){                                printf("F[%i] = F[%d]\n",i+1,j+1);                                  F[i+1] = F[j+1];                                  i++;                               j++;                               continue;                          } else {                              F[i+1] = j+1;  // 这里的F[i+1]   是为了kmp函数里不用写F[j-1]   直接写  F[j]                            }                             break;                     }                                            if(j == 0) { F[i+1] = 0; break; }  // 这里的F[i+1]   是为了kmp函数里不用写F[j-1]   直接写  F[j]                       j = F[j];                }                                                       }                 }     代码写的比较乱,但还是比较容易理解的。 可以整理成好看一点的形式,不过理解起来就没那么容易了,所以我就保留现在这样的了。   最后完整的测试代码是这样的       ----------------------------------------------------------------- #include  #include  #include     int naive_match (char s[], char p[], int m , int n) {      int i=0,j=0;      for (i = 0; i< m - n + 1; i++) {                   int ii = i;           for ( j = 0; j< n;j++) {                 if (s[ii] == p[j]) {                       printf("s[%d] == p[%d]\n",ii,j);                             ii++;                                                if (j + 1 == n) {                          return i;                       }                                } else {                     printf("s[%d] != p[%d]\n",ii,j);                          break;                 }              }             }               return -1; }  //寻找一个字符串的 所有的前缀字符串所有后缀中 前缀和后缀相等的最大长度 static  int  F[1000]; void caculate_jump( char p[],  int n) {                F[0] = F[1] =0;                  int i =0,j=0;         for (i = 1; i <= n; i++){                              if ( i > n) break;                                                       j = F[i];                              for (;;) {                     if ( p[i] == p[j]){                             F[i+1] = j+1;  // 这里的F[i+1]   是为了kmp函数里不用写F[j-1]   直接写  F[j]                            break;                     }                                            if(j == 0) { F[i+1] = 0; break; }   // 这里的F[i+1]   是为了kmp函数里不用写F[j-1]   直接写  F[j]                       j = F[j];                }                                                       }                  }   void caculate_jump_enhance( char p[],  int n) {                F[0] = F[1] =0;                  int i =0,j=0;         for (i = 1; i <= n; i++){                              if ( i > n) break;                                                               j = F[i];                                              for (;;) {                     if ( p[i] == p[j]){                                                      if (p[i+1] == p[j+1] ){                                printf("F[%i] = F[%d]\n",i+1,j+1);                                  F[i+1] = F[j+1];                                  i++;                               j++;                               continue;                          } else {                              F[i+1] = j+1;  // 这里的F[i+1]   是为了kmp函数里不用写F[j-1]   直接写  F[j]                            }                             break;                     }                                            if(j == 0) { F[i+1] = 0; break; }  // 这里的F[i+1]   是为了kmp函数里不用写F[j-1]   直接写  F[j]                       j = F[j];                }                                                       }                 }   int kmp (char s[], char p[], int m , int n) {          int i=0,j=0;            for ( ; ;) {                 if ( i>=m) break;  //到了字符串末尾了                                  if (s[i] == p[j]) {                                   printf("s[%d] == p[%d]\n",i,j);                                                       i++;                         j++;                                               if (j == n) {                          return i - n;  //匹配整个长度了, 返回匹配的位置                       }                                } else if( j > 0){                       printf("s[%d] != p[%d]\n",i,j);                           j = F[j];    ///这个时候 j 是不匹配的                                                  } else {                        printf("s[%d] != p[%d]\n",i,j);                           i++;                 }                }                             return -1; }  int main(int argc,char **argv) {    char a[] =  "abadbabcefgabababacefababa";    char b[] =  "ababac";       int i  = naive_match(a,b,strlen(a),strlen(b));         printf ("i=%d\n" , i);        caculate_jump(b,strlen(b));    for (i =0;i< 7;i++)    {       printf ("F[%d] =%d\n" , i,F[i]);    }    i  = kmp(a,b,strlen(a),strlen(b));         printf ("i=%d\n" , i);           caculate_jump_enhance(b,strlen(b));       for (i =0;i< 7;i++)    {       printf ("F[%d] =%d\n" , i,F[i]);    }    i  = kmp(a,b,strlen(a),strlen(b));          printf ("i=%d\n" , i);    return 0; }        -------------------------------------------------------------           执行一下,KMP算法是不是比常规的暴力匹配要少用几次比较呢! 可以弄多点测试来看看。     ./a.out  s[0] == p[0] s[1] == p[1] s[2] == p[2] s[3] != p[3] s[1] != p[0] s[2] == p[0] s[3] != p[1] s[3] != p[0] s[4] != p[0] s[5] == p[0] s[6] == p[1] s[7] != p[2] s[6] != p[0] s[7] != p[0] s[8] != p[0] s[9] != p[0] s[10] != p[0] s[11] == p[0] s[12] == p[1] s[13] == p[2] s[14] == p[3] s[15] == p[4] s[16] != p[5] s[12] != p[0] s[13] == p[0] s[14] == p[1] s[15] == p[2] s[16] == p[3] s[17] == p[4] s[18] == p[5] i=13 -------------------------- F[0] =0 F[1] =0 F[2] =0 F[3] =1 F[4] =2 F[5] =3 F[6] =0 s[0] == p[0] s[1] == p[1] s[2] == p[2] s[3] != p[3] s[3] != p[1] s[3] != p[0] s[4] != p[0] s[5] == p[0] s[6] == p[1] s[7] != p[2] s[7] != p[0] s[8] != p[0] s[9] != p[0] s[10] != p[0] s[11] == p[0] s[12] == p[1] s[13] == p[2] s[14] == p[3] s[15] == p[4] s[16] != p[5] s[16] == p[3] s[17] == p[4] s[18] == p[5] ------------------------ i=13 F[3] = F[1] F[4] = F[2] F[0] =0 F[1] =0 F[2] =0 F[3] =0 F[4] =0 F[5] =3 F[6] =0 s[0] == p[0] s[1] == p[1] s[2] == p[2] s[3] != p[3] s[3] != p[0] s[4] != p[0] s[5] == p[0] s[6] == p[1] s[7] != p[2] s[7] != p[0] s[8] != p[0] s[9] != p[0] s[10] != p[0] s[11] == p[0] s[12] == p[1] s[13] == p[2] s[14] == p[3] s[15] == p[4] s[16] != p[5] s[16] == p[3] s[17] == p[4] s[18] == p[5] i=13         整个弄完,再去看一下书“麻省理工学院-算法导论.Introduction.to.Algorithms",好像写的也挺简单的嘛,怎么我之前就理解不了呢?猪阿,就是猪阿!  随便说一下书上讲的 Rabin-Karp Algorithm (RK) 算法也是不错的,把几个字符的比较转换成一个int的比较,,一种不错的方法阿,可以去看一下。   
  评论这张
 
阅读(478)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017