编辑距离

编辑距离可以用来判断两个字符串的相似性。量测方式是把一个字符串转变为另外一个字符串所需的操作次数。操作类型只有三种：增加，删除和替换。这样子，字符串的相似性则可以用1-编辑距离/MAX(字符串1长度,字符串2长度)来度量。

递归计算编辑距离

首先计算编辑距离，会用到几个递归逻辑。假设有两个字符串A和B。A[0,n]代表A的前n个字符，B[0,m]代表B的前m个字符。A[n]代表A的最后一个字符，B[m]代表B的最后一个字符。编辑距离记作D，则：

• A[n]==B[m]时，D(A[0,n],B[0,m]) == D(A[0,n-1],B[0,m-1])，即D(fxy,fay) == D(fx,fa)
• A[n]!=B[m]时，取下面三个的最小值

1. 删除A[n]，D(A[0,n],B[0,m]) == D(A[0,n-1],B[0,m])+1，即D(fxy,fab) == D(fx,fab)+1
2. 往A插入B[m]，D(A[0,n],B[0,m]) == D(A[0,n],B[0,m-1])+1，即D(fxy,fab) == D(fxyb,fab)+1 == D(fxy,fa)+1
3. 将A[n]替换为B[m]，D(A[0,n],B[0,m]) == D(A[0,n-1],B[0,m-1])+1，即D(fxy,fab) == D(fxb,fab)+1 == D(fx,fa)+1

递归边界：

当B为空字符串时，表示要删除全部A，所以D=|A|

当A为空字符串时，表示要把B都加进A，所以D=|B|

非递归、“可视化”计算编辑距离

假设要计算字符串ivan1和ivan2的编辑距离。首先如下图创建一个矩阵，按012345的自然数来初始化第一行和第一列。

然后对于留空的格子，每个格子都先查看他左边，左上角，上边格子的最小值min，然后根据当前格子的字符是否相等，相等的话，本格子就直接是min，否则就min+1。如此填完整个矩阵，最后右下角的那个格子便是编辑距离。

java实现

import java.util.Arrays;

/**
 * @author cellargalaxy
 * @time 2018/11/14
 */
public class Test {
    public static void main(String[] args) {
        String s1 = "ace";
        String s2 = "abcdef";
        int[][] ints = createInitMatrix(s1, s2);
        System.out.println("initMatrix");
        printMatrix(ints);
        System.out.println();

        System.out.println("writeMatrix");
        writeMatrix(s1, s2, ints);
        printMatrix(ints);
        System.out.println();

        int editDistance = ints[ints.length - 1][ints[ints.length - 1].length - 1];
        System.out.println("editDistance: " + editDistance);
    }

    public static final int editDistance(String s1, String s2) {
        if (s1.length() == 0) {
            return s2.length();
        }
        if (s2.length() == 0) {
            return s1.length();
        }
        //创建一个经过初始化的矩阵
        int[][] ints = createInitMatrix(s1, s2);
        //把矩阵填满
        writeMatrix(s1, s2, ints);
        //填满后，矩阵右下角的值就是编辑距离
        return ints[ints.length - 1][ints[ints.length - 1].length - 1];
    }

    private static final int[][] createInitMatrix(String s1, String s2) {
        int[][] ints = new int[s1.length() + 1][s2.length() + 1];
        //初始化第一行和第一列
        for (int i = 0; i < ints[0].length; i++) {
            ints[0][i] = i;
        }
        for (int i = 0; i < ints.length; i++) {
            ints[i][0] = i;
        }
        return ints;
    }

    private static final void writeMatrix(String s1, String s2, int[][] ints) {
        //第一行和第一列已经在初始化的时候填写
        for (int i = 1; i < ints.length; i++) {
            for (int j = 1; j < ints[i].length; j++) {
                //找出左边，左上角，上边的最小值
                int min = Math.min(ints[i - 1][j], Math.min(ints[i][j - 1], ints[i - 1][j - 1]));
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    //如果当前字符相同，则直接赋为min
                    ints[i][j] = min;
                } else {
                    //否则赋为min+1
                    ints[i][j] = min + 1;
                }
            }
        }
    }

    private static final void printMatrix(int[][] ints) {
        for (int[] anInt : ints) {
            System.out.println(Arrays.toString(anInt));
        }
    }
}

参考文章：

编辑距离 (Edit distance)

编辑距离算法（Edit Distance）