编辑距离概念描述:
编辑距离,又称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)); }
相关推荐
在IT领域,字符串相似度...总之,编辑距离算法(Levenshtein Distance)是字符串处理中的一个重要工具,它提供了一种量化字符串相似性的方法。理解并熟练运用这个算法能够帮助我们在处理文本数据时做出更准确的决策。
在本文中,我们将讨论一种常用的字符串相似度算法:Levenshtein Distance。 什么是Levenshtein Distance? Levenshtein Distance(LD)是一种衡量两个字符串之间相似度的方法,衡量的是将源字符串(s)转换为目标...
Levenshtein Distance--求字符串的相似程度的算法,文件用IE6可以打开。
Levenshtein库提供了高效的算法来计算这个距离,并且可以用来评估字符串之间的相似度。在Python中,你可以通过以下方式导入并使用这个库: ```python from Levenshtein import distance ``` 然后,你可以用`...
C#,字符串相似度的莱文斯坦距离(Levenshtein Distance)算法与源代码 莱文斯坦距离(Levenshtein Distance)用于衡量两个字符串之间的相似度。 莱文斯坦距离以俄国科学家(Vladimir I. Levenshtein)命名,他于...
Levenshtein距离是一种衡量字符串相似度的算法,它计算的是将一个字符串转换成另一个字符串所需要的最少单字符编辑(插入、删除或替换)的数量。 Levenshtein距离的核心思想是动态规划,由俄国数学家Vladimir ...
在上述代码中,`LevenshteinDistance`函数接受两个字符串作为参数,并返回它们之间的Levenshtein距离。初始化二维数组`dp`用于存储中间结果,`min`函数用于找到三个整数中的最小值。 从压缩包文件"levenshtein-...
在IT领域,字符串相似度算法是一种非常重要的工具,特别是在数据挖掘、信息检索、文本分类以及自然语言处理等应用中。这个小例子旨在介绍如何通过计算字符串间的相似度来进行模糊匹配。我们将探讨几种常见的字符串...
两个字符串的相似度算法实现——编辑距离之Levenshtein距离
在计算机科学领域,字符串编辑距离(Levenshtein Distance)是一种衡量两个字符串相似度的指标,它定义了将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数。这些操作包括插入、删除和替换。这个概念广泛...
在这个开源项目——ferhatelmas/levenshtein中,作者用Golang实现了Levenshtein距离算法,为开发者提供了高效且灵活的字符串相似度计算工具。 首先,我们来详细了解Levenshtein距离的计算原理。假设我们有两个字符...
1. **编辑距离(Levenshtein Distance)**:编辑距离是指将一个字符串转换成另一个字符串所需的最少单字符编辑(插入、删除或替换)次数。这个概念在拼写检查和DNA序列比对等领域非常有用。 2. **Jaccard相似度**:...
Levenshtein Distance算法提供了一种有效的方法来度量两个字符串之间的相似性,而基于关键词的空间向量模型则适用于更广泛的文本相似度计算任务。掌握这两种算法的原理及其应用场景对于从事数据挖掘、自然语言处理等...
Levenshtein Distance 算法是一种计算两个字符串之间的编辑距离的算法,编辑距离是指从一个字符串变换到另一个字符串所需要的最少变化操作步骤。该算法的计算过程可以用一个二维表来理解,以beauty 和 batyu为例: ...
字符串算法是计算机科学中的一个重要领域,它涉及到对字符串(一串字符序列)进行操作和分析的各种算法。在处理文本、编程语言、数据压缩、搜索、排序等问题时,字符串算法起着至关重要的作用。这里我们将深入探讨...
总的来说,`Levenshtein`库是Python中一个强大的工具,它提供了计算和分析字符串相似度的功能,对于需要处理文本相似性问题的开发者来说,是一个不可或缺的资源。这个特定的压缩包版本适用于64位Windows系统上的...
在实际使用中,开发者可以通过npm(Node Package Manager)安装这个库,然后在项目中导入并调用其提供的函数,如`levenshteinDistance(str1, str2)`,来计算两个字符串的Levenshtein距离。 总结来说,这个“前端...
当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看下面的摘要表以获取完整列表... 下载 使用Maven: <groupId>info.debatty <artifactId>java-...