一、定义
定义：将一个字符串转换成另一个字符串时需要付出的代价。转换可以采用插入、删除和替换三种编辑方式，转换的代价就是对字符串的编辑次数，不同的转换方法需要的编辑次数也不一样，最少的那个编辑次数就是字符串的编辑距离。
二、算法实现
递归算法实现：
int edit_distance(char *src, char *dest)
{
if((0==strlen(src) || (0==strlen(dest))
return abs(strlen(src)-strlen(dest));
if ((dest[0]==src[0]))
return edit_distance(src+1,dest+1);
int insertion=edit_distance(src,dest+1)+1;
int deletion=edit_distance(src+1,dest)+1;
int replace=edit_distance(src+1,dest+1)+1;
return min(min(insetion,deletion),replace);
}
动态规划算法实现：
typedef struct dynamic_programming
{
long int distance;//编辑距离，初始化为0xFFFF，表示一个无效状态
long int reference_count;//记录状态被应用的次数，0表示没有这个状态记录
}dp;
long int s_maxoflength=strlen(src);
long int t_maxoflenght=strlen(dest);
dp memory[s_maxoflenth][t_maxoflenth];
memory[0][0].distance=0xFFFF;
memory[0][0].reference_count=0;
int edit_distance(char *src,char *dest,int i,int j)
{
if(0!=memory[i][j].referece_count)
{
memory[i][j].reference_count++;
return memory[i][j].distance;
}
int distance=0;
if(0==strlen(src+i))
{
distance=strlen(dest+j);
}
else if (0==strlen(dest+j))
{
distance=strlen(src+i);
}
else
{
if(src[i]==dest[j]) distance=edit_distance(src,dest,i+1,j+1);
else
{
int insertion=edit_distance(src,dest,i,j_1)+1;
int deletion=edit_distance(src,dest,i+1,j)+1;
int replace=edit_distance(src,dest,i+1,j+1)+1;
distance=min(min(insertion,deletion),replace);
}
}
memory[i][j].distance=distance;
memorty[i][j].reference_count=1;
}
确定了递推关系和边界条件的动态规划算法：
int edit_distance(char *src,char *dest)
{
int d[s_maxoflenth][t_maxoflenth]={0xFFFF};
for(long int i=0;i<=strlen(src);i++) d[i][0]=i;
for(long int j=0;j<=strlen(dest);j++) d[0][j]=j;
for(long int i=1;i<=strlen(src);i++)
{
for(long int j=1;j<=strlen(dest);j++)
{
if(src[i-1]==dest[j=1]) d[i][j]=d[i-1][j-1];
else
{
int insertion=d[i][j-1]+1;
int deletion=d[i-1][j]+1;
int replace=d[i-1][j-1]+1;
d[i][j]=min(min(insertion,deletion),replace);
}
}
}
return d[strlen(src)][strlen(dest)];
}
评论