相似度Levenshtein

class Main {
    public static void main(String[] args) {
        String src = "周一是今天吗";
        String des = "周一是今天";

        float sd = LevenshteinDistance.getInstance().getSimilarityDegree(src,des);
        System.out.println(sd);
    }
}


/**
 * 文本相似度匹配
 * Levenshtein distance算法
 */
class LevenshteinDistance{
    private static LevenshteinDistance _instance = null;
    public static LevenshteinDistance getInstance(){
        if (_instance == null){
            return new LevenshteinDistance();
        }
        return _instance;
    }
  
    public int LowerOfThree(int first, int second, int third){
        int min = first;
        if (second < min)
            min = second;
        if (third < min)
            min = third;
        return min;
    }
    
    
    /**
     * 文本相似度匹配
     * Levenshtein distance算法
     */
    public float getSimilarityDegree(String str1, String str2){
        
        int val = 0;
        if(str1==null||str2==null){
            return 0.0f;
        }
        int n = str1.length();
        int m = str2.length();


        if (n == 0){
            val = m;
        }else if (m == 0){
            val = n;
        }else{
            int[][] Matrix = new int[n + 1][ m + 1];

            for (int i = 0; i <= n; i++){
                Matrix[i][0] = i;
            }
    
            for (int j = 0; j <= m; j++){
                Matrix[0][j] = j;
            }
    
            int temp = 0;  
            for (int i = 1; i <= n; i++){
                for (int j = 1; j <= m; j++){
                    temp = str1.charAt(i-1) ==str2.charAt(j-1)?0:1;
                    Matrix[i][j] = LowerOfThree(Matrix[i-1][j] + 1, Matrix[i][j-1] + 1, Matrix[i-1][j-1] + temp);
                }
            }
            val = Matrix[n][m];
        }
        int maxLen = n>m?n:m;
        return 1 - (float)val/maxLen;
    }

}