Levenshtein 算法：相似度--模糊查询，数据匹配

待我称王封你为后i 2022-05-31 00:43 250阅读 0赞

## 1.百度百科介绍： ##

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。

许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。

## 2.用途 ##

模糊查询

## 3.实现过程 ##

### a.首先是有两个字符串,这里写一个简单的 abc和abe ###

### b.将字符串想象成下面的结构。 ###

A处 是一个标记，为了方便讲解，不是这个表的内容。

### c.来计算A处 出得值 ###

它的值取决于：左边的1、上边的1、左上角的0.

按照Levenshtein distance的意思：

上面的值和左面的值都要求加1，这样得到1+1=2。

A处 由于是两个a相同，左上角的值加0.这样得到0+0=0。

这是后有三个值，左边的计算后为2，上边的计算后为2，左上角的计算为0，所以A处 取他们里面最小的0.

### d.于是表成为下面的样子 ###

在B处 会同样得到三个值，左边计算后为3，上边计算后为1，在B处 由于对应的字符为a、b，不相等，所以左上角应该在当前值的基础上加1，这样得到1+1=2，在（3,1,2）中选出最小的为B处的值。

### e.于是表就更新了 ###

C处 计算后：上面的值为2，左边的值为4，左上角的：a和e不相同，所以加1，即2+1，左上角的为3。

在（2,4,3）中取最小的为C处 的值。

### f.于是依次推得到 ###

I处: 表示abc 和abe 有1个需要编辑的操作。这个是需要计算出来的。

同时，也获得一些额外的信息。

A处: 表示a      和a      需要有0个操作。字符串一样

B处: 表示ab    和a      需要有1个操作。

C处: 表示abe  和a      需要有2个操作。

D处: 表示a      和ab    需要有1个操作。

E处: 表示ab    和ab    需要有0个操作。字符串一样

F处: 表示abe  和ab    需要有1个操作。

G处: 表示a      和abc   需要有2个操作。

H处: 表示ab    和abc    需要有1个操作。

I处: 表示abe   和abc    需要有1个操作。

### g.计算相似度 ###

先取两个字符串长度的最大值maxLen，用1-（需要操作数除maxLen），得到相似度。

例如abc 和abe 一个操作，长度为3，所以相似度为1-1/3=0.666。

## 4.代码实现 ##

直接能运行， 复制过去就行。

**\[java\]**  [view plain][]  [copy][view plain]

1.  package code;    
2.      
3.  /\*\*  
4.   \* @className:MyLevenshtein.java  
5.   \* @classDescription:Levenshtein Distance 算法实现  
6.   \* 可以使用的地方：DNA分析 　　拼字检查 　　语音辨识 　　抄袭侦测  
7.   \* @author:donghai.wan  
8.   \* @createTime:2012-1-12  
9.   \*/    
10. public class MyLevenshtein \{    
11.     
12.     public static void main(String\[\] args) \{    
13.         //要比较的两个字符串    
14.         String str1 = "今天星期四";    
15.         String str2 = "今天是星期五";    
16.         levenshtein(str1,str2);    
17.     \}    
18.     
19.     /\*\*  
20.      \* 　　DNA分析 　　拼字检查 　　语音辨识 　　抄袭侦测  
21.      \*   
22.      \* @createTime 2012-1-12  
23.      \*/    
24.     public static void levenshtein(String str1,String str2) \{    
25.         //计算两个字符串的长度。    
26.         int len1 = str1.length();    
27.         int len2 = str2.length();    
28.         //建立上面说的数组，比字符长度大一个空间    
29.         int\[\]\[\] dif = new int\[len1 + 1\]\[len2 + 1\];    
30.         //赋初值，步骤B。    
31.         for (int a = 0; a <= len1; a++) \{    
32.             dif\[a\]\[0\] = a;    
33.         \}    
34.         for (int a = 0; a <= len2; a++) \{    
35.             dif\[0\]\[a\] = a;    
36.         \}    
37.         //计算两个字符是否一样，计算左上的值    
38.         int temp;    
39.         for (int i = 1; i <= len1; i++) \{    
40.             for (int j = 1; j <= len2; j++) \{    
41.                 if (str1.charAt(i - 1) == str2.charAt(j - 1)) \{    
42.                     temp = 0;    
43.                 \} else \{    
44.                     temp = 1;    
45.                 \}    
46.                 //取三个值中最小的    
47.                 dif\[i\]\[j\] = min(dif\[i - 1\]\[j - 1\] + temp, dif\[i\]\[j - 1\] + 1,    
48.                         dif\[i - 1\]\[j\] + 1);    
49.             \}    
50.         \}    
51.         System.out.println("字符串\\""\+str1+"\\"与\\""\+str2+"\\"的比较");    
52.         //取数组右下角的值，同样不同位置代表不同字符串的比较    
53.         System.out.println("差异步骤："\+dif\[len1\]\[len2\]);    
54.         //计算相似度    
55.         float similarity =1 - (float) dif\[len1\]\[len2\] / Math.max(str1.length(), str2.length());    
56.         System.out.println("相似度："\+similarity);    
57.     \}    
58.     
59.     //得到最小值    
60.     private static int min(int... is) \{    
61.         int min = Integer.MAX\_VALUE;    
62.         for (int i : is) \{    
63.             if (min > i) \{    
64.                 min = i;    
65.             \}    
66.         \}    
67.         return min;    
68.     \}    
69.     
70. \}    
71.

[view plain]: http://blog.csdn.net/basycia/article/details/51884350#