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

widebright的个人空间

// 编程和生活

 
 
 

日志

 
 

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

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

  下载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
  

再看求
ababac的例子
ababac
  ababac
     ^
      比如求最后一位的F[n] 的时候,
      因为ababa的F[n】已经先计算出来了,
      所以先 j = F[i];  初始化一下
           
      p[i] == p[j]) 比较看最后的一个字符是不是能够让匹配部分增加
     
      'c' 不等于'b'了,这时只能退而求其次了,因为知道前面的ababa的最长匹配前缀是aba,就再看这个最长长度的前缀是不是也是ababac的后缀。
      j = F[j];
     
      就是这样比较一下。
ababac
   ababac
     ^
    
     然后不行,继续探测下一个最长前缀( aba 的最长前缀) 是不是ababac 也满足的。
循环下去,最后就可以计算出来F[n] = 0了

========================================================


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 <stdio.h>
#include <stdlib.h>
#include <string.h>



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的比较,,一种不错的方法阿,可以去看一下。


  评论这张
 
阅读(752)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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