详解编辑距离问题(动态规划)

朴灿烈づ我的快乐病毒、 2022-04-23 22:56 383阅读 0赞

### 问题描述: ###

对于序列S和T, 它们之间的距离定义为: 对二者其一进行几次以下操作: 1, 删除一个字符; 2, 插入一个字符; 3, 改变一个字符. 每进行一次操作, 计数增加1. 将S和T变为相等序列的最小计数就是两者的编辑距离(edit distance)或者叫相似度. 请给出相应算法及其实现.

### 分析: ###

**最优解的结构分析**

假设序列S和T的长度分别为m和n, 两者的编辑距离表示为edit\[m\]\[n\]. 则对序列进行操作时存在以下几种情况:

1.  当S和T的末尾字符相等时, 对末尾字符不需要进行上述定义操作中(亦即"编辑")的任何一个, 也就是不需要增加计数. 则满足条件: edit\[m\]\[n\] = edit\[m - 1\]\[n - 1\].
2.  当S和T的末尾字符不相等时, 则需要对两者之一的末尾进行编辑, 相应的计数会增加1.
    
        ① 对S或T的末尾进行修改, 以使之与T或S相等, 则此时edit[m][n] = edit[m - 1][n - 1] + 1;
        
         ②删除S末尾的元素,或者在T末尾添加元素, 使S与T相等, 则此时edit[m][n] = edit[m - 1][n] + 1;
        
         ③删除T末尾的元素, 或者在T末尾添加元素, 使T与S相等, 则此时edit[m][n] = edit[m][n - 1] + 1;
3.  比较特殊的情况是, 当S为空时, edit\[0\]\[n\] = n; 而当T为空时, edit\[m\]\[0\] = m; 这个很好理解, 例如对于序列"“和"abc”, 则两者的最少操作为3, 即序列""进行3次插入操作, 或者序列"abc"进行3次删除操作.

**最优值的递推公式**  
![在这里插入图片描述][20190409215807700.png]  
**求最优解**  
最优值中的最大值

### 代码 ###

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    #define N 9999
    char a[N],b[N];
    int f[N][N];
    int main()
    { 
    
    	cin>>a;
    	cin>>b;
    	int m=strlen(a);
    	int n=strlen(b);
    	for(int i=1;i<=n;i++)
    		f[i][0]=i;
    	for(int j=1;j<=n;j++)
    		f[0][j]=j;
    	for(int i=1;i<=m;i++)
    	{ 
    		for(int j=1;j<=n;j++)
    		{ 
    			if(a[i-1]==b[j-1])
                   f[i][j]=f[i-1][j-1];
    			else
    			   f[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;
    		}
    	}cout<<f[m][n];
    
    }

[20190409215807700.png]: /images/20220222/5f79a4dba8fb44f4823f9e9826191f0b.png