Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明,用他的名字命名。不会拼读,可以叫它edit distance(编辑距离)。
原理很简单,就是返回将第一个字符串转换(删除、插入、替换)成第二个字符串的编辑次数。次数越少,意味着字符串相似度越高
Levenshtein distance可以用来:
Spell checking(拼写检查)
Speech recognition(语句识别)
DNA analysis(DNA分析)
Plagiarism detection(抄袭检测)
LD用m*n的矩阵存储距离值。算法大概过程:
java 代码实现:
/**
* 编辑距离的两字符串相似度
*
* @author jianpo.mo
*/
public class SimilarityUtil {
private static int min(int one, int two, int three) {
int min = one;
if(two < min) {
min = two;
}
if(three < min) {
min = three;
}
return min;
}
public static int ld(String str1, String str2) {
int d[][]; //矩阵
int n = str1.length();
int m = str2.length();
int i; //遍历str1的
int j; //遍历str2的
char ch1; //str1的
char ch2; //str2的
int temp; //记录相同字符,在某个矩阵位置值的增量,不是0就是1
if(n == 0) {
return m;
}
if(m == 0) {
return n;
}
d = new int[n+1][m+1];
for(i=0; i<=n; i++) { //初始化第一列
d[i][0] = i;
}
for(j=0; j<=m; j++) { //初始化第一行
d[0][j] = j;
}
for(i=1; i<=n; i++) { //遍历str1
ch1 = str1.charAt(i-1);
//去匹配str2
for(j=1; j<=m; j++) {
ch2 = str2.charAt(j-1);
if(ch1 == ch2) {
temp = 0;
} else {
temp = 1;
}
//左边+1,上边+1, 左上角+temp取最小
d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+temp);
}
}
return d[n][m];
}
public static double sim(String str1, String str2) {
int ld = ld(str1, str2);
return 1 - (double) ld / Math.max(str1.length(), str2.length());
}
public static void main(String[] args) {
String str1 = "chenlb.blogjava.net";
String str2 = "chenlb.javaeye.com";
System.out.println("ld="+ld(str1, str2));
System.out.println("sim="+sim(str1, str2));
}
}
- 浏览: 123700 次
- 性别:
- 来自: 北京
最新评论
-
xiejin2008:
最近1-2年比较流行的树组件 ztree
Dtree+Jquery动态生成树节点例子《新手可参考》 -
xiejin2008:
cyl5753 写道按照上面的步骤,访问https://127 ...
WebLogic Server 10.3 SSL配置及SSL协议传输的WebSevice调用 -
cyl5753:
按照上面的步骤,访问https://127.0.0.1:700 ...
WebLogic Server 10.3 SSL配置及SSL协议传输的WebSevice调用 -
wang1248912822:
[size=large][/size] [b] ...
Ext3.0 动态数据 Chart 初探 -
fushun_test:
很不错,柱状的每个珠子颜色和饼状的每个部分的颜色可以自定义吗 ...
Ext3.0 动态数据 Chart 初探
java 两字符串相似度计算算法 (转)Levenshtein Distance编辑距离算法
- 博客分类:
- J2EE
相关推荐
Levenshtein:快速计算编辑距离以及字符串的相似度
NULL 博文链接:https://biansutao.iteye.com/blog/326008
两个字符串的相似度算法实现——编辑距离之Levenshtein距离
C#,字符串相似度的莱文斯坦距离(Levenshtein Distance)算法与源代码 莱文斯坦距离(Levenshtein Distance)用于衡量两个字符串之间的相似度。 莱文斯坦距离以俄国科学家(Vladimir I. Levenshtein)命名,他于...
“成本”列给出了计算成本的估算值,以分别计算长度为m和n的两个字符串之间的相似度。 归一化? 公制? 类型 成本 典型用法 距离 没有 是 O(米* n) 1 距离相似 是 没有 O(米* n) 1 距离 没有 没有 O(米* n...
编辑距离算法,即Levenshtein Distance (LD)算法。 这个算法其实是一个动态规划(DP)。levenshtein() 返回两个字符串之间的 Levenshtein 距离。 Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个...
编辑距离(EditDistance)定义 编辑距离就是用来计算从原串(s)转换到目标串(t)所需要的最少的插入,删除和替换的数目,在NLP中...编辑距离的算法是首先由俄国科学家Levenshtein提出的,故又叫Levenshtein Distance。
“成本”列给出了计算成本的估算值,以分别计算长度为m和n的两个字符串之间的相似度。 归一化? 公制? 类型 成本 典型用法 距离 没有 是 O(米* n) 1 距离相似 是 没有 O(米* n) 1 距离 没有 没有 O(米* n...
Levenshtein Distance算法可以看作动态规划 它的思路就是从两个字符串的左边开始比较 记录已经比较过的子串相似度 实际上叫做距离 然后进一步得到下一个字符位置时的相似度 用下面的例子: GUMBO和GAMBOL 当算到矩阵D...
(换句话来说,就计算两个字符串的相似度,值越小相似度越高)。该实现采用了编辑距离算法,详见:###2、使用方法:使用源代码的话,从第1步开始。如果是直接使用二进制发布包的话,直接从第4步开始即可。1)下载本...
目前实现了十几种算法(包括 Levenshtein 编辑距离和兄弟姐妹、最长公共子序列、余弦相似度等)。 查看下面的汇总表以获取完整列表... 参数 返回 排序匹配 参数 返回 参数 返回 发行说明1.x 版本 麻省理工学院 ...
LD算法(Levenshtein Distance)又称编辑距离算法(Edit Distance)。以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B,那么操作的过程的次数表示两个字符串的差异。本资源为此算法的python实现。...
该gem实现了纯Levenshtein算法,即Damerau的改进算法(其中2个字符换位算作1个编辑距离)。 它还包括Boermer&Rees 2008对Damerau算法的修改,其中也考虑了大于1个字符块的转置 。 require "damerau-levenshtein...
字符串相似度.NET Java字符串相似性的.NET端口: : 一个... “成本”列给出了计算成本的估算值,以分别计算长度为m和n的两个字符串之间的相似度。 归一化? 公制? 类型成本距离没有是O(米* n) 1距离相似是没有O
列文斯基距离(LD,Levenshtein Distance)又成为编辑距离算法(Edit Distance)。他是以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B,那么操作的过程的次数表示两个字符串的差异。 文件1里面是需要...
这些是不同“编辑距离”或模糊字符串比较算法的 C# 实现。 莱文斯坦距离 两个单词之间的 Levenshtein 距离是将一个单词更改为另一个单词所需的最小单字符编辑(插入、删除、替换)次数。 短语编辑距离通常用于特指 ...
Levenshtein命名)是两个字符串之间的“距离”(字符串度量),即符号的有限序列,通过计算最小值将一个字符串转换为另一个字符串所需的操作数,其中一个操作定义为单个字符的插入,删除或替换,或者两个相邻字符的...
编辑距离 字符串距离算法的实现。 描述 编辑模糊匹配的距离算法。 具体来说,这个库提供: 例子 Levenshtein d = new Levenshtein (); print (d. distance ( 'witch' , 'kitsch' )); // 2
贝达 获取BEDA ...介绍 BEDA是一个golang库,用于检测两个单词或...Jaro&Jaro Winkler Distance:一个字符串度量,用于测量两个序列之间的编辑距离。 BEDA是印度尼西亚语中“不同”的意思。 用法 import "github.com/h