Levenshtein Distance编辑距离算法

在使用ES进行fuzzy查询时，可以实现模糊查询。其中参数fuzziness用来设置允许的最大编辑距离，那么编辑距离如何计算的呢？

ES中提到了使用Levenshtein Distance(莱文斯坦距离)来计算编辑距离，其中修改、删除和插入都将编辑距离算作为1。

例如现在需要将dag编程dog，那么最简单的方式就是将a编程o即可实现，而它们之间的编辑距离则为1。

算法实现

对于简单的单词可能一眼就能看出来，但是复杂的单词可能就难以看出来了。这里我将使用动态规划的方法去计算出编辑距离，其大致步骤如下：

初始化一个矩阵(M,N)，其中M和N分别是两个输入字符串的长度。
从左上角向右下角填充矩阵，每个水平或者垂直跳转分别对应于一个插入或者删除。
定义每个操作成本为1，如果两个字符串不匹配，则对角跳转的代价为1，否则为0。
按照上面规则填充完所有矩阵，最终右下角的数字就是两个字符串的编辑距离。

例如现在计算dag变成dog的编辑距离：

首先初始化矩阵如左边的图，接着就是开始计算了。这里我先定义矩阵中的点如下，[x,y]其中x代表横向字符，y代表竖向字符。对于[d,d]该点的值字符相同，其计算逻辑如下：

取该点左边和上边的数字加1，计算后分别为2和2。左上的点不变，则为0。
求计算后左边(2)，上面(2)和左上(0)的最小值，最后就是0。

对于字符不同的点，计算有稍许区别。对于[a,d]计算如下：

取该点左边、上边和左上三个点，其值分别为0、2、1。
求出上面三个点中的最小值，然后加1。最后算出该值为1。

上图中所有的点都是按照该逻辑计算得出，从最终[g,g]的值可以看出，dag变成dog只需要编辑一步即可完成。

java代码实现

public class App {

    public static int ld(String source,String target){
        int x = source.length();
        int y = target.length();
        //定义矩阵
        int[][] matrix = new int[y+1][x+1];
        //初始化矩阵
        for (int i = 0; i <= x; i++) {
            matrix[0][i] = i;
        }
        for (int i = 0; i <= y; i++) {
            matrix[i][0] = i;
        }

        for (int i = 1; i <= y; i++) {
            for (int j = 1; j <= x; j++) {
                boolean b = target.charAt(i - 1) == source.charAt(j - 1);
                int cost = b ? 0 : 1;
                //左
                int z = matrix[i][j - 1] + 1;
                //上
                int s = matrix[i-1][j] + 1;
                //左上
                int zs = matrix[i-1][j-1] + cost;
                //求最小值
                int temp = Math.min(z,Math.min(s,zs));
                matrix[i][j] = temp;
            }
        }

        return matrix[y][x];
    }

    public static void main(String[] args) {
        int ld = ld("dog", "dg");
        System.out.println(ld);
    }
}

该算法通常可以使用在拼写检查、文本近似度匹配等方面。例如源字符串hello，现在给出world、hell、hello三个字符串，求哪个字符串与源字符串最相似。这里直接使用编辑距离算法计算如下：

    public static void main(String[] args) {
        String source = "hello";
        String s1 = "world";
        String s2 = "hell";
        String s3 = "hello";
        System.out.println(ld(source,s1));
        System.out.println(ld(source,s2));
        System.out.println(ld(source,s3));
    }