5.1. 编辑距离¶

编辑距离 是衡量把一个字符串转换为另一个字符串所需最小更改次数的度量。 这里我们的目标是设计一个算法，在给定两个字符串的情况下，计算出这个最小的更改次数。 两种无趣的情况是： （1）如果两个字符串完全相同，那么需要 0 次操作； （2）如果其中一个字符串的长度为零，那么所需操作的次数就是另一个字符串的长度。

按照动态规划的方法，第一步是用递归方式求解该问题。 与大多数递归解法一样，这个算法很容易理解。 首先，先给出一些符号及其定义，以便更容易理解后面的描述。

递归算法如下：

1. 基本情况检查。该算法的基本情况很简单：当你用完了要比较的字符时，即 S 或 T 中任一字符串的字符耗尽。如果两个字符串的字符都用完了，返回的数值就是零。但是如果其中一个字符串的字符用完了，而另一个还没用完，返回的数值是长度非零的那个字符串中剩余的字符数。

2. 检查 S(i) == T(j) 是否成立。

   1. 1）如果它们匹配，递归调用 ED(S,T,i-1,j-1)。既然它们匹配，这个位置不需要做任何操作，所以该值不增加操作计数。

   2. 2）如果它们不匹配，就需要三次递归调用。依次为：

      • A) 替换（Substitution）：递归调用 ED(S,T,i-1,j-1) 并加一*。

      • B) 插入（Insertion）：递归调用 ED(S,T,i,j-1) 并加一*。

      • C) 删除（Deletion）：递归调用 ED(S,T,i-1,j) 并加一*。

      • D) 选择要执行的操作。由于编辑距离是一个返回最小值的函数，只需找出能产生最小更改次数（操作计数）的操作即可。如果出现平局，就按照递归调用的顺序所确立的优先次序执行：替换、插入、删除。

* 由于这些递归调用各自对应一个具体的操作，因此每次递归调用返回的操作计数（即返回值）都会增加 1。

初始函数调用形如 ED(S,T,m,n)。注意，在本算法中并不使用标准的从 0 开始的数组编号；字符串从字符位置 1 开始，而不是 0 。

操作说明：

替换

起始字符串中的当前字符变为目标字符串中的当前字符。S(i) = T(j)

示例：

起始字符串：sit

目标字符串：sat

比较两个字符串的第二个字符时，"i" 变成了 "a"，即一次替换。

插入

目标字符串比起始字符串长，所以把目标字符串的当前字符插入到起始字符串当前字符的位置。S.insert(i,T(j))

示例：

起始字符串：red

目标字符串：read

比较两个字符串的倒数第二个字符时，插入一个 "a" 使字符串匹配。

删除

起始字符串比目标字符串长，所以把起始字符串的当前字符删除。S.remove(i)

示例：

起始字符串：123456

目标字符串：13456

为使字符串匹配，需要删除起始字符串的第二个字符 "2"。

下面是递归实现的编辑距离算法（Java 语言）。:

int editDistance(String S, String T, int i, int j)
{
        //base cases 基本情况
        if (i === 0)
                return j;
        if (j === 0)
                return i;

        //recursive call, start with match check 递归调用，先进行匹配检查
        if (S.charAt(i) == T.charAt(j))
                return editDistance(S, T, i-1, j-1);
        else
        {       //no match, recurse three times 不匹配，递归三次

                int sub = editDistance(S, T, i-1, j-1) + 1;
                int ins = editDistance(S, T, i, j-1) + 1;
                int del = editDistance(S, T, i-1, j) + 1;

                return Math.min(Math.min(sub, ins), del);
        }
}

这个递归算法可以处理编辑距离问题，但随着字符串长度的增加，调用栈会呈指数级增长。它之所以指数级增长，是因为在任意一次字符比较时，最多可能产生三次递归调用，所以复杂度为 \(O(3^{max(m,n)})\)。递归调用树可以通过下面的动画查看。

注意，在这些动画中，起始字符串是 "cat"，目标字符串是 "kate"。每个结点中的数字表示递归函数调用的参数，这里分别是指起始字符串和目标字符串中用于比较的字符位置。为简单起见，假设起始字符串和目标字符串是全局定义的。

显然，要比较任何大型字符串，递归解法都不是最优的。正如之前动态规划的演示所示，对该问题采用动态方法会使运行更加高效（即以线性时间运行）。

下面的动画演示了与之前 N-Choose-K 和 0/1 背包问题演示相同的过程：修剪递归调用树以填充动态网格。

注意，由于方法上的相似性，驱动下面这个动画的大部分代码采用了一种抽象形式，它实际上运行的是全部三个动态规划问题可视化的第二个动画。如果你已经看过 N-Choose-K 和 0/1 背包问题，你就已经见过这个动画了，只是可视化的算法不同而已。如果你看不出相似之处，也不用担心。这三个算法演示（N-Choose-K、0/1 背包和编辑距离）的重点，是揭示为问题创建动态解的同一抽象方法。由于这三个演示的第二步几乎完全相同，我们只制作了一个动画来处理它们全部。

如你所见，这种动态方法的效率为 \(O(m*n)\)，显然优于递归方法的效率 \(O(3^{max(m,n)})\)。事实上，就这个具体例子而言，在原来的 19 次函数调用中，动态方法消除了其中 10 次调用，效率提升了 52.6%，而这还只是一个 小 例子！

网格填满之后，动态解法的最后一步是找出到达解的最优路径。下面的动画正是展示这一点。请注意过渡文本，它描述的是每次比较时执行哪个操作。理解下一格子的哪个位置对应哪个操作是关键。为简单起见，左上表示替换，左侧表示插入，上方表示删除。

注意，在这个动画中没有删除操作。如果起始字符串比目标字符串更长，那么就不会有插入操作，而会有一到多次删除操作。

下面是与上面相同的编辑距离算法，但采用了动态实现。如你所见，使用了记忆化技术来提供查找表，存储重复的函数调用。网格的初始设置可能是最难理解的部分。这段代码会生成一个与之前动画网格同类型的二维数组，但不包含用于显示待比较字符串的初始行和列。:

 int editDistance(String start, String end) {
         int startMax = start.length; int endMax = end.length; int array[][] = new int[startMax + 1][endMax + 1]

        //initialize all array values to zero 将所有数组值初始化为零
        for (int i = 0; i <= startMax; i++)
        {
                for (int j = 0; j <= endMax; j++)
                {
                        array[i][j] = 0;
                }
        }

        //initialize the base cases 初始化基本情况
        for (int i = 1; i <= startMax; i++)
        {
                array[i][0] = i;
        }

        for (int j = 1; j <= endMax; j++)
        {
                array[0][j] = j;
        }

        //fill in the grid 填充网格
        for (int i = 1; i <= startMax; i++)
        {
                for(int j = 1; j <= endMax; j++)
                {
                        //match check 匹配检查
                        if (start.charAt(i-1) == end.charAt(j-1))
                                array[i][j] = array[i-1][j-1];
                        else
                        {
                                int sub = array[i-1][j-1] + 1;
                                int ins = array[i][j-1] + 1;
                                int del = array[i-1][j] + 1;

                                array[i][j] = Math.min(Math.min(sub, ins), del);
                        }
                }
        }

        return array[startMax][endMax];
}

递归版编辑距离与这个动态版编辑距离的一个主要区别，在于网格的填充方式。正如上面第二个动画所示，并非每个格子都填入了值。这些缺失的值对于确定两个字符串之间的实际编辑距离完全没有必要，因此被跳过了。而正如第三个动画所示，这个动态实现会把每个格子都填入相应的值。也许你能想出只填充必要格子的动态方法。

5.2. 练习 1¶

现在你已经看到了算法的实际运行过程，希望你已经理解网格中的值从何而来。更重要的是，你应该理解算法如何选择下一步要执行的操作。要完成下面的测验，关键在于最终理解在任意时刻将执行哪个操作。对于任意给定的格子，请判断哪个操作会产生最低的总操作计数。

5.3. 练习 2¶

在下一个测验中，请确定应填入高亮格子的正确值。