java 两字符串相似度计算算法 (转)Levenshtein Distance编辑距离算法

标签: java 字符串 相似 | 发表时间:2013-12-08 23:39 | 作者:xiejin2008
出处:http://www.iteye.com

Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明,用他的名字命名。不会拼读,可以叫它edit distance(编辑距离)。 

原理很简单,就是返回将第一个字符串转换(删除、插入、替换)成第二个字符串的编辑次数。次数越少,意味着字符串相似度越高 

    Levenshtein distance可以用来: 

Spell checking(拼写检查) 
Speech recognition(语句识别) 
DNA analysis(DNA分析) 
Plagiarism detection(抄袭检测) 
LD用m*n的矩阵存储距离值。算法大概过程: 

java 代码实现: 

/** 
* 编辑距离的两字符串相似度 

* @author jianpo.mo 
*/ 
public class SimilarityUtil { 

    private static int min(int one, int two, int three) { 
        int min = one; 
        if(two < min) { 
            min = two; 
        } 
        if(three < min) { 
            min = three; 
        } 
        return min; 
    } 
    
    public static int ld(String str1, String str2) { 
        int d[][];    //矩阵 
        int n = str1.length(); 
        int m = str2.length(); 
        int i;    //遍历str1的 
        int j;    //遍历str2的 
        char ch1;    //str1的 
        char ch2;    //str2的 
        int temp;    //记录相同字符,在某个矩阵位置值的增量,不是0就是1 
        if(n == 0) { 
            return m; 
        } 
        if(m == 0) { 
            return n; 
        } 
        d = new int[n+1][m+1]; 
        for(i=0; i<=n; i++) {    //初始化第一列 
            d[i][0] = i; 
        } 
        for(j=0; j<=m; j++) {    //初始化第一行 
            d[0][j] = j; 
        } 
        for(i=1; i<=n; i++) {    //遍历str1 
            ch1 = str1.charAt(i-1); 
            //去匹配str2 
            for(j=1; j<=m; j++) { 
                ch2 = str2.charAt(j-1); 
                if(ch1 == ch2) { 
                    temp = 0; 
                } else { 
                    temp = 1; 
                } 
                //左边+1,上边+1, 左上角+temp取最小 
                d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+temp); 
            } 
        } 
        return d[n][m]; 
    } 
    
    public static double sim(String str1, String str2) { 
        int ld = ld(str1, str2); 
        return 1 - (double) ld / Math.max(str1.length(), str2.length()); 
    } 
    
    public static void main(String[] args) { 
       
        String str1 = "chenlb.blogjava.net"; 
        String str2 = "chenlb.javaeye.com"; 
        System.out.println("ld="+ld(str1, str2)); 
        System.out.println("sim="+sim(str1, str2)); 
    } 
}



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [java 字符串 相似] 推荐:

java 两字符串相似度计算算法 (转)Levenshtein Distance编辑距离算法

- - 开源软件 - ITeye博客
Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明,用他的名字命名. 不会拼读,可以叫它edit distance(编辑距离). 原理很简单,就是返回将第一个字符串转换(删除、插入、替换)成第二个字符串的编辑次数. 次数越少,意味着字符串相似度越高 .

字符串相似算法-Jaro-Winkler Distance

- - 开源软件 - ITeye博客
Jaro-Winkler Distance 算法. 这是一种计算两个字符串之间相似度的方法,想必都听过Edit Distance,Jaro-inkler Distance 是Jaro Distance的一个扩展,而Jaro Distance(Jaro 1989;1995)据说是用来判定健康记录上两个名字是否相同,也有说是是用于人口普查,具体干什么就不管了,让我们先来看一下Jaro Distance的定义.

判断字符串是否是有效json对象(java + gson )

- - 改善
已有 0 人发表留言,猛击->> 这里<<-参与讨论. —软件人才免语言低担保 赴美带薪读研.

(转)Java中字符串与内存泄漏的问题

- - jackyrong
对于这个写法,实际上对于oldStr是一个char[]数组[h,e,l,l,0,,,c,l,a,r,k],对于subString操作,newStr并不是自己copy oldStr的char[]数组hello自己去创建一个新的char[]数组,而是java在背后进行了String Reusing Optimization,它不会自己创建一个新的char数组,而是reuse原来的char数组.

字符串匹配 KMP 算法 Java实现

- - ITeye博客
字符串匹配过程中,如果使用蛮力算法,效率非常的差,在此介绍一种较为高效的匹配算法KMP算法. 其主要思想是从匹配的模版去分析,即去分析Pattern串的自身规律,进而去优化匹配的效率. 例如字符串“ababcb”,明显看出是ab出现一组重复,若出现如下匹配模式:. 此时发生错误,一般情况下会选择移动Pattern一个位置来继续,事实证明效果不佳.

Java字符串的10大热点问题盘点

- - 极客521 | 极客521
下面我为大家总结了10条Java开发者经常会提的关于Java字符串的问题,如果你也是Java初学者,仔细看看吧:. 1、如何比较字符串,应该用”==”还是equals(). 总的来说,”==”是用来比较字符串的引用地址,而equals()才是比较字符串的值. 两个值相同的字符串用”==”比较结果有可能是false,而用equals()则一定为true.

十个最常见的Java字符串问题 - liushaobo

- - 博客园_首页
翻译自: Top 10 questions of Java Strings. 用”==”还是用equals(). 简单地说,”==”测试两个字符串的引用是否相同,equals()测试两个字符串的值是否相同. 除非你希望检查两个字符串是否是同一个对象,否则最好用equals(). 2.为什么对于安全性敏感的信息char[]要优于String.

Java实现字符串反转的8种9种方法

- - ITeye博客
注:对于第7种使用异或的方式来实现字符串的反转,如果不太看得明白的,可以参照另一篇博客:. * 二分递归地将后面的字符和前面的字符连接起来. * 取得当前字符并和之前的字符append起来. * 将字符从后往前的append起来. * 和StringBuffer()一样,都用了Java自实现的方法,使用位移来实现.

[记录]字符串相似度算法(编辑距离算法 Levenshtein Distance)

- - xilo's blog
在搞验证码识别的时候需要比较字符代码的相似度用到“编辑距离算法”,关于原理和C#实现做个记录. 编辑距离,又称Levenshtein距离(也叫做Edit Distance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数,如果它们的距离越大,说明它们越是不同. 许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符.

利用编辑距离(Edit Distance)计算两个字符串的相似度

- - Java - 编程语言 - ITeye博客
利用编辑距离(Edit Distance)计算两个字符串的相似度.         编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数. 许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符. 一般来说,编辑距离越小,两个串的相似度越大.