什么是Levenshtein
Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。levenshtein() 函数返回两个字符串之间的 Levenshtein 距离。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance
实现过程
首先我们明确从一个字符串变化到另一个字符串需要进行添加、修改、删除来变化
如a变化到ab需要一步，添加一个b，
aa变化到ab需要修改一个a到b，
ab变化到a需要删除一个b。
首先我们确定了两个字符串str1,str2;假设这两个字符为a1a2a3a4......,b1b2b3......
那么构建一个二维矩阵
空 a1 a2 a3 a4 ......
空 [1] [2] [3] [4] [5]......
b1 [6] [7] [8] [9] [10]......
b2 [11] [12] [13] [14] [15]......
b3 [16] [17] .......
...
1.判断[1]左边为空，上面为空，从空到空需要变化0次
2.所以可以得到下面的矩阵
空 a1 a2 a3 a4 ......
空 0 1 2 3 4......
b1 1 [7] [8] [9] [10]......
b2 2 [12] [13] [14] [15]......
b3 3 [17] .......
.......
3.到7的位置表示了[空a1]变化到[空b1]，这里我们需要得到三个值
1）从[2]变化到[7]需要的步数是[2]+1
2）从[6]变化到[7]需要的变化是[6]+1
3) 从[1]变化到[7]需要的变化是 ，如果a1=b1，那么需要0步，如果a1！=b1，那么需要删除一个a1在添加一个b1，需要2步，也就是大于1步。
我们取这三步中所需走的最短步数填到[7]的位置 。
4.以此推得到
Amn的值为Am-1n+1，Amn-1+1，Am-1n-1+x(当am=bn时x=0，否则x=2)的最小值
5.当求得的值的最后一位得到的值N，用1-n/(max(len(a),len(b)))得到相关度。
实现代码
/// <summary>
/// Levenshtein 算法实现
/// </summary>
/// <param name="value1"></param>
/// <param name="values2"></param>
/// <returns></returns>
public static float Leven(string value1, string value2)
{
int len1 = value1.Length;
int len2 = value2.Length;
int [,] dif =new int[len1+1,len2+1];
for (int a=0;a<=len1;a++)
{
dif[a,0] = a;
}
for (int a = 0; a <= len2; a++)
{
dif[0, a] = a;
}
int temp =0;
for (int i = 1; i <= len1; i++)
{
for (int j = 1; j <= len2; j++)
{
if (value1[i - 1] == value2[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);
}
}
float similarity=1- (float)dif[len1, len2]/Math.Max(len1,len2);
return similarity;
}
public static int Min(int a, int b, int c)
{
int i = a < b ? a : b;
return i = i < c ? i : c;
}
