计算字符串相似度算法—Levenshtein什么是Levenshtein实现过程实现代码

69 阅读 0 评论 46 点赞

我是靠谱客的博主聪慧豆芽，最近开发中收集的这篇文章主要介绍计算字符串相似度算法—Levenshtein什么是Levenshtein实现过程实现代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

什么是Levenshtein

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。levenshtein() 函数返回两个字符串之间的 Levenshtein 距离。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance

实现过程

首先我们明确从一个字符串变化到另一个字符串需要进行添加、修改、删除来变化

如a变化到ab需要一步，添加一个b，

aa变化到ab需要修改一个a到b，

ab变化到a需要删除一个b。

首先我们确定了两个字符串str1,str2;假设这两个字符为a₁a₂a₃a_4......,b₁b₂b_3......

那么构建一个二维矩阵

空　　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.以此推得到

A_mn的值为A_m-1n+1，A_mn-1+1，A_m-1n-1+x(当a_m=b_n时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;
}