本文共 2101 字，大约阅读时间需要 7 分钟。
最近帮一个项目分析数据库瓶颈，于是想先通过SQL Profiler把SQL语句的运行数据抓下来，再对不同语句分类统计。这其中涉及一个如何识别相似语句的问题，于是上网找了找，一个叫Levenshtein Distance的算法比较简单，就写了段代码实现了一下，效果还不错。
这个算法是一个俄国人Lvenshtein提出的，用于计算两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。次数越少，表示两个字符串相似度越高。
用实例来讲解算法最直观，我们假设有两个字符串：test和est，需要经过以下几个步骤来获取LD值。
1、初始化一个矩阵
┌──┬───────────┐
│ │test t e s t │
├──┼───────────┤
│ est│ 0 1 2 3 4 │
│ e│ 1 x │
│ s│ 2 │
│ t│ 3 │
└──┴───────────┘
2、计算x值
计算x的算法为：
取x1 = 左边的值+1 = 1+1 = 2；
取x2 = 上边的值+1 = 1+1 = 2；
如果横纵坐标的字符不一样，则取x3 = 左上角的值+1，否则取x3 = 左上角的值。此处由于e≠t，所以x3 = 0+1 = 1。
然后得到x = min(x1, x2, x3) = 1。
3、以此类推，填满矩阵，最右下角的值即为LD值
┌──┬───────────┐
│ │test t e s t │
├──┼───────────┤
│ est│ 0 1 2 3 4 │
│ e│ 1 1 1 2 3 │
│ s│ 2 2 2 1 2 │
│ t│ 3 2 3 2 1 │
└──┴───────────┘
4、计算相似度
公式为：相似度 = 1 - (LD / 最大字符串长度)
本例中，相似度 = 1 - (1 / 4) = 0.75，这个值介于0到1之间，值越高，表示两字符串相似度越大。
用C#代码实现一下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | /// <summary> /// 计算LD值 /// </summary> /// <param name="str1">第一个字符串</param> /// <param name="str2">第二个字符串</param> /// <returns>LD</returns> public int GetLevenshteinDistince( string str1, string str2) { //初始化矩阵 int [,] matrix = new int [str1.Length + 1, str2.Length + 1]; //赋第一行与第一列的初值 for ( int i = 0; i <= str1.Length; ++i) matrix[i, 0] = i; for ( int i = 0; i <= str2.Length; ++i) matrix[0, i] = i; //开始填充矩阵 for ( int i = 1; i <= str1.Length; i++) { for ( int j = 1; j <= str2.Length; j++) { //左上角相同加0，否则加1 int addition = str1[i - 1] == str2[j - 1] ? 0 : 1; //取三者中的最小值 int min = Math.Min(matrix[i - 1, j - 1] + addition, matrix[i, j - 1] + 1); matrix[i, j] = Math.Min(min, matrix[i - 1, j] + 1); } } //矩阵最右下角数字即是LD return matrix[str1.Length, str2.Length]; } /// <summary> /// 计算相似度 /// </summary> /// <param name="str1">第一个字符串</param> /// <param name="str2">第二个字符串</param> /// <returns>相似度，0-1之间</returns> public float ComputeSimilarity( string str1, string str2) { return 1 - ( float )GetLevenshteinDistince(str1, str2) / Math.Max(str1.Length, str2.Length); } |
OK，运行效率还是挺高的。
本文转自 BoyTNT 51CTO博客，原文链接：http://blog.51cto.com/boytnt/822237，如需转载请自行联系原作者