算法思想之动态规划(五)——最小编辑距离问题

2019-06-01 本文已影响0人复旦猿

前言

今天我们继续讨论经典的动态规划问题之最小编辑距离问题。

找零钱问题

问题描述

对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。例如将"abc"转化为"adc"，c0=5，c1=3，c2=100，最小代价为8。

问题分析

我们先解释下问题描述中为什么最小代价是8。如果插入、删除和修改操作的代价相同，显然，"abc"->"adc"直接将'b'->'d'即可。但是由于多了c0=5，c1=3，c2=100的条件，所以直接进行修改操作其代价为100，显然不是最小代价。最小代价对应的操作应该是使用插入、删除操作代替修改操作——先在'a'与'c'中插入'd'，然后删除'b'，或者先删除'b'，在插入'd'。这样最小代价为8。
其实，该问题实质上是求解 $A \to B$ 的最小编辑距离，只不过对每种操作赋予了权值。假设两字符串A和B的长度分别为 $n$ 和 $m$ 。我们需要构建一个 $(n+1) \times (m+1)$ 的矩阵 $dp$ ，代表 $A[0:i] \to B[0:j]$ 的最小代价为 $dp[i][j]$ 。可能你会疑问，为什么是 $(n+1) \times (m+1)$ ，而不是 $n \times m$ 呢? 观察下面的矩阵，你可能会找到答案。我们需要在两字符串前添加空字符串来得到增加、删除操作所对应的代价作为初始值。

	''	'a'	'd'	'c'
''	0	5	10	15
'a'	3
'b'	6
'c'	9

对于矩阵第0行第0列，代表由 $'' \to ''$ ，显然代价为0，即 $dp[0][0] = 0$ ;
对于矩阵第0行第1列，代表由 $'' \to a$ ，其代价为 $c_0$ ，即 $dp[0][1] = c_0 = 5$ ;
对于矩阵第0行第2列，代表由 $'' \to ad$ ，其代价为 $2*c_0$ ，即 $dp[0][1] = 2 * c_0 = 10$ ;
依次类推， $dp[0][j] = j * c_0，0 \leq j \leq m$ 。
同样的，对于 $dp[i][0] = i * c_1，0 \leq i \leq n$ 。
那么当 $1 \leq i \leq n, 1 \leq j \leq m$ 时， $dp[i][j] = ?$
下面，我们分两种情况进行讨论：
(1) 当 $A[i] == B[j]$ 时，可能的操作即最小代价有以下几种情况：

不需要进行任何操作，此时最小代价就是 $A[0:i-1] \to B[0:j-1]$ 的最小代价，即 $dp[i-1][j-1]$ ；
先 $A[0:i] \to B[0:j-1]$ ，然后增加 $B[j]$ ，此时最小代价为 $A[0:i] \to B[0:j-1]$ 的最小代价 + $c_0$ ，即 $dp[i][j-1] + c_0$ ；
先将 $A[0:i-1] \to B[0:j]$ ，然后删除 $A[i]$ ，此时最小代价为 $A[0:i-1] \to B[0:j]$ 的最小代价 + $c_1$ ，即 $dp[i-1][j] + c_1$ 。

此时， $dp[i][j] = min\{dp[i-1][j-1], dp[i][j-1] + c0, dp[i-1][j] + c1\}$ ;
(2) 当 $A[i] \neq B[j]$ 时，可能的操作即最小代价有以下几种情况：

直接将A[i]替换为B[j]，此时最小代价就是 $A[0:i-1] \to B[0:j-1]$ 的最小代价 + $c_2$ ，即 $dp[i-1][j-1] + c_2$ ；
先 $A[0:i] \to B[0:j-1]$ ，然后增加 $B[j]$ ，此时最小代价为 $A[0:i] \to B[0:j-1]$ 的最小代价 + $c_0$ ，即 $dp[i][j-1] + c_0$ ；
先将 $A[0:i-1] \to B[0:j]$ ，然后删除 $A[i]$ ，此时最小代价为 $A[0:i-1] \to B[0:j]$ 的最小代价 + $c_1$ ，即 $dp[i-1][j] + c_1$ 。

此时， $dp[i][j] = min\{dp[i-1][j-1] + c_2, dp[i][j-1] + c0, dp[i-1][j] + c_1\}$ ;
需要注意的是，当 $c_2 \geq c_0 + c_1$ 时，需要令 $c_2 = c_0 + c_1$ ，这是因为修改操作可以用增加+删除操作代替，这样的代价比直接进行修改操作的代价要低。问题分析一开始也给出了说明。

代码实现

通过问题分析，可以很容易得用代码实现，下面给出算法的java实现。

public class MinCost {
    public int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
        return core(A, n, B, m, c0, c1, c2);
    }

    public int core(String A, int n, String B, int m, int c0, int c1, int c2) {
        if (A.length() == 0 || B.length() == 0) {
            return 0;
        }
        A = " " + A;
        B = " " + B;
        int[][] dp = new int[n + 1][m + 1];
        // 初始化第0行
        dp[0][0] = 0;
        for (int i = 1; i < m + 1; i++) {
            dp[0][i] = c0 * i;
        }

        // 初始化第0列
        for (int j = 1; j < n + 1; j++) {
            dp[j][0] = c1 * j;
        }

        //update=delete+insert,如果update花费更多就用delete+insert的花费之和替换
        if (c2 >= c0 + c1) {
            c2 = c0 + c1;
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if (A.charAt(i) == B.charAt(j)) {
                    //如果两个字符串中A[i],B[j]的字符都一样的
                    //1.什么都不做就行，0操作
                    int dontChange = dp[i - 1][j - 1];
                    //2.比如由abcd→abcd=abc→abcd+A串删除d
                    int delete = dp[i - 1][j] + c1;
                    //3.比如由abcd→abcd=abcd→abc+B串插入d
                    int insert = dp[i][j - 1] + c0;
                    dp[i][j] = Math.min((Math.min(dontChange, delete)), insert);
                } else {
                    //1. A abcd → B abce = A abc→B abc + (A abcd → B abce, 替换d为e)
                    int replace = dp[i - 1][j - 1] + c2;
                    //2.比如由A abcd→B abce=A abc→B abce+A串删除d
                    int delete = dp[i - 1][j] + c1;
                    //3.比如由A abcd→B abce=A abcd→B abc+B串插入e
                    int insert = dp[i][j - 1] + c0;
                    dp[i][j] = Math.min((Math.min(replace, delete)), insert);
                }
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) {
        MinCost minCost = new MinCost();
        String A = "abc";
        int n = A.length();
        String B = "adc";
        int m = B.length();
        int c0 = 3;
        int c1 = 5;
        int c2 = 3;
        int res = minCost.findMinCost(A, n, B, m, c0, c1, c2);
        System.out.println(res);
    }
}

经典问题

未来几篇博文，我将继续对经典的动态规划问题进行整理，敬请关注~
由于本人水平有限，文章难免有欠妥之处，欢迎大家多多批评指正！

写在最后

欢迎大家关注我的个人博客复旦猿。