4. 编辑距离,又称Levenshtein距离,是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符、插入一个字符、删除一个字符。请设计并实现一个算法来计算两个字符串的编辑距离,并计算其复杂度。在某些应用场景下,替换操作的代价比较高,假设替换操作的代价是插入和删除的两倍,算法该如何调整?
本题可以使用动态规划的方法来解决,具体思路如下:
给定字符串s1,s2,首先定义一个函数D(i,j) (0<=i<=strlen(s1),0<=j<=strlen(s2)),用来表示第一个字符串s1长度为i的子串与第二个字符串s2长度为j的子串的编辑距离。从s1变到s2可以通过如下三种操作:
1)添加操作。假设已经计算出D(i,j-1)的值(s1[0...i]与s2[0...j-1]的编辑距离),则D(i,j)=D(i,j-1)+1(s1长度为i的字串后面添加s2[j]即可)。
2)删除操作。假设已经计算出D(i-1,j)的值(s1[0...i-1]到s2[0...j]的编辑距离),则D(i,j)=D(i-1,j)+1(s1长度为i的字串删除最后的字符s1[j]即可)。
3)替换操作。假设已经计算出D(i-1,j-1)的值(s1[0...i-1]与s2[0...j-1]的编辑距离),如果s1[i]=s2[j],则D(i,j)=D(i-1,j-1),如果s1[i]!=s2[j],则D(i,j)=D(i-1,j-1)+1(替换s1[i]为s2[j],或替换s2[j]为s1[i])。
此外,D(0,j)=j且D(i,0)=i(从一个字符串变成长度为0的字符串的代价为这个字符串的长度)。
由此可以得出如下实现方式:对于给定的字符串s1,s2,定义一个二维数组D,则有以下几种可能性。
1)如果i==0,那么D[i,j]=j(0<=j<=strlen(s2))。
2)如果j==0,那么D[i,j]=i(0<=k=strlen(s1))。
3)如果i>0且j>0,
①如果s1[i]==s2[j],那么D(i,j)=min{ edit(i-1,j)+1,edit(i,j-1)+1,edit(i-1,j-1)}。
②如果s1[i]!=s2[j],那么D(i,j)=min{ edit(i-1,j)+1,edit(i,j-1)+1,edit(i-1,j-1)+1}。
通过以上分析可以发现,对于第一个问题可以直接采用上述的方法来解决。对于第二个问题,由于替换操作是插入或删除操作的两倍,因此,只需要修改如下条件即可:
如果s1[i]!=s2[j],那么D(i,j)=min{ edit(i-1,j)+1,edit(i,j-1)+1,edit(i-1,j-1)+2}。
根据上述分析,给出实现代码如下:
public class EditDistance
{
private int Min(int a, intb, int c)
{
int tmp=a<b?a:b;
return tmp<c?tmp:c;
}
//参数replaceWight用来表示替换操作与插入删除操作相比的倍数
int edit(String s1, String s2, int replaceWight)
{
//两个空串的编辑距离为0
if(s1==null &&s2==null)
rerurn 0;
//如果s1为空串, 则编辑距离为s2的长度
if(s1==null)
return s2.Length;
if(s2==null)
return s1.Length;
int len1=s1.Length;
int len2=s2.Length;
//申请二维数组来存储中间的计算结果
int[,]D=new int[len1+1,len2+1];
int i,j;
for(i=0;i<len1+1;i++)
{
D[i,0]=i;
}
for(i=0;i<len2+1;i++)
{
D[0,i]=i;
}
for(i=1;i<len1+1;i++)
{
for(j=1;j<len2+1;j++)
{
if(s1[i-1]==s2[j-1])
{
D[i,j]-Min(D[i-1,j]+1,D[i,j-1]+1,D[i-1,j-1]);
}
else
{
D[i,j]=Min(D[i-1,j]+1,D[i,j-1]+1, D[i-1,j-1]+replaceWight);
}
}
}
Console.WriteLine("-------------------");
for(i=0;i<len1+1;i++)
{
for(j=0;j<len2+1;j++)
{
Console.Write(D[i,j]+"");
}
Console.WriteLine();
}
Console.WriteLine("--------------------");
int dis=D[len1,len2];
return dis;
}
public static void Main(String[] args)
{
String s1="bciln";
String s2="fciling";
EditDistance ed=new EditDistance();
Console.WriteLine("第一问:");
Console.WriteLine("编辑距离: "+ed.edit(s1, s2, 1));
Console.WriteLine("第二问:");
Console.WriteLine("编辑距: "+ed.edit(s1,s2,2));
Console,Read();
}
}
程序运行结果为:
第一问:
--------------
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 1 2 3 4 5 6
3 3 2 1 2 3 4 5
4 4 3 2 1 2 3 4
5 5 4 3 2 2 2 3
--------------
编辑距离:3
第二问:
--------------
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 2 3 4 5 6 7
3 4 3 2 3 4 5 6
4 5 4 3 2 3 4 5
5 6 5 4 3 4 3 4
--------------
编辑距离:4
算法性能分析:
这个算法的时间复杂度与空间复杂度都为O(m*n)(其中,m,n分别为两个字符串的长度)。
[考点] 如何求字符串的编辑距离