求编辑距离

高爽

发布于 2019-07-02 02:13:34

65800

代码可运行

文章被收录于专栏：高爽的专栏高爽的专栏

运行总次数：0

代码可运行

定义

编辑距离又称Leveinshtein距离，是由俄罗斯科学家Vladimir Levenshtein在1965年提出。编辑距离是计算两个文本相似度的算法之一，以字符串为例，字符串a和字符串b的编辑距离是将a转换成b的最小操作次数，这里的操作包括三种：

插入一个字符
删除一个字符
替换一个字符

举个例子，kitten和sitting的编辑距离是3，kitten -> sitten(k替换为s) -> sittin(e替换为i) -> sitting(插入g)，至少要做3次操作。

实现

用leva,b(i,j)lev_{a,b}(i,j)来表示a和b的Leveinshtein距离(i和j分别代表a和b的长度)，则：

当min(i,j)=0时，leva,b(i,j)=max(i,j)，一个字符串的长度为0，编辑距离自然是另一个字符串的长度当min(i,j)=0时，lev_{a,b}(i,j)=max(i,j)，一个字符串的长度为0，编辑距离自然是另一个字符串的长度
当ai=bj时，leva,b(i,j)=leva,b(i−1,j−1)，比如xxcz和xyz的距离=xxc和xy的距离当a_i=b_j时，lev_{a,b}(i,j)=lev_{a,b}(i-1,j-1)，比如xxcz和xyz的距离=xxc和xy的距离
否则，leva,b(i,j)为如下三项的最小值：否则，lev_{a,b}(i,j)为如下三项的最小值：

- leva,b(i−1,j)+1(删除ai)，比如xxc和xyz的距离=xx和xyz的距离+1lev\_{a,b}(i-1,j)+1(删除a\_i)，比如xxc和xyz的距离=xx和xyz的距离+1
- leva,b(i,j−1)+1(插入bj)，比如xxc和xyz的距离=xxcz和xyz的距离+1=xxc和xy的距离+1lev\_{a,b}(i,j-1)+1(插入b\_j)，比如xxc和xyz的距离=xxcz和xyz的距离+1=xxc和xy的距离+1
- leva,b(i−1,j−1)+1(替换bj)，比如xxc和xyz的距离=xxz和xyz的距离+1=xx和xy的距离+1lev\_{a,b}(i-1,j-1)+1(替换b\_j)，比如xxc和xyz的距离=xxz和xyz的距离+1=xx和xy的距离+1

用公式表示如下：

leva,b(i,j)=⎧⎩⎨⎪⎪⎪⎪⎪⎪if min(i,j)=0 max(i,j)if ai=bjleva,b(i−1,j−1)otherwisemin⎧⎩⎨⎪⎪leva,b(i−1,j)+1leva,b(i,j−1)+1leva,b(i−1,j−1)+1

lev_{a,b}(i,j)= \left{ \begin{array}{ll} if\space min(i,j)=0\qquad\space max(i,j)\ if\space a_i=b_j\qquad\qquad lev_{a,b}(i-1,j-1)\ otherwise\qquad\qquad min\left{ \begin{array}{ll} lev_{a,b}(i-1,j)+1\ lev_{a,b}(i,j-1)+1\ lev_{a,b}(i-1,j-1)+1 \end{array} \right. \end{array} \right.

递归实现

用上面的公式可以很容易的写出递归实现：

public static int levenshteinDistance(String left, String right) {
    return levenshteinDistance(left.toCharArray(), left.length(), right.toCharArray(), right.length());
}
private static int levenshteinDistance(char[] left, int leftLen, char[] right, int rightLen) {
    if (Math.min(leftLen, rightLen) == 0) {
        return Math.max(leftLen, rightLen);
    }
    if (left[leftLen - 1] == right[rightLen - 1]) {
        return levenshteinDistance(left, leftLen - 1, right, rightLen - 1);
    }
    return Math.min(levenshteinDistance(left, leftLen - 1, right, rightLen),
            Math.min(levenshteinDistance(left, leftLen, right, rightLen - 1),
                    levenshteinDistance(left, leftLen - 1, right, rightLen - 1))) + 1;
}

递归的实现比较简单，递归的思想是通过递归的形式，最终得到一个由不可继续分割(递归出口)的式子组成的表达式，最终会存在非常多的重复的不可继续分割的式子，造成大量的重复计算，所以很低效。

动态规划实现

递归是从后向前分解，那与之相对的就是从前向后计算，逐渐推导出最终结果，此法被称之为动态规划，动态规划很适用于具有重叠计算性质的问题，但这个过程中会存储大量的中间计算的结果，一个好的动态规划算法会尽量减少空间复杂度。

全矩阵

以xxc和xyz为例，建立一个矩阵，通过矩阵记录计算好的距离：

当min(i,j)=0时，leva,b(i,j)=max(i,j)当min(i,j)=0时，lev_{a,b}(i,j)=max(i,j)，根据此初始化矩阵的第一行和第一列：

依据上面的公式可以继续推导出第二行：

继续迭代，直至推导出最终结果：

这个过程记录了所有中间结果，空间复杂度为O(n2)O(n^2)，来看一下代码实现：

public static int levenshteinDistance(String left, String right) {
    // 创建矩阵
    int[][] d = new int[left.length() + 1][right.length() + 1];
    // 初始化第一列
    for (int i = 0; i <= left.length(); i++) {
        d[i][0] = i;
    }
    // 初始化第一行
    for (int j = 1; j <= right.length(); j++) {
        d[0][j] = j;
    }
    // 从第二行第二列开始迭代
    for (int i = 1; i <= left.length(); i++) {
        for (int j = 1; j <= right.length(); j++) {
            // 套公式计算
            if (left.charAt(i - 1) == right.charAt(j - 1)) {
                d[i][j] = d[i - 1][j - 1];
            } else {
                d[i][j] = Math.min(d[i - 1][j], Math.min(d[i][j - 1], d[i - 1][j - 1])) + 1;
            }
        }
    }
    // 最后一个格子即为最终结果
    return d[left.length()][right.length()];
}

两行

空间复杂度可以继续优化，我们计算当前行时，只依赖上一行的数据，所以我们只需要O(2n)O(2n)的空间复杂度，代码实现：

public static int levenshteinDistance3(String left, String right) {
    int[] pre = new int[right.length() + 1];// 上一行
    int[] current = new int[right.length() + 1];// 当前行
    // 初始化第一行
    for (int i = 0; i < pre.length; i++) {
        pre[i] = i;
    }
    for (int i = 1; i <= left.length(); i++) {
        current[0] = i;// 第一列
        for (int j = 1; j <= right.length(); j++) {
            // 套公式计算
            if (left.charAt(i - 1) == right.charAt(j - 1)) {
                current[j] = pre[j - 1];
            } else {
                current[j] = Math.min(current[j - 1], Math.min(pre[j], pre[j - 1])) + 1;
            }
        }
        // current -> pre
        System.arraycopy(current, 0, pre, 0, current.length);
    }
    return pre[pre.length - 1];
}

单行

我们还可以进一步优化，其实只需要一行就可以了，计算当前格子时，只需要左、上、左上的值，左面的值可以直接得到，上面的值是当前格子修改前的旧值，也可以直接得到，左上角的值是左面格子修改前的旧值，需要暂存，这时空间复杂度为O(n)O(n)。

代码实现：

public static int levenshteinDistance(String left, String right) {
    // 初始化当前行
    int[] d = new int[right.length() + 1];
    for (int i = 0; i < d.length; i++) {
        d[i] = i;
    }
    int leftTop, nextLeftTop;
    for (int i = 1; i <= left.length(); i++) {     
        leftTop = i - 1;// 当前行的左上角初始值
        d[0] = i;// 第一列
        for (int j = 1; j <= right.length(); j++) {
            nextLeftTop = d[j];// 暂存，此时d[j]为上一行的值，也是d[j+1]左上角的值
            // 套公式计算
            if (left.charAt(i - 1) == right.charAt(j - 1)) {
                d[j] = leftTop;
            } else {
                d[j] = Math.min(d[j - 1], Math.min(d[j], leftTop)) + 1;
            }
            leftTop = nextLeftTop;
        }
    }
    return d[d.length - 1];
}