字符串相似度算法(编辑距离算法 Levenshtein Distance)原理及C#代码实现转自:http://www.deepleo.com/archives/220
编辑距离,又称Levenshtein距离(也叫做Edit Distance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数,如果它们的距离越大,说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。例如将kitten一字转成sitting:sitten (k→s)sittin (e→i)sitting (→g)俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。因此也叫Levenshtein Distance。例如如果str1=”ivan”,str2=”ivan”,那么经过计算后等于 0。没有经过转换。相似度=1-0/Math.Max(str1.length,str2.length)如果str1=”ivan1″,str2=”ivan2″,那么经过计算后等于1。str1的”1″转换”2″,转换了一个字符,所以距离是1,相似度=1-1/Math.Max(str1.length,str2.length)应用DNA分析拼字检查语音辨识抄袭侦测算法过程str1或str2的长度为0返回另一个字符串的长度。 if(str1.length==0) return str2.length; if(str2.length==0) return str1.length;初始化(n+1)*(m+1)的矩阵d,并让第一行和列的值从0开始增长。扫描两字符串(n*m级的),如果:str1[i] == str2[j],用temp记录它,为0。否则temp记为1。然后在矩阵d[i,j]赋于d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp三者的最小值。扫描完后,返回矩阵的最后一个值d[n][m]即是它们的距离。计算相似度公式:1-它们的距离/两个字符串长度的最大值。
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace DeepLeo.Library.String { public class LevenshteinSimilarity { public class LevenshteinDistance { /// <summary> /// 取最小的一位数 /// </summary> /// <param name="first"></param> /// <param name="second"></param> /// <param name="third"></param> /// <returns></returns> private int LowerOfThree(int first, int second, int third) { int min = Math.Min(first, second); return Math.Min(min, third); } private int Levenshtein_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 = new int[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); } } for (i = 0; i <= n; i++) { for (j = 0; j <= m; j++) { Console.Write(" {0} ", Matrix[i, j]); } Console.WriteLine(""); } return Matrix[n, m]; } /// <summary> /// 计算字符串相似度 /// </summary> /// <param name="str1"></param> /// <param name="str2"></param> /// <returns></returns> public decimal LevenshteinDistancePercent(string str1, string str2) { //int maxLenth = str1.Length > str2.Length ? str1.Length : str2.Length; int val = Levenshtein_Distance(str1, str2);return 1 - (decimal)val / Math.Max(str1.Length, str2.Length); } } } }