转载文章地址:
http://wdhdmx.iteye.com/blog/1343856
1.百度百科介绍:
Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。
许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
编辑距离的算法是首先由俄国科学家Levenshtein提出的,故又叫Levenshtein Distance。
2.用途
模糊查询
package com.leve;
/**
* @className:MyLevenshtein.java
* @classDescription:Levenshtein Distance 算法实现
* 可以使用的地方:DNA分析 拼字检查 语音辨识 抄袭侦测
* @author:donghai.wan
* @createTime:2012-1-12
*/
public class MyLevenshtein {
public static void main(String[] args) {
//要比较的两个字符串
String str1 = "四川成都市二环东路122号";
String str2 = "四川成都市二环东路142号";
levenshtein(str1,str2);
}
/**
* DNA分析 拼字检查 语音辨识 抄袭侦测
*
* @createTime 2012-1-12
*/
public static void levenshtein(String str1,String str2) {
//计算两个字符串的长度。
int len1 = str1.length();
int len2 = str2.length();
//建立上面说的数组,比字符长度大一个空间
int[][] dif = new int[len1 + 1][len2 + 1];
//赋初值,步骤B。
for (int a = 0; a <= len1; a++) {
dif[a][0] = a;
}
for (int a = 0; a <= len2; a++) {
dif[0][a] = a;
}
//计算两个字符是否一样,计算左上的值
int temp;
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
temp = 0;
} else {
temp = 1;
}
//取三个值中最小的
dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,
dif[i - 1][j] + 1);
}
}
System.out.println("字符串\""+str1+"\"与\""+str2+"\"的比较");
//取数组右下角的值,同样不同位置代表不同字符串的比较
System.out.println("差异步骤:"+dif[len1][len2]);
//计算相似度
float similarity =1 - (float) dif[len1][len2] / Math.max(str1.length(), str2.length());
System.out.println("相似度:"+similarity);
}
//得到最小值
private static int min(int... is) {
int min = Integer.MAX_VALUE;
for (int i : is) {
if (min > i) {
min = i;
}
}
return min;
}
}
分享到:
相关推荐
levenshtein - 这是一个Go实现计算Levenshtein距离算法
NULL 博文链接:https://biansutao.iteye.com/blog/326008
C#,字符串相似度的莱文斯坦距离(Levenshtein Distance)算法与源代码 莱文斯坦距离(Levenshtein Distance)用于衡量两个字符串之间的相似度。 莱文斯坦距离以俄国科学家(Vladimir I. Levenshtein)命名,他于...
LevenshteinDistance(编辑距离)算法详解[借鉴].pdf
Levenshtein:快速计算编辑距离以及字符串的相似度
Levenshtein Distance--求字符串的相似程度的算法,文件用IE6可以打开。
两个字符串的相似度算法实现——编辑距离之Levenshtein距离
Angular Smart 404演示 该演示演示了使用Levenshtein距离算法的正确路径建议的实现。
Levenshtein Distance算法可以看作动态规划 它的思路就是从两个字符串的左边开始比较 记录已经比较过的子串相似度 实际上叫做距离 然后进一步得到下一个字符位置时的相似度 用下面的例子: GUMBO和GAMBOL 当算到矩阵D...
基于 , 的最快JS实现 比快100% 经过测试,覆盖率100% 使用静态类型检查 更好地控制要返回的比赛类型 支持匹配对象的path而不只是key 安装 npm install didyoumean2 const didYouMean = require ( 'didyoumean2...
Crystal语言的Damerau-Levenshtein算法实现。 安装 将其添加到Projectfile deps do github " suxxes/damerau-levenshtein " end 用法 require " damerau-levenshtein " DamerauLevenshtein .distance( " string " ...
Metaphone-拼写检查 拼写检查程序使用 Levenshtein Distance 和 Metaphone 算法的组合为用户提供 5 种可能的更正
编辑距离算法,即Levenshtein Distance (LD)算法。 这个算法其实是一个动态规划(DP)。levenshtein() 返回两个字符串之间的 Levenshtein 距离。 Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个...
LD算法(Levenshtein Distance)又称编辑距离算法(Edit Distance)。以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B,那么操作的过程的次数表示两个字符串的差异。本资源为此算法的python实现。...
该gem实现了纯Levenshtein算法,即Damerau的改进算法(其中2个字符换位算作1个编辑距离)。 它还包括Boermer&Rees 2008对Damerau算法的修改,其中也考虑了大于1个字符块的转置 。 require "damerau-levenshtein...
模糊匹配器 Clojure 的近似模式匹配库,可用于基于 Levenshtein 距离查找相似词。... you can specify a different rank(edit distance) if you want to ( fuzzy/search " hi " [ " ho " " hello " " correct " " boo
实现 使用算法的简单搜索建议。 安装 $ npm install fulfil --save 用法 var words = require ( 'superb' ) . words ; var fulfil = require ( 'fulfil' ) ; fulfil ( 'batueiful' , words ) . shift ( ) ; // ...
快速实现编辑距离(Levenshtein距离)。 该库仅使用C ++和Cython实现。 该库中使用的算法由提出 。 二元轮 多亏了 ,Linux,Mac OS和Windows上都有二进制轮子。 安装 您可以通过pip安装: pip install edit...
pyxDamerauLevenshtein在Cython中为Python实现了Damerau-Levenshtein(DL)编辑距离算法,以实现高性能。 礼貌: 在信息论和计算机科学中,Damerau-Levenshtein距离(以Frederick J. Damerau和Vladimir I. ...