【C语言】编辑距离问题【原创技术】.doc

文档介绍：字符串A通过插入、删除、替换字符变成另一个字符串B,操作的次数表示两个字符串的差异。
用于计算文本相关性、相似性
递归关系
两字符串长度为N、M,对1≤i≤N,1≤j≤M,有
l 若ai=bj 则LD(i,j)=LD(i-1,j-1)
l 若ai≠bj 则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1
求解例
A=GGATCGA,B=GAATTCAGTTA,计算LD(A,B)
实现代码如下:
(代码一)
#include<>
#include<>
int min(int x,int y,int z)
{
int q;
if(x<y&&x<z) q=x;
else if(y<z&&y<x) q=y;
else q=z;
return(q);
}
int LevenshDistance(char strA[],char strB[])
{
int i,j;
int m=strlen(strA)+1;
int n=strlen(strB)+1;
int L[200][200];
for( i=0;i<m;i++)
{L[0]=i;}
for( j=0;j<n;j++)
{L[0][j]=j;}
for(i=1;i<m;i++)
for(j=1;j<n;j++){
if(strA==strB[j]) L[j]=L[i-1][j-1];
else L[j]=min(L[i-1][j-1],L[i-1][j],L[j-1])+1;
}
return L[m-1][n-1];
}
void main()
{
char a[200],b[200];
gets(a);
gets(b);
printf("%d\n",Le
venshDistance(a,b));
}
(代码二)
//题目:编辑距离计算算法
//作者:武叶
//日期:2012年3月28日
#include<>
#include<>
int min_one(int left,int middle,int right) ;
pare_Distance(char strA[],char strB[]);
int main()
{
int distance;
char a[100],b[100];
gets(a); //输入两组字符串
gets(b);
pare_Distance(a,b); //pare_Distance函数计算编辑距离
printf("%d\n",distance);
return 0;
}
int min_one(int left,int middle,int right)
{
int min_one;
if(left<middle&&left<right) min_one=left; //最右边的是最小的一个
else if(middle<right&&middle<left) min_one=middle; //中间的一个是最小的一个
else min_one=left; //右边的是最小的一个
return(min_one