///要求:求串s到串t编辑距离并输出一种编辑方法。
///编辑距离就是用来计算从原串(s)转换到目标串(t)所需要的最少的插入,删除和替换的数目,在NLP中应用比较广泛。
#include <iostream>
#include <string.h>
using namespace std;
//存储操作信息;
struct OperInfo
{
int oper; //操作类型,0:无操作、1:delete,2:insert,3:replace;
int i; //当前操作处于源串第i位;
int j; //当前操作处于目的串第j位;
OperInfo *next;//下一个操作;
};
//第五位表示操作0:无操作、1:delete,2:insert,3:replace;
int doInfo[1000][5]={{0,0,0,0,0}};
int cnt=0;
int count=0;
//求三个数中的最小数
int Minimum(int a, int b, int c)
{
int mi;
mi = a;
if (b < mi)
{
mi = b;
}
if (c < mi)
{
mi = c;
}
return mi;
}
//计算两个字符串间的编辑距离
//原理请参见:http://www.gdcp.cn/jpkc/sjjg/app/jm/edit_distance/problem.htm
int getEditDistance(char *s, char *t) {
int **d; // matrix
int n; // length of s
int m; // length of t
int i; // iterates through s
int j; // iterates through t
char s_i; // ith character of s
char t_j; // jth character of t
int cost; // cost
// Step 1
n = strlen(s);
m = strlen(t);
d=new int*[n+1];
for(i=0;i<=n;i++)
{
d[i]=new int[m+1];
}
if (n == 0) {
return m;
}
if (m == 0) {
return n;
}
// Step 2
for (i = 0; i <= n; i++) {
d[i][0] = i;
}
for (j = 0; j <= m; j++) {
d[0][j] = j;
}
// Step 3
for (i = 1; i <= n; i++) {
s_i = s[i-1];
// Step 4
for (j = 1; j <= m; j++) {
t_j = t[j - 1];
// Step 5
if (s_i == t_j) {
cost = 0;
} else {
cost = 1;
}
// Step 6
//若最后一步为delete操作:则d[i][j]=d[i-1][j]+1;
//若最后一步为insert操作:则d[i][j]=d[i][j-1]+1;
//若cost=0,则不操作。
//若cost=1,则作替换。
d[i][j] = Minimum(d[i - 1][j] + 1, d[i][j - 1] + 1,
d[i - 1][j - 1] + cost);
if (d[i][j]==(d[i - 1][j] + 1))
{
doInfo[cnt][0]=i;
doInfo[cnt][1]=j;
doInfo[cnt][2]=i-1;
doInfo[cnt][3]=j;
doInfo[cnt][4]=1;//delete
cnt++;
}
if (d[i][j]==(d[i][j-1] + 1))
{
doInfo[cnt][0]=i;
doInfo[cnt][1]=j;
doInfo[cnt][2]=i;
doInfo[cnt][3]=j-1;
doInfo[cnt][4]=2;//insert
cnt++;
}
if (d[i][j]==(d[i - 1][j-1] +cost)&&cost==1)
{
doInfo[cnt][0]=i;
doInfo[cnt][1]=j;
doInfo[cnt][2]=i-1;
doInfo[cnt][3]=j-1;
doInfo[cnt][4]=3;//replace
cnt++;
}
if (d[i][j]==(d[i - 1][j-1] +cost)&&cost==0)
{
doInfo[cnt][0]=i;
doInfo[cnt][1]=j;
doInfo[cnt][2]=i-1;
doInfo[cnt][3]=j-1;
doInfo[cnt][4]=0;//no
cnt++;
}
}
}
// Step 7
int result=d[n][m];
//释放二维数组占用的空间
for (i=0;i<=n;i++)
{
delete []d[i];
}
delete []d;
return result;
}
//将操作步聚存储到链表中;
void getOperater(int n,int m,OperInfo *head)
{
int i;
for (i=0;i<100;i++)
{
if(doInfo[i][0]==0&&doInfo[i][1]==0&&doInfo[i][2]==0&&doInfo[i][3]==0&&doInfo[i][4]==0)
break;
if (doInfo[i][0]==n&&doInfo[i][1]==m)
{
OperInfo *node=new OperInfo;
node->oper=doInfo[i][4];
node->i=doInfo[i][0];
node->j=doInfo[i][1];
node->next=head->next;
head->next=node;
if (m==0&&n==0)
break;
getOperater(doInfo[i][2],doInfo[i][3],head);
break;//只取一种实现方式。
}
}
}
void displayDoInfo(OperInfo *head,char *a,char *b)
{
cout<<"其中的一种操作步骤如下:"<<endl;
OperInfo *node=head;
node=node->next;
while(node!=NULL)
{
if (node->oper==0)
{
cout<<"没有操作,直接看下一位"<<endl;
}
if (node->oper==1)
{
count++;
cout<<"第"<<count<<"步--"<<"delete:"<<a[node->i-1]<<endl;
}
if (node->oper==2)
{
count++;
cout<<"第"<<count<<"步--"<<"insert:"<<b[node->j-1]<<endl;
}
if (node->oper==3)
{
count++;
cout<<"第"<<count<<"步--"<<"replace:"<<a[node->i-1]<<"->"<<b[node->j-1]<<endl;
}
node=node->next;
}
/*
int i,j;
for (i=0;i<100;i++)
{
for (j=0;j<5;j++)
{
cout<<doInfo[i][j]<<" ";
}
cout<<endl;
} */
}
void main()
{
char *a="aded";
char *b="acfbe";
int n=strlen(a);
int m=strlen(b);
OperInfo *head=new OperInfo;
head->next=NULL;
cout<<a<<"-->"<<b<<"的编辑距离为:"<<getEditDistance(a,b)<<endl;
getOperater(n,m,head);
displayDoInfo(head,a,b);
}
分享到:
相关推荐
将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。 编程任务: 对于给定的字符串A和字符串B,编程...
编辑距离就是用来计算从原串(s)转换到目标串(t)所需要的最少的插入,删除和替换的数目,在NLP中应用比较广泛,如一些评测方法中就用到了(wer,mWer等),同时也常用来计算你对原文本所作的改动数。编辑距离的算法...
输入任意两个字符串,计算它们的编辑距离。 编辑距离是指两个字符串之间,由一个转换为另一个所需的最少编辑操作次数。许可的编辑操作包括字符的替换、插入和删除。
试验题目:近似字符串匹配问题计算两个字符串s1+ch1, s2+ch2的编辑距离有这样的性质: 1. d(s1,””) = d(“”,s1) = |s1| d(“ch1”,”ch2”) = ch1 == ch2 ? 0 : 1; 2. d(s1+ch1,s2+ch2) = min( d(s1,s2)+ ch1==...
两个字符串的相似度算法实现——编辑距离之Levenshtein距离
自己做的c++的求编辑距离的程序,求插入,删除,替换这几项字符变换产生的编辑距离。
符串A到B 的编辑距离,记为d(A,B)。试设计一个有效算 法,对任给的2 个字符串A和B,计算出它们的编辑距离 d(A,B)。 编程任务: 对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)。 Input 输入由多组测试...
将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。 编程任务: 对于给定的字符串A和字符串B,编程...
解码时声学特性最优的路径蕴含了揭示当前路径是否正确的重要参考信息,为此提出了一种随机段模型系统的解码优化方法。训练能够准确地衡量当前路径与声学最优路径相似性程度的上下文相关音素串编辑距离模型,在N-Best...
编辑距离算法,比较字符串相似度 pb11.5版本
参考清华大学的《算法设计与分析》课后的习题,输入两个字符串后输出其编辑距离。
设A和B是2个字符串.要用最少的字符操作将字符串A转换为字符...将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B).试设计一个有效算法,对任给的2个字符串A和B,计算出他们的编辑距离d(A,B)
编辑距离算法,即Levenshtein ... Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符
Levenshtein:快速计算编辑距离以及字符串的相似度
针对中西文混合字符串,采用了将汉字作为西文字符的等价单位计算编辑距离的方法,并从输入法的角度提出了采用拼音编码和五笔编码计算编辑距离的方法,最后给出了融合三种编辑距离计算字符串相似度的算法。...
计算两个字符串的编辑距离 -- 快速算法
编辑距离就是用来计算从原串(s)转换到目标串 t 所需要的最少的插入 删除和替换的数目 在NLP中应用比较广泛 如一些评测方法中就用到了(wer mWer等) 同时也常用来计算你对原文本所作的改动数 编辑距离的算法是首先...
编辑距离:字符串的相似度 编辑距离的伪算法 java实现
提供html5开发中经常用到html富文本内容的转换插件、可以编辑想编辑的内容并输出以富文本内容的字符串
这是用JS编写的一个编辑距离算法,可以用来在网页中检测语句相似性!检测两个字符串的相似性!