编辑距离概念描述:
编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
例如将kitten一字转成sitting:
sitten (k→s)
sittin (e→i)
sitting (→g)
俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
问题:找出字符串的编辑距离,即把一个字符串s1最少经过多少步操作变成编程字符串s2,操作有三种,添加一个字符,删除一个字符,修改一个字符
解析:
首先定义这样一个函数——edit(i, j),它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。
显然可以有如下动态规划公式:
<!--[if !supportLists]-->if i == 0 且 j == 0,edit(i, j) = 0
<!--[if !supportLists]-->if i == 0 且 j > 0,edit(i, j) = j
<!--[if !supportLists]-->if i > 0 且j == 0,edit(i, j) = i
<!--[if !supportLists]-->if i ≥ 1 且 j ≥ 1 ,edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) },当第一个字符串的第i个字符不等于第二个字符串的第j个字符时,f(i, j) = 1;否则,f(i, j) = 0。
|
0 |
f |
a |
i |
l |
i |
n |
g |
0 |
|
|
|
|
|
|
|
|
s |
|
|
|
|
|
|
|
|
a |
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
l |
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
0 |
f |
a |
i |
l |
i |
n |
g |
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
s |
1 |
|
|
|
|
|
|
|
a |
2 |
|
|
|
|
|
|
|
i |
3 |
|
|
|
|
|
|
|
l |
4 |
|
|
|
|
|
|
|
n |
5 |
|
|
|
|
|
|
|
计算edit(1, 1),edit(0, 1) + 1 == 2,edit(1, 0) + 1 == 2,edit(0, 0) + f(1, 1) == 0 + 1 == 1,min(edit(0, 1),edit(1, 0),edit(0, 0) + f(1, 1))==1,因此edit(1, 1) == 1。 依次类推:
|
0 |
f |
a |
i |
l |
i |
n |
g |
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
s |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
a |
2 |
2 |
|
|
|
|
|
|
i |
3 |
|
|
|
|
|
|
|
l |
4 |
|
|
|
|
|
|
|
n |
5 |
|
|
|
|
|
|
|
edit(2, 1) + 1 == 3,edit(1, 2) + 1 == 3,edit(1, 1) + f(2, 2) == 1 + 0 == 1,其中s1[2] == 'a' 而 s2[1] == 'f'‘,两者不相同,所以交换相邻字符的操作不计入比较最小数中计算。以此计算,得出最后矩阵为:
|
0 |
f |
a |
i |
l |
i |
n |
g |
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
s |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
a |
2 |
2 |
1 |
2 |
3 |
4 |
5 |
6 |
i |
3 |
3 |
2 |
1 |
2 |
3 |
4 |
5 |
l |
4 |
4 |
3 |
2 |
1 |
2 |
3 |
4 |
n |
5 |
5 |
4 |
3 |
2 |
2 |
2 |
3 |
Lucene里的实现:
//***************************** // Compute Levenshtein distance: see org.apache.commons.lang.StringUtils#getLevenshteinDistance(String, String) //***************************** public float getDistance (String target, String other) { char[] sa; int n; int p[]; //'previous' cost array, horizontally int d[]; // cost array, horizontally int _d[]; //placeholder to assist in swapping p and d /* * 这里的实现是仅仅使用一个临时数组做交换空间,避免直接创建 * 一个二维数组可能出现的oom */ sa = target.toCharArray(); n = sa.length; // 初始化目标字符串 p = new int[n+1]; d = new int[n+1]; final int m = other.length(); if (n == 0 || m == 0) { if (n == m) { return 1; } else { return 0; } } // indexes into strings s and t int i; // iterates through s int j; // iterates through t char t_j; // jth character of t int cost; // cost // 横向字符串,初始化编辑距离 0-n, 第一个横排的值 for (i = 0; i<=n; i++) { p[i] = i; } for (j = 1; j<=m; j++) { // 竖向字符串,从第二个横排开始 // 注意,这里j-1是由于数组的第一个位置是0,字符串位置从1开始的,实际取字符时,要位置-1得到下标 t_j = other.charAt(j-1); // 横向编辑距离的第一个值的值初始值(1-m) d[0] = j; for (i=1; i<=n; i++) { cost = sa[i-1]==t_j ? 0 : 1; // edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) } // minimum of cell to the left+1, to the top+1, diagonally left and up +cost d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost); } // copy current distance counts to 'previous row' distance counts _d = p; // 记录上一个横排的值 p = d; // 下一个马上处理的横排 d = _d; } // our last action in the above loop was to switch d and p, so p now // actually has the most recent cost counts return 1.0f - ((float) p[n] / Math.max(other.length(), sa.length)); }
相关推荐
Levenshtein Distance--求字符串的相似程度的算法,文件用IE6可以打开。
Levenshtein:快速计算编辑距离以及字符串的相似度
NULL 博文链接:https://biansutao.iteye.com/blog/326008
C#,字符串相似度的莱文斯坦距离(Levenshtein Distance)算法与源代码 莱文斯坦距离(Levenshtein Distance)用于衡量两个字符串之间的相似度。 莱文斯坦距离以俄国科学家(Vladimir I. Levenshtein)命名,他于...
两个字符串的相似度算法实现——编辑距离之Levenshtein距离
当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看下面的摘要表以获取完整列表... 下载 使用Maven: <groupId>info.debatty <artifactId>java-...
distance ( "Something" , "Smoething" ) #returns 1 根据Levenshtein alrorithm,它还会返回两个字符串之间的差异。 差异由标签<ins> , 和<subst> 。 这样的标签使得可以灵活地突出显示字符串之间的差异。 ...
编辑距离算法,即Levenshtein Distance (LD)算法。 这个算法其实是一个动态规划(DP)。levenshtein() 返回两个字符串之间的 Levenshtein 距离。 Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个...
字符串相似度.NET Java字符串相似性的.NET端口: : 一个实现不同字符串相似度和距离度量的库。 当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看下面的...
Levenshtein命名)是两个字符串之间的“距离”(字符串度量),即符号的有限序列,通过计算最小值将一个字符串转换为另一个字符串所需的操作数,其中一个操作定义为单个字符的插入,删除或替换,或者两个相邻字符的...
一个带有字符串度量算法的简单库。 如果您想阅读有关字符串度量算法的更多信息,请阅读。 该库希望支持MRI (1.9.3、2.0.0、2.1.0)、 JRuby和Rubinius 。 安装 将此行添加到应用程序的 Gemfile 中: gem '...
这些是不同“编辑距离”或模糊字符串比较算法的 C# 实现。 莱文斯坦距离 两个单词之间的 Levenshtein 距离是将一个单词更改为另一个单词所需的最小单字符编辑(插入、删除、替换)次数。 短语编辑距离通常用于特指 ...
LD算法(Levenshtein Distance)又称编辑距离算法(Edit Distance)。以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B,那么操作的过程的次数表示两个字符串的差异。本资源为此算法的python实现。...
Strutil strutil提供了用于计算字符串相似度的字符串度量标准以及其他字符串实用程序功能。 完整文档可在以下找到: : 。安装 go get github.com/adrg/strutil字符串指标杰罗·温克勒史密斯·沃特曼·高图索伦森-...
当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看下面的摘要表以获取完整列表... 下载 从pypi: # pip install strsim # deprecated, do not use this...
编辑距离 字符串距离算法的实现。 描述 编辑模糊匹配的距离算法。 具体来说,这个库提供: 例子 Levenshtein d = new Levenshtein (); print (d. distance ( 'witch' , 'kitsch' )); // 2
一个实现不同字符串相似性、距离和 sortMatch 度量的库。 目前实现了十几种算法(包括 Levenshtein 编辑距离和兄弟姐妹、最长公共子序列、余弦相似度等)。 查看下面的汇总表以获取完整列表... 参数 返回 排序匹配 ...
Levenshtein Distance算法可以看作动态规划 它的思路就是从两个字符串的左边开始比较 记录已经比较过的子串相似度 实际上叫做距离 然后进一步得到下一个字符位置时的相似度 用下面的例子: GUMBO和GAMBOL 当算到矩阵D...
他是以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B,那么操作的过程的次数表示两个字符串的差异。 文件1里面是需要比较的内容,文件2是被比较的文本,现在需要找到在文件1中每一行的文本在文件2中...