直接递归形式的编辑距离求解(递归过程会产生很多重复计算,所以应该采用动态规划来提高效率)
public class LevenshteinDistance
{
/**
* @param args
*/
public static void main(String[] args)
{
//1
// String str1 = "abc";
// String str2 = "adc";
//2
// String str1 = "ababababa";
// String str2 = "babababab";
//2
// String str1 = "abcd";
// String str2 = "acdb";
//3
String str1 = "kitten";
String str2 = "sitting";
int result = Distance(str1, 0, str1.length()-1, str2, 0, str2.length()-1);
System.out.println(result);
}
public static int Distance(String str1, int begin1, int end1, String str2, int begin2, int end2)
{
//如果第一个已经遍历完了
if(begin1 > end1)
{
//如果第二个也遍历完了
if(begin2 > end2)
{
return 0;
}
//如果第二个还没遍历完(剩余的第二个字符的长度依次删除就可以了)
else
{
return end2 - begin2 + 1;
}
}
//和上面同理
if(begin2 > end2)
{
if(begin1 > end1)
{
return 0;
}
else
{
return end1 - begin1 + 1;
}
}
//如果这两个字符相等,无需操作,均跳到下一个位置比较
if(str1.charAt(begin1) == str2.charAt(begin2))
{
return Distance(str1, begin1 + 1, end1, str2, begin2 + 1, end2);
}
else
{
//删除str1中begin1位置的字符,继续比较str1的begin1+1和str2的begin2(或者在str2的begin2位置前面增加一个字符使之等于str1的begin1)
int value1 = Distance(str1, begin1 + 1, end1, str2, begin2, end2) + 1;
//删除str2中begin2位置的字符,继续比较str2的begin2+1和str1的begin1(或者在str1的begin1位置前面增加一个字符使之等于str2的begin2)
int value2 = Distance(str1, begin1, end1, str2, begin2 + 1, end2) + 1;
//修改str1的begin1位置的字符或者修改str2的begin2位置的字符,使二者相等,然后比较str1的begin1+1和str2的begin2+1
int value3 = Distance(str1, begin1 + 1, end1, str2, begin2 + 1, end2) + 1;
//返回最小值
return min(value1, value2, value3);
}
}
public static int min(int a, int b, int c)
{
int min = a;
if(b<min)
{
min = b;
}
if(c<min)
{
min = c;
}
return min;
}
}
动态规划形式:
public class LDistance
{
/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
String str1 = "kitten";
String str2 = "sitting";
// System.out.println(min(4,5,1));
int result = Distance(str1, str2);
System.out.println(result);
}
public static int Distance(String str1, String str2)
{
int str1Length = str1.length();
int str2Length = str2.length();
if(str1Length == 0)
{
return str2Length;
}
if(str2Length == 0)
{
return str1Length;
}
int[][] d = new int[str1Length + 1][str2Length + 1];
//填写纵向的第一列
for (int i = 0; i < str1Length + 1; i++)
{
d[i][0] = i;
}
//填写横向的第一列
for (int i = 0; i < str2Length + 1; i++)
{
d[0][i] = i;
}
for (int i = 1; i < str1Length + 1; i++)
{
for (int j = 1; j < str2Length + 1; j++)
{
int cost = 0;
if(str1.charAt(i-1) != str2.charAt(j-1))
{
cost = 1;
}
//在str1上i位置删除字符(或者在str2上j-1位置插入字符)
d[i][j] = min(d[i-1][j] + 1,
//在str1上i-1位置插入字符(或者在str2上j位置删除字符)
d[i][j-1] + 1,
// 替换操作
d[i-1][j-1] + cost);
}
}
return d[str1Length][str2Length];
}
public static int min(int a, int b, int c)
{
int min = a;
if(b<min)
{
min = b;
}
if(c<min)
{
min = c;
}
return min;
}
}
分享到:
相关推荐
这是 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==...