动态规划 求解 Minimum Edit Distance

时间:2022-02-06 04:28:11

http://blog.csdn.net/abcjennifer/article/details/7735272

 

自然语言处理(NLP)中,有一个基本问题就是求两个字符串的minimal Edit Distance, 也称Levenshtein distance。受到一篇Edit Distance介绍文章的启发,本文用动态规划求取了两个字符串之间的minimal Edit Distance. 动态规划方程将在下文进行讲解。 

 

简单地说,就是仅通过插入(insert)、删除(delete)和替换(substitute)个操作将一个字符串s1变换到另一个字符串s2的最少步骤数。熟悉算法的同学很容易知道这是个动态规划问题。 

其实一个替换操作可以相当于一个delete+一个insert,所以我们将权值定义如下:

I  (insert):1

D (delete):1

S (substitute):2


2. example:

intention->execution

Minimal edit distance:

delete i ; n->e ; t->x ; insert c ; n->u 求和得cost=8

3.calculate minimal edit distance dynamically
思路见注释,这里D[i,j]就是取s1前i个character和s2前j个character所得minimal edit distance

三个操作动态进行更新:

D(i,j)=min { D(i-1, j) +1, D(i, j-1) +1 , D(i-1, j-1) + s1[i]==s2[j] ? 0 : 2};中的三项分别对应D,I,S。(详见我同学的博客

 

  1. /* 
  2.  * minEditDis.cpp 
  3.  * 
  4.  *  @Created on: Jul 10, 2012 
  5.  *      @Author: sophia 
  6.  *  @Discription: calculate the minimal edit distance between 2 strings 
  7.  * 
  8.  *  Method : DP (dynamic programming) 
  9.  *  D[i,j]: the minimal edit distance for s1的前i个字符和 s2的前j个字符 
  10.  *  DP Formulation: D[i,j]=min(D[i-1,j]+1,D[i,j-1]+1,D[i-1,j-1]+flag);//其中if(s1[i]!=s2[j])则flag=2,else flag=0; 
  11.  * 
  12.  */  
  13.   
  14. #include"iostream"  
  15. #include"stdio.h"  
  16. #include"string.h"  
  17. using namespace std;  
  18.   
  19. #define N 100  
  20. #define INF 100000000  
  21. #define min(a,b) a<b?a:b  
  22.   
  23. int dis[N][N];  
  24. char s1[N],s2[N];  
  25. int n,m;//length of the two string  
  26.   
  27.   
  28. int main()  
  29. {  
  30.     int i,j,k;  
  31.     while(scanf("%s%s",&s1,&s2)!=EOF)  
  32.     {  
  33.         n=strlen(s1);m=strlen(s2);  
  34.         for(i=0;i<=n+1;i++)  
  35.             for(j=0;j<=m+1;j++)  
  36.                 dis[i][j]=INF;  
  37.         dis[0][0]=0;  
  38.   
  39.         for(i=0;i<=n;i++)  
  40.             for(j=0;j<=m;j++)  
  41.             {  
  42.                 if(i>0) dis[i][j] = min(dis[i][j],dis[i-1][j]+1); //delete  
  43.                 if(j>0) dis[i][j] = min(dis[i][j],dis[i][j-1]+1);//insert  
  44.   
  45.                 //substitute  
  46.                 if(i>0&&j>0)  
  47.                 {  
  48.                     if(s1[i-1]!=s2[j-1])  
  49.                         dis[i][j] = min(dis[i][j],dis[i-1][j-1]+2);  
  50.                     else  
  51.                         dis[i][j] = min(dis[i][j],dis[i-1][j-1]);  
  52.                 }  
  53.             }  
  54.   
  55.         printf("min edit distance is: %d\n",dis[n][m]);  
  56.     }  
  57.     return 0;  
  58. }  

 

感谢FallingStar08的提醒,上面最小化的宏定义部分改为

 

  1. #ifndef min  
  2. #define min(a,b) (((a) < (b)) ? (a) : (b))  
  3. #endif  

 

 

运行结果:


intention
execution
min edit distance is: 8
abc
acbfbcd
min edit distance is: 4
zrqsophia
aihposqrz
min edit distance is: 16


另外,xuhanqiu在下面的提示也很有意义:

coursera上老师讲substitute的cost=2默认了substitute = delete+insertion,而这样违反了三角不等式即dis(a,b)+dis(a,c)>dis(b,c),这样一来sustitute就失去了存在的意义,所以如果存在三个基本操作delete,insert和substitute,我们应当把substitute cost改为1,而上面的代码对应于基本操作仅有delete和insertion的情况。当然,实际中有很多变体,具体问题具体分析。

 

Reference: 

1. https://www.coursera.org/course/nlp

2. http://blog.csdn.NET/huaweidong2011/article/details/7727482