LD算法获取字符串相似度

最近帮一个项目分析数据库瓶颈，于是想先通过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　│

  │  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

<code>/// &lt;summary&gt; </code>

<code>/// 计算LD值 </code>

<code>/// &lt;/summary&gt; </code>

<code>/// &lt;param name="str1"&gt;第一个字符串&lt;/param&gt; </code>

<code>/// &lt;param name="str2"&gt;第二个字符串&lt;/param&gt; </code>

<code>/// &lt;returns&gt;LD&lt;/returns&gt; </code>

<code>public</code> <code>int</code> <code>GetLevenshteinDistince(</code><code>string</code> <code>str1, </code><code>string</code> <code>str2) </code>

<code>{ </code>

<code>    </code><code>//初始化矩阵 </code>

<code>    </code><code>int</code><code>[,] matrix = </code><code>new</code> <code>int</code><code>[str1.Length + 1, str2.Length + 1]; </code>

<code> </code> 

<code>    </code><code>//赋第一行与第一列的初值 </code>

<code>    </code><code>for</code><code>(</code><code>int</code> <code>i = 0; i &lt;= str1.Length; ++i) </code>

<code>        </code><code>matrix[i, 0] = i; </code>

<code>    </code><code>for</code><code>(</code><code>int</code> <code>i = 0; i &lt;= str2.Length; ++i) </code>

<code>        </code><code>matrix[0, i] = i; </code>

<code>    </code><code>//开始填充矩阵 </code>

<code>    </code><code>for</code><code>(</code><code>int</code> <code>i = 1; i &lt;= str1.Length; i++) </code>

<code>    </code><code>{ </code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>j = 1; j &lt;= str2.Length; j++) </code>

<code>        </code><code>{ </code>

<code>            </code><code>//左上角相同加0，否则加1 </code>

<code>            </code><code>int</code> <code>addition = str1[i - 1] == str2[j - 1] ? 0 : 1; </code>

<code>            </code><code>//取三者中的最小值 </code>

<code>            </code><code>int</code> <code>min = Math.Min(matrix[i - 1, j - 1] + addition, matrix[i, j - 1] + 1); </code>

<code>            </code><code>matrix[i, j] = Math.Min(min, matrix[i - 1, j] + 1); </code>

<code>        </code><code>} </code>

<code>    </code><code>} </code>

<code>    </code><code>//矩阵最右下角数字即是LD </code>

<code>    </code><code>return</code> <code>matrix[str1.Length, str2.Length]; </code>

<code>} </code>

<code>/// 计算相似度 </code>

<code>/// &lt;returns&gt;相似度，0-1之间&lt;/returns&gt; </code>

<code>public</code> <code>float</code> <code>ComputeSimilarity(</code><code>string</code> <code>str1, </code><code>string</code> <code>str2) </code>

<code>    </code><code>return</code> <code>1 - (</code><code>float</code><code>)GetLevenshteinDistince(str1, str2) / Math.Max(str1.Length, str2.Length); </code>

<code>}</code>

OK，运行效率还是挺高的。

     本文转自 BoyTNT 51CTO博客，原文链接：http://blog.51cto.com/boytnt/822237，如需转载请自行联系原作者