编辑距离算法详解：Levenshtein Distance算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了编辑距离算法详解：Levenshtein Distance算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3233字，纯文字阅读大概需要5分钟。
内容图文
算法基本原理：假设我们可以使用d[ i , j ]个步骤（可以使用一个二维数组保存这个值），表示将串s[ 1…i ] 转换为 串t [ 1…j ]所需要的最少步骤个数，那么，在最基本的情况下，即在i等于0时，也就是说串s为空，那么对应的d[0,j] 就是 增加j个字符，使得s转化为t，在j等于0时，也就是说串t为空，那么对应的d[i,0] 就是 减少 i个字符，使得s转化为t。
然后我们考虑一般情况，加一点动态规划的想法，我们要想得到将s[1..i]经过最少次数的增加，删除，或者替换操作就转变为t[1..j]，那么我们就必须在之前可以以最少次数的增加，删除，或者替换操作，使得现在串s和串t只需要再做一次操作或者不做就可以完成s[1..i]到t[1..j]的转换。所谓的“之前”分为下面三种情况：
1）我们可以在k个操作内将 s[1…i] 转换为 t[1…j-1]
2）我们可以在k个操作里面将s[1..i-1]转换为t[1..j]
3）我们可以在k个步骤里面将 s[1…i-1] 转换为 t [1…j-1]
针对第1种情况，我们只需要在最后将 t[j] 加上s[1..i]就完成了匹配，这样总共就需要k+1个操作。
针对第2种情况，我们只需要在最后将s[i]移除，然后再做这k个操作，所以总共需要k+1个操作。
针对第3种情况，我们只需要在最后将s[i]替换为 t[j]，使得满足s[1..i] == t[1..j]，这样总共也需要k+1个操作。而如果在第3种情况下，s[i]刚好等于t[j]，那我们就可以仅仅使用k个操作就完成这个过程。
最后，为了保证得到的操作次数总是最少的，我们可以从上面三种情况中选择消耗最少的一种最为将s[1..i]转换为t[1..j]所需要的最小操作次数。
算法基本步骤：
（1）构造 行数为m+1 列数为 n+1 的矩阵 , 用来保存完成某个转换需要执行的操作的次数，将串s[1..n] 转换到 串t[1…m] 所需要执行的操作次数为matrix[n][m]的值；
（2）初始化matrix第一行为0到n，第一列为0到m。
Matrix[0][j]表示第1行第j-1列的值，这个值表示将串s[1…0]转换为t[1..j]所需要执行的操作的次数，很显然将一个空串转换为一个长度为j的串，只需要j次的add操作，所以matrix[0][j]的值应该是j，其他值以此类推。
（3）检查每个从1到n的s[i]字符；
（4）检查每个从1到m的s[i]字符；
（5）将串s和串t的每一个字符进行两两比较，如果相等，则让cost为0，如果不等，则让cost为1（这个cost后面会用到）;
(6)a、如果我们可以在k个操作里面将s[1..i-1]转换为t[1..j]，那么我们就可以将s[i]移除，然后再做这k个操作，所以总共需要k+1个操作。
b、如果我们可以在k个操作内将 s[1…i] 转换为 t[1…j-1] ，也就是说d[i,j-1]=k，那么我们就可以将 t[j] 加上s[1..i]，这样总共就需要k+1个操作。
c、如果我们可以在k个步骤里面将 s[1…i-1] 转换为 t [1…j-1]，那么我们就可以将s[i]转换为 t[j]，使得满足s[1..i] == t[1..j]，这样总共也需要k+1个操作。（这里加上cost，是因为如果s[i]刚好等于t[j]，那么就不需要再做替换操作，即可满足，如果不等，则需要再做一次替换操作，那么就需要k+1次操作）
因为我们要取得最小操作的个数，所以我们最后还需要将这三种情况的操作个数进行比较，取最小值作为d[i,j]的值；
d、然后重复执行3,4,5,6，最后的结果就在d[n,m]中；
图解：
图解过程如下：
step 1：初始化如下矩阵
step 2：从源串的第一个字符（“j”）开始，从上至下与目标串进行对比
如果两个字符相等，则在从此位置的左，上，左上三个位置中取出最小的值；若不等，则在从此位置的左，上，左上三个位置中取出最小的值再加上1；
第一次，源串第一个字符“j” 与目标串的“j”对比,左，上，左上三个位置中取出最小的值0，因为两字符相等，所以加上0；接着，依次对比“j”→“e”，“j”→“r”，“j”→“r”，，“j”→“y” 到扫描完目标串。
step 3：遍历整个源串与目标串对比：
step 4：扫描完最后一列，则最后一个为最短编辑距离：
求出编辑距离，那么两个字符串的相似度 Similarity = (Max(x,y) - Levenshtein)/Max(x,y)，其中 x,y 为源串和目标串的长度。
核心代码如下：
public
class
LevenshteinDistance
{
private
static LevenshteinDistance _instance = null;
publicstatic LevenshteinDistance Instance
{
get
{
if (_instance == null)
{
returnnew LevenshteinDistance();
}
return _instance;
}
}
publicint LowerOfThree(int first, int second, int third)
{
int min = first;
if (second < min)
min = second;
if (third < min)
min = third;
return min;
}
publicint Compare_Distance(string str1, string str2)
{
int[,] Matrix;
int n = str1.Length;
int m = str2.Length;
int temp = 0;
char ch1;
char ch2;
int i = 0;
int j = 0;
if (n == 0)
{
return m;
}
if (m == 0)
{
return n;
}
Matrix = newint[n + 1, m + 1];
for (i = 0; i <= n; i++)
{
Matrix[i, 0] = i;
}
for (j = 0; j <= m; j++)
{
Matrix[0, j] = j;
}
for (i = 1; i <= n; i++)
{
ch1 = str1[i - 1];
for (j = 1; j <= m; j++)
{
ch2 = str2[j - 1];
if (ch1.Equals(ch2))
{
temp = 0;
}
else
{
temp = 1;
}
Matrix[i, j] = LowerOfThree(Matrix[i - 1, j] + 1, Matrix[i, j - 1] + 1, Matrix[i - 1, j - 1] + temp);
}
}
return Matrix[n, m];
}
publicdecimal LevenshteinDistancePercent(string str1, string str2)
{
int maxLenth = str1.Length > str2.Length ? str1.Length : str2.Length;
int val = Compare_Distance(str1, str2);
return1 - (decimal)val / maxLenth;
}
}
原文：http://www.cnblogs.com/sumuncle/p/5632032.html
内容总结
以上是互联网集市为您收集整理的编辑距离算法详解：Levenshtein Distance算法全部内容，希望文章能够帮你解决编辑距离算法详解：Levenshtein Distance算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。