最短编辑距离

编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。

例如两个字符串 “main” 和 “mian”,从前一个字符串变成后一个串,需要先删除一个字符 ‘ a ’ ,然后再在字符 ‘ i ‘ 后面加一个 ‘ a ‘ ,那么他们的最短编辑距离就为2。

求解这类问题的方法一般为动态规划。

不加权最短编辑距离

这是最基本的裸题,只求字符串操作次数。

假设当前第一个串位置为 i ,第二个串位置为 j ,dp[ i ][ j ] 表示最短编辑距离。

我们看一下三种操作:替换,插入,删除

替换

​ 如果仅仅是替换,假设我们已经求出来了 dp[ i - 1 ][ j - 1 ] , 那么从dp[ i - 1 ][ j - 1 ] 到 dp[ i ][ j ] $只操作了一次,即 dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] +1 。

插入

​ 如果插入后串的长度分别为 i , j ,那么当前状态可以是从 i - 1 , j 的情况下第一个串插入一个字符得到的,因此 dp[ i ][ j ]= dp[ i - 1 ][ j ] + 1 ;

删除

​ 删除同上,当前状态可以是从 i , j - 1 的情况下删除了一个字符得到的,因此dp[ i ][ j ]= dp[ i ][ j - 1 ] + 1 ;

这就是三种状态分别对应的状态方程,特殊的,当 i = 0 或 j = 0 时,最短编辑距离就是当前两个串的差值,即另一个变量对应的值。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
//字符串数组下标从1开始

//初始化i=0或j=0的情况。
for(int i=0;i<=n;i++) dp[i][0]=i;
for(int j=0;j<=m;j++) dp[0][j]=j;

//四种状态 按顺序为:删除,插入,字符匹配(不需要编辑),替换
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+(a[i]==b[j]?0:1));
}
}

加权最短编辑距离

省赛原题:

多组输入

第一行输入四个数 a,b,c,d,表示字符匹配加 a 分,替换减b分,插入减c分,删除减d分。

接下来两行,每行一个字符串。

输出最大得分。

这个题其实也算是编辑距离的裸题,当时状态方程写了出来,但是不知道为什么wa了(可能还是不熟悉)。

加权的转移方程其实和不加权的差不多,只是在转移方程的加减上做了一点变化。

代码如下:

1
2
3
4
5
6
7
8
9
//由于对应的权值不同,初始化的值也不同
for(int i=0;i<=n;i++) dp[i][0]=-i*d;
for(int j=0;j<=m;j++) dp[0][j]=-j*c;

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=max(max(dp[i-1][j]-c,dp[i][j-1]-d),dp[i-1][j-1]+(s1[i]==s2[j]?a:-b));
}
}
感谢您的支持
-------------本文结束感谢您的阅读-------------