文档介绍：计算字符串相似度算法—— Levenshtein 博客分类: 我喜欢的算法 levenshtein 相似度编辑距离算法实现 0. 这个算法实现起来很简单 1. 百度百科介绍: Levenshtein 距离, 又称编辑距离, 指的是两个字符串之间, 由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的,故又叫 Levenshtein Distance 。 2. 用途模糊查询 3. 实现过程 a. 首先是有两个字符串, 这里写一个简单的 abc 和 abe b. 将字符串想象成下面的结构。 A处是一个标记,为了方便讲解,不是这个表的内容。 abc abc abe 0123 a1A处 b2e3 c. 来计算 A处出得值它的值取决于:左边的 1 、上边的 1 、左上角的 0. 按照 Levenshtein distance 的意思: 上面的值和左面的值都要求加 1 ,这样得到 1+1=2 。 A处由于是两个 a 相同,左上角的值加 0. 这样得到 0+0=0 。这是后有三个值,左边的计算后为 2 ,上边的计算后为 2 ,左上角的计算为 0 ,所以 A 处取他们里面最小的 0. d. 于是表成为下面的样子 abc abc abe 0123 a10b2B处 e3 在B处会同样得到三个值,左边计算后为 3 ,上边计算后为 1 ,在 B处由于对应的字符为 a、b ,不相等,所以左上角应该在当前值的基础上加 1 ,这样得到 1+1=2 ,在( 3,1,2 )中选出最小的为 B 处的值。 e. 于是表就更新了 abc abc abe 0123 a10b21e3C处 C 处计算后: 上面的值为 2 , 左边的值为 4 , 左上角的:a 和e 不相同, 所以加 1 ,即 2+1 , 左上角的为 3 。在( 2,4,3 )中取最小的为 C 处的值。 f. 于是依次推得到 abc 0123 a1A处0D处1G处2 b2B处1E处0H处1 e3C处2F处1I处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 个操作。 g. 计算相似度先取两个字符串长度的最大值 maxLen ,用 1- (需要操作数除 maxLen ),得到相似度。例如 abc 和 abe 一个操作,长度为 3 ,所以相似度为 1-1/3= 。 4. 代码实现直接能运行, 复制过去就行。 Java 代码 1. package code; 2. 3. /** 4.* ***@className: 5.* ***@classDescription:Levenshtein Distance 算法实现 6.*可以使用的地方: DNA 分析拼字检查语音辨识抄袭侦测 7.* ***@author: 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 = (); 27. int len2 = (); 28. // 建立上面说的数组,比字符长度大一个空间 29. int [][] dif = new int [len1 +1 ][len2 +1 ]