加权编辑距离

在词项独立的矫正方法中，有一种叫做编辑距离的方法。

给定两个字符串s1和s2，两者的编辑距离定义为将s1转换成s2的最小编辑操作数。

这些编辑操作包括：

1. 将一个字符插入字符串中
2. 将一个字符从字符串中删除
3. 将字符串中的一个字符替换为另外一个字符

对于加权的编辑距离，假定删除一个字符的权重为delCost，替换字符的权重定义为键盘上按键的曼哈顿距离dist[i][j]，插入一个字符的代价为insertCost。

于是有

dp[i][j] = min(min(dp[i-1][j-1]+if(s1[i]==s2[j]) then 0 else dist[i][j],dp[i-1][j]+delCost),del[i][j-1]+delCost);

对于边界有dp[i][0] = i ; dp[0][j] = j * insertCost;

附代码如下：

//karsbin 2012.11.13
/*
*加权编辑距离，动态规划
*在搜索引擎拼写矫正中，通过键盘按键的曼哈顿距离给编辑距离赋权值
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
const int maxn = 1024 ;
int dist[32][32] ;
int dp[maxn][maxn] ;
int delCost = 6 ;	//删除一个字符的代价
int insertCost = 6 ;//插入一个字符的代价
char dict[][11] = {"qwertyuiop","asdfghjkl*","zxcvbnm***"};
//计算键盘按键的权值，对于其他权值，可通过给dist赋值实现
void calcWeidht()
{
int i , j , x , y ;
for( i = 0 ; i < 3 ; i++)
{
for ( j = 0 ; j < 10 ; j++)
{
if ( dict[i][j] == '*' )
{
break ;
}
//计算dict[i][j]和其他元素的权值
for ( x = 0 ; x < 3 ; x++)
{
for ( y = 0 ; y < 10 ; y++) if( dict[x][y] != '*' )
{
dist[dict[i][j]-'a'][dict[x][y]-'a'] = abs(i-x)+abs(j-y);
}
}
}
}
}
inline int get_min(int a,int b)	{	return a < b ? a : b ;	}
//计算A，B的编辑距离，假定长度 < maxn-1
int calcEditDist(char A[],char B[])
{
int lenA = strlen(A);
int lenB = strlen(B);
int i , j ;
//初始化边界
for( i = 1 ; i <= lenA ; i++)
{
dp[i][0] = i * insertCost ;
}
for ( j = 1 ; j <= lenB ; j++)
{
dp[0][j] = j * insertCost ;
}
//dp
for ( i = 1 ; i <= lenA ; i++)
{
for ( j = 1 ; j <= lenB ; j++)
{
int changeCost = (A[i-1]==B[j-1]?0:dist[tolower(A[i-1])-'a'][tolower(B[j-1])-'a']) ;
dp[i][j] = get_min(dp[i-1][j]+delCost,get_min(dp[i][j-1]+delCost,dp[i-1][j-1]+changeCost));
}
}
return dp[lenA][lenB];
}
int main()
{
char strA[maxn] , strB[maxn] ;
calcWeidht();
while (~scanf("%s%s",strA,strB))
{
printf("%s和%s的编辑距离为：%dn",strA,strB,calcEditDist(strA,strB));
}
}

最后

以上就是无私睫毛为你收集整理的加权编辑距离的全部内容，希望文章能够帮你解决加权编辑距离所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。