【Similarity calculation】 Levenshtein Distance

Levenshtein Distance

概念：
首先由俄国科学家Levenshtein提出的，又叫Levenshtein Distance。
是一种字符串之间相似度计算的方法。给定两个字符串S、T，将S转换成T所需要的删除，插入，替换操作的数量就叫做S到T的编辑路径。而最短的编辑路径就叫做字符串S和T的编辑距离。

分析：
例子：S=“eeba”   T="abac"   我们可以按照这样的步骤转变：
(1) 将S中的第一个e变成a;
(2) 删除S中的第二个e;
(3) 在S中最后添加一个c;
那么S到T的编辑路径就等于3。当然，这种变换并不是唯一的。
但如果3是所有变换中最小值的话，那么我们就可以说S和T的编辑距离等于3了。

动态规划解决编辑距离
动态规划(dynamicprogramming)是一种解决复杂问题最优解的策略。
它的基本思路就是：将一个复杂的最优解问题分解成一系列较为简单的最优解问题，再将较为简单的的最优解问题进一步分解，直到可以一眼看出最优解为止。

例子：S=“eeba”   T="abac" 。
首先定义一个函数
edit(i, j)：它表示第一个字符串S长度为i的子串si（S[0...i]）到第二个字符串T长度为j的子串T[0...j]的编辑距离.

如果S只有1个字符e、T只有1个字符a，那么就可以立即得到S和T的编辑距离edit(0,0)=1(将e替换成a)    ------------ 替换一个
如果S中有1个字符e、T中有2个字符ab，可以分解成：edit(0,1)=edit(0,0)+1 (将e替换成a后，在添加一个b)。 ------------ 替换一个，增加一个
如果S中有2个字符ee，T中有2个字符ab，可以分解成：edit(1,1)=min(edit(0,1)+1, edit(1,0)+1, edit(0,0)+f(1,1)).

这样我们可以得到这样一些动态规划公式：     

        如果i=0且j=0        edit(0, 0) = 1
        如果i=0且j>0        edit(0, j) = edit(0, j-1)+1
        如果i>0且j=0        edit(i, 0) = edit(i-1, 0)+1
        如果i>0且j>0        edit(i, j) = min(edit(i-1, j)+1, edit(i,j-1)+1, edit(i-1,j-1)+f(i, j) )
 
  f(i, j)：表示S中第i个字符s(i)转换到T中第j个字符s(j)所需要的操作次数。
  如果s(i)==s(j)，则不需要任何操作f(i, j)=0； 否则，需要替换操作，f(i, j)=1 。

这就是将长字符串间的编辑距离问题一步一步转换成短字符串间的编辑距离问题，直至只有1个字符的串间编辑距离为1。

相似度计算
相似度 = 1 - edit(S.length, T.length) / Math.Max(S.length, T.length)
例如：
如果str1="ivan"，str2="ivan"，没有经过转换。那么经过计算后等于 0。相似度=1-0/Math.Max(str1.length,str2.length)=1
如果str1="ivan1"，str2="ivan2"，str1的"1"转换"2"，转换了一个字符，所以距离是1，相似度=1-1/Math.Max(str1.length,str2.length)=0.8

 
public class SimilarityCalculate {
    //Levenshtein Distance
    private int edit(String source, String target) {
        int n = source.length();
        int m = target.length();
        int i, j; //
        char schar, tchar; //
        int temp; //
 
        if (n == 0)
            return m;
        if (m == 0)
            return n;
 
        int d[][] = new int[n + 1][m + 1];
 
        // initialization
        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++) {
            schar = source.charAt(i - 1);
            for (j = 1; j <= m; j++) {
                tchar = target.charAt(j - 1);
                if (schar == tchar) {
                    temp = 0;
                } else {
                    temp = 1;
                }
                int one = d[i - 1][j] + 1;
                int two = d[i][j - 1] + 1;
                int three = d[i - 1][j - 1] + temp;
                d[i][j] = (one = one < two ? one : two) < three ? one : three;
            }
        }
        return d[n][m];
    }
 
    // get the similarity ratio of two strings
    public float getSimilarityRatio(String source, String target) {
        return 1 - (float) edit(source, target)
                / Math.max(source.length(), target.length());
    }
 
    //main
    public static void main(String[] args) {
        SimilarityCalculate sc = new SimilarityCalculate();
        String source = "中国";
        String target = "中文";
        System.out.println("Distance = " + sc.edit(source, target) +
                "\tsimilarityRatio = " + sc.getSimilarityRatio(source, target));
 
        source = "SUNNY";
        target = "hgjdSUN";
        System.out.println("Distance = " + sc.edit(source, target) +
                "\tsimilarityRatio = " + sc.getSimilarityRatio(source, target));
 
    }
 
}

 Result
Distance = 1    similarityRatio = 0.5
Distance = 6    similarityRatio = 0.14285713