Levenshtein 算法

所谓Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，操作包括一切你使用的手段将一个字符串转换成另一个字符串，比如插入一个字符、删除一个字符..等等；操作次数越少，说明两个字符串距离Levenshtein Distance越小，表示两个字符串越想似。

应用最广泛的的当然就是DNA序列比对了。

此处算法思想用一个“代价表”表示（我这里这么称呼，因为比对过程中产生的代价总和就是字符串的距离），比如有两个字符串s1=“ABCDEFGZ”,s2="ABFDFEGXY"；则代价表如下：（代价表实现思想：若比较过程中两个字符相同，则直接取左上角代价，若不同，则取左上角、左、上三方代价最小值再加1.）

<caption>代价表</caption>
|
|
| A | B | C | D | E | F | G | Z |
|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| B | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| F | 3 | 2 | 1 | 1 | 2 | 3 | 3 | 4 | 5 |
| D | 4 | 3 | 2 | 2 | 1 | 2 | 3 | 4 | 5 |
| F | 5 | 4 | 3 | 3 | 2 | 2 | 2 | 3 | 4 |
| E | 6 | 5 | 4 | 4 | 3 | 2 | 3 | 3 | 4 |
| G | 7 | 6 | 5 | 5 | 4 | 3 | 4 | 3 | 4 |
| X | 8 | 7 | 6 | 6 | 5 | 4 | 5 | 4 | 4 |
| Y | 9 | 8 | 7 | 7 | 6 | 5 | 6 | 5 | 5 |

由上述表可得：s1=“ABCDEFGZ”与s2="ABFDFEGXY"的距离为5

程序实现如下：

package com.wxhi.main;

/**
 * Levenshtein Distance算法
 * @author wxshi
 *
 */
public class Levenshtein {

    /**
     * @param s1
     * @param s2
     * @return Levenshtein Distance
     */
    public double getStringDistance(String s1, String s2) {

        double distance[][];// 定义距离表
        int s1_len = s1.length();
        int s2_len = s2.length();

        if (s1_len == 0) {
            return s2_len;
        }
        if (s2_len == 0) {
            return s1_len;
        }
        distance = new double[s1_len + 1][s2_len + 1];

        // 二维数组第一行和第一列放置自然数
        for (int i = 0; i <= s1_len; i++) {
            distance[i][0] = i;
        }
        for (int j = 0; j <= s2_len; j++) {
            distance[0][j] = j;
        }
        // 比较，若行列相同，则代价为0，否则代价为1；
        for (int i = 1; i <= s1_len; i++) {
            char s1_i = s1.charAt(i - 1);
            // 逐一比较
            for (int j = 1; j <= s2_len; j++) {
                char s2_j = s2.charAt(j - 1);
                // 若相等，则代价取0；直接取左上方值
                if (s1_i == s2_j) {
                    distance[i][j] = distance[i - 1][j - 1];
                } else {
                    // 否则代价取1，取左上角、左、上 最小值 + 代价（代价之和便是最终距离）
                    distance[i][j] = getMin(distance[i - 1][j], distance[i][j - 1], distance[i - 1][j - 1]) + 1;
                }
            }
        }
        // 取二位数组最后一位便是两个字符串之间的距离
        return distance[s1_len][s2_len];
    }

    // 求最小值
    private double getMin(double a, double b, double c) {
        double min = a;
        if (b < min) {
            min = b;
        }
        if (c < min) {
            min = c;
        }
        return min;
    }
}