一、问题描述
设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括:
<wbr>(1)删除一个字符;</wbr>
<wbr>(2)插入一个字符;</wbr>
<wbr>(3)将一个字符改为另一个字符;</wbr>
<wbr>将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的两个字符串A和B,计算出它们的编辑距离d(A,B)。</wbr>
<wbr></wbr>
二、分析解答
设所给的两个字符串为A[1:m]和B[1:n]。定义D[i][j]=d(A[1:i],B[1,j])。单字符a,b间的距离定义为:
d(a,b)=0 (a=b)
d(a,b)=1(a!=b)
考察从字符串A[1:i]到字符串B[1:j]的变换。可分成以下几种情况:
(1)字符A[i]改为字符B[j];需要d(A[i],B[j])次操作。
(2)删除字符A[i];需要1次操作。
(3)插入字符B[j];需要1次操作。
因此,D[i][j]可递归地计算如下。
D[i][j]=min{D[i-1][j-1]+d(A[i],B[j]),D[i-1][j]+1,D[i][j-1]+1}。
<wbr></wbr>
三、算法描述
int dist(A[0…m-1],B[0…n-1])
{
int D[0…m,0…n]
int i,j,cost
对于i等于0至m
D[i, 0]=i
对于j等于0至n
D[0,j]=j
对于i等于1至m
<wbr><wbr><wbr>对于j等于1至n</wbr></wbr></wbr>
<wbr><wbr><wbr><wbr><wbr><wbr>若 A[i-1]=B[j-1]则cost=0 否则 cost=1</wbr></wbr></wbr></wbr></wbr></wbr>
<wbr><wbr><wbr><wbr><wbr><wbr><wbr>D[i][j]=min(D[i-1,j]+1,//删除</wbr></wbr></wbr></wbr></wbr></wbr></wbr>
<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>D[i,j-1]+1,//插入</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>D[i-1,j-1]+cost//替换</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>)</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
返回d[m,n]
}
<wbr></wbr>
四、代码实现
定义一个二维数组D[][]存储中间结果,如下图所示,为已经初始化后的情况。然后从D[1,1]开始从左到右,从上到下依次按填表,表的最后一个元素D[m,n]就是要求的最终结果。
<wbr></wbr>
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
0
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
1
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
2
|
2
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
3
|
3
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
4
|
4
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
5
|
5
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
6
|
6
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
|
<wbr></wbr>
#include<iostream>
#include<string>
using namespace std;
int D[100][100];
int dis[100];
int min(int a,int b,int c)
{
return c<(a>b?b:a)?c:(a>b?b:a);
}
int dist(char * A,char * B)
{
int m=strlen(A);
int n=strlen(B);
int i,j;
for(i=0;i<=m;++i)
{
D[i][0]=i;
}
for(j=0;j<=n;++j)
{
D[0][j]=j;
}
int cost;
for(i=1;i<=m;++i)
{
for(j=1;j<=n;++j)
{
if(A[i-1]==B[j-1])
cost=0;
else
cost=1;
D[i][j]=min(D[i-1][j-1]+cost,D[i-1][j]+1,D[i][j-1]+1);
}
}
return D[m][n];
}
int dist2(char * A,char * B)
{
int m=strlen(A);
int n=strlen(B);
int i,j;
for(i=0;i<=n;++i)
dis[i]=i;
int cost;
for(i=1;i<=m;++i)
{
int y=i-1;
for(j=1;j<=n;++j)
{
int x=y;
y=dis[j];
int z=j>1?dis[j-1]:i;
cost=A[i-1]==B[j-1]?0:1;
dis[j]=min(x+cost,y+1,z+1);
}
}
return dis[n];
}
int main(int argc, char* argv[])
{
char * ch1="bcdefghijklmnopq";
char * ch2="abcdefghijklmnopadfsafwe";
cout<<dist(ch1,ch2)<<endl;
cout<<dist2(ch1,ch2)<<endl;
return 0;
}
package net.hr.algorithm.stroper;
/**
* 字符串编辑距离
*
* 这是一种字符串之间相似度计算的方法。
* 给定字符串S、T,将S转换T所需要的插入、删除、替代操作的数量叫做S到T的编辑路径。
* 其中最短的路径叫做编辑距离。
*
* 这里使用了一种动态规划的思想求编辑距离。
*
* @author heartraid
*
*/
public class StrEditDistance {
/**字符串X*/
private String strX="";
/**字符串Y*/
private String strY="";
/**字符串X的字符数组*/
private char[] charArrayX=null;
/**字符串Y的字符数组*/
private char[] charArrayY=null;
public StrEditDistance(String sa,String sb){
this.strX=sa;
this.strY=sb;
}
/**
* 得到编辑距离
* @return 编辑距离
*/
public int getDistance(){
charArrayX=strX.toCharArray();
charArrayY=strY.toCharArray();
return editDistance(charArrayX.length-1,charArrayY.length-1);
}
/**
* 动态规划解决编辑距离
*
* editDistance(i,j)表示字符串X中[0.... i]的子串 Xi 到字符串Y中[0....j]的子串Y1的编辑距离。
*
* @param i 字符串X第i个字符
* @param j 字符串Y第j个字符
* @return 字符串X(0...i)与字符串Y(0...j)的编辑距离
*/
private int editDistance(int i,int j){
if(i==0&&j==0){
//System.out.println("edit["+i+","+j+"]="+isModify(i,j));
return isModify(i,j);
}
else if(i==0||j==0){
if(j>0){
//System.out.println("edit["+i+","+j+"]=edit["+i+","+(j-1)+"]+1");
if(isModify(i,j) == 0) return j;
return editDistance(i, j-1) + 1;
}
else{
//System.out.println("edit["+i+","+j+"]=edit["+(i-1)+","+j+"]+1");
if(isModify(i,j) == 0) return i;
return editDistance(i-1,j)+1;
}
}
else {
//System.out.println("edit["+i+","+j+"]=min( edit["+(i-1)+","+j+"]+1,edit["+i+","+(j-1)+"]+1,edit["+(i-1)+","+(j-1)+"]+isModify("+i+","+j+")");
int ccc=minDistance(editDistance(i-1,j)+1,editDistance(i,j-1)+1,editDistance(i-1,j-1)+isModify(i,j));
return ccc;
}
}
/**
* 求最小值
* @param disa 编辑距离a
* @param disb 编辑距离b
* @param disc 编辑距离c
*/
private int minDistance(int disa,int disb,int disc){
int dismin=Integer.MAX_VALUE;
if(dismin>disa) dismin=disa;
if(dismin>disb) dismin=disb;
if(dismin>disc) dismin=disc;
return dismin;
}
/**
* 单字符间是否替换
*
* isModify(i,j)表示X中第i个字符x(i)转换到Y中第j个字符y(j)所需要的操作次数。
* 如果x(i)==y(j),则不需要任何操作isModify(i, j)=0; 否则,需要替换操作,isModify(i, j)=1。
* @param i 字符串X第i个字符
* @param j 字符串Y第j个字符
* @return 需要替换,返回1;否则,返回0
*/
private int isModify(int i,int j){
if(charArrayX[i]==charArrayY[j])
return 0;
else return 1;
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
System.out.println("编辑距离是:"+new StrEditDistance("eeba","abac").getDistance());
}
}
<wbr></wbr>
五、优化方法
从上面算法可以看出,该算法时间复杂性为0(m*n),空间复杂性为O(m*n)。同时可以看出,当对第i行进行填表时,只需要用到第i-1行的数据,因此可以用一个一维数组dis[0…n]代替二维数组D[0…m,0…n],因此空间复杂性降为O(n)。实现代码如上面函数dist2()所示。
分享到:
相关推荐
这是 APTED 算法的 Python 实现,它是计算树编辑距离的最先进的解决方案 ,它取代了 RTED 算法 输入 目前,我们只支持输入树的所谓括号表示法,例如,编码{A{B{X}{Y}{F}}{C}}对应于以下树: A / \ B C /|\ X Y...
将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。 编程任务: 对于给定的字符串A和字符串B,编程...
将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。 编程任务: 对于给定的字符串A和字符串B,编程...
Problem A:编辑距离问题 Description 设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。 将...
自己做的c++的求编辑距离的程序,求插入,删除,替换这几项字符变换产生的编辑距离。
编辑距离问题-算法导论.pdf
编辑距离算法,即Levenshtein Distance (LD)算法。 这个算法其实是一个动态规划(DP)。levenshtein() 返回两个字符串之间的 Levenshtein 距离。 Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个...
SQL SERVER实现编辑距离(Edit Distance)算法,可进行模糊匹配查询
编辑距离的动态规划实现,C/C++,直接可以使用,设:A字符串为a[0:m-1],B字符串为b[0:n-1]; d[i][j]表示a[0]到a[i]变化为b[0]b[j]的编辑距离; 则有: {█(d[i][j]=d[i-1]d[j-1],a[i]=b[j]@min┬█(0≤i≤m-1,@0≤j...
输入任意两个字符串,计算它们的编辑距离。 编辑距离是指两个字符串之间,由一个转换为另一个所需的最少编辑操作次数。许可的编辑操作包括字符的替换、插入和删除。
编辑距离(EditDistance)定义 编辑距离就是用来计算从原串(s)转换到目标串(t)所需要的最少的插入,删除和替换的数目,在NLP中应用比较广泛,如一些评测方法中就用到了(wer,mWer等),同时也常用来计算你对原...
我的上机实验 编辑距离原代码 根据<算法导论>编的
利用动态规划算法解决编辑距离,在度量空间中有编辑距离这一个概念,通常利用动态规划等算法进行解决
如果是A串的第i个字符和B串的第j个字符 1.在A的第i个字符后插入一个字符B[j],问题转化为计算A[i...lenA]和B[j+1...lenB]的距离 ...d [i-1][j] 、d [i][j-1]、d [i-1][j-1]进行比较,其中最小的就是当前A和B的编辑距离
训练能够准确地衡量当前路径与声学最优路径相似性程度的上下文相关音素串编辑距离模型,在N-Best重打分的过程中将音素串编辑距离加入到路径总得分中。在“863-test”测试集上进行的连续语音识别实验显示汉语字的相对...
设A和B是2个字符串.要用最少的字符操作将字符串A转换为字符...将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B).试设计一个有效算法,对任给的2个字符串A和B,计算出他们的编辑距离d(A,B)
动态规划之编辑距离问题
编辑距离用来计算两个字符串的相似度。Oracle中提供了相应的函数,但是在Sql server中没有找到,因此到国外网站上copy来一个网友编写的T-SQL版的编辑距离函数。
这是用JS编写的一个编辑距离算法,可以用来在网页中检测语句相似性!检测两个字符串的相似性!
试验题目:近似字符串匹配问题计算两个字符串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==...