Levenshtein

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

public double levenshtein(final String a, final String b)
{
    int[][] ret=new int[a.length()+1][b.length()+1];

    for (int i = 0; i <= a.length(); i++)
    {
        for (int j = 0; j <= b.length(); j++)
        {
            if(i==0)
            {
                ret[i][j]=j;
            }else if(j==0)
            {
                ret[i][j]=i;
            }else if(a.charAt(i-1)==b.charAt(j-1))
            {
                ret[i][j]=ret[i-1][j-1];
            }else
                ret[i][j]=1+Math.min(ret[i-1][j-1],Math.min(ret[i][j-1],ret[i-1][j]));
        }
    }
    return ret[a.length()][b.length()];
}
/**
 * 由 levenshtein 优化而成的写法更省空间
 */
public double levenshteinPro(final String a, final String b)
{
    int[] v0 =new int[b.length()+1];
    int[] v1 =new int[b.length()+1];
    int[] temp;

    for (int i = 0; i <= b.length(); i++)
        v0[i]=i;

    for (int i = 0; i < a.length(); i++)
    {
        v1[0]=i+1;
        for (int j = 0; j < b.length(); j++)
        {
            int cost=1;
            if(a.charAt(i)==b.charAt(j))
            {
                //相同不需要替换 不需+1
                cost=0;
            }
            v1[j+1]=cost + Math.min(v1[j],Math.min(v0[j],v0[j+1]));
        }
        System.err.println(Arrays.toString(v1));
        temp=v1;
        v1=v0;
        v0=temp;
    }
    return v0[b.length()];
}