文档介绍：计算字符串相似度算法——Levenshtein
博客分类: 
我喜欢的算法
levenshtein相似度编辑距离算法实现 
:
Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。
许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
编辑距离的算法是首先由俄国科学家Levenshtein提出的,故又叫Levenshtein Distance。
模糊查询
,这里写一个简单的 abc和abe
。
A处 是一个标记,为了方便讲解,不是这个表的内容。
 
abc
a
b
c
abe
0
1
2
3
a
1
A处
b
2
e
3
 出得值
它的值取决于:左边的1、上边的1、左上角的0.
按照Levenshtein distance的意思:
上面的值和左面的值都要求加1,这样得到1+1=2。
A处 由于是两个a相同,+0=0。
这是后有三个值,左边的计算后为2,上边的计算后为2,左上角的计算为0,所以A处 取他们里面最小的0.
abc
a
b
c
abe
0
1
2
3
a
1
0
b
2
B处
e
3
在B处 会同样得到三个值,左边计算后为3,上边计算后为1,在B处 由于对应的字符为a、b,不相等,所以左上角应该在当前值的基础上加1,这样得到1+1=2,在(3,1,2)中选出最小的为B处的值。
 
abc
a
b
c
abe
0
1
2
3
a
1
0
b
2
1
e
3
C处
C处 计算后:上面的值为2,左边的值为4,左上角的:a和e不相同,所以加1,即2+1,左上角的为3。
在(2,4,3)中取最小的为C处 的值。
a
b
c
0
1
2
3
a
1
A处 0
D处 1
G处 2
b
2
B处 1
E处 0
H处 1
e
3
C处 2
F处 1
I处 1
 
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个操作。
先取两个字符串长度的最大值maxLen,用1-(需要操作数除maxLen),得到相似度。
例如abc 和abe 一个操作,长度为3,所以相似度为1-1/3=。
直接能运行, 复制过去就行。
Java代码  
package code;  
  
/** 
 * ***@className: 
 * ***@classDescription:Levenshtein Distance 算法实现 
 * 可以使用的地方:DNA分析  拼字检查  语音辨识  抄袭侦测 
 * ***@author: 
 * ***@createTime:2012-1-12 
 */  
public class MyLevenshtein {  
  
    public static void main(String[] args) {  
        //要比较的两个字符串  
        String str1 = "今天星期四";  
        String str2 = "今天是星期五";  
        levenshtein(str1,str2);  
    }  
  
    /** 
     *  DNA分析  拼字检查  语音辨识  抄袭侦测 
     *  
     * ***@createTime 2012-1-12 
     */  
    public static