java分析文本相似度、相差度

 

package util;

 

/**

 * 计算文本相差度/相似度

 * 返回数字越大，两个字符串相差就越大

 * @author Administrator

 *

 */

public class Distance {

 

   

    public static void main(String[] args){

       Distance dis = new Distance();

       String s1="比干缘何落马死，勾践因此可吞吴省长市长共商议，抓好米袋菜篮子饭店是事实上是个 规范的炎热他依然额头";

       String s2="比干缘何落马死勾践因此可吞吴省长市长共商议，抓好米袋分舵是否但是发斯蒂芬斯蒂芬的说法都是菜篮子";

//     System.out.println((s1.length()));

       System.out.println(dis.LD(s2, s1));

      

    }

    // ****************************

    // Get minimum of three values

    // ****************************

 

    private int Minimum(int a, int b, int c) {

       int mi;

 

       mi = a;

      

       if (b < mi) {

           mi = b;

       }

      

       if (c < mi) {

           mi = c;

       }

      

       return mi;

 

    }

 

    // *****************************

    // Compute Levenshtein distance

    // *****************************

 

    public int LD(String s, String t) {

       int d[][]; // matrix

       int n; // length of s

       int m; // length of t

       int i; // iterates through s

       int j; // iterates through t

       char s_i; // ith character of s

       char t_j; // jth character of t

       int cost; // cost

 

       // Step 1

 

       n = s.length();

       m = t.length();

       if (n == 0) {

           return m;

       }

       if (m == 0) {

           return n;

       }

       d = new int[n + 1][m + 1];

 

       // Step 2

 

       for (i = 0; i <= n; i++) {

           d[i][0] = i;

       }

 

       for (j = 0; j <= m; j++) {

           d[0][j] = j;

       }

 

       // Step 3

 

       for (i = 1; i <= n; i++) {

 

           s_i = s.charAt(i - 1);

 

           // Step 4

 

           for (j = 1; j <= m; j++) {

 

              t_j = t.charAt(j - 1);

 

              // Step 5

 

              if (s_i == t_j) {

                  cost = 0;

              } else {

                  cost = 1;

              }

 

              // Step 6

 

              d[i][j] = Minimum(d[i - 1][j] + 1, d[i][j - 1] + 1,

                     d[i - 1][j - 1] + cost);

 

           }

 

       }

 

       // Step 7

 

       return d[n][m];

 

    }

 

}