15-问题分析

4.4.1　问题分析

编辑距离是指将一个字符串变换为另一个字符串所需要的最小编辑操作。

给定两个序列X={x₁，x₂，x₃，…，x_m}和Y={y₁，y₂，y₃，…，y_n}，找出X和Y的编辑距离。

例如：X=（A，B，C，D，A，B），Y=（B，D，C，A，B）。如果用穷举法，会有很多种对齐方式，暴力穷举的方法是不可取的。那么怎么找到编辑距离呢？

首先考虑能不能把原问题变成规模更小的子问题，如果可以，那就会容易得多。

要求两个字符串X={x₁，x₂，x₃，…，x_m}和Y={y₁，y₂，y₃，…，y_n}的编辑距离，那么可以求其前缀X_i={x₁，x₂，x₃，…，x_i}和Y_j={y₁，y₂，y₃，…，y_j}的编辑距离，当i=m，j=n时就得到了所有字符的编辑距离。

那么能不能用动态规划算法呢？

下面我们分析该问题是否具有最优子结构性质。

（1）分析最优解的结构特征

假设已经知道d[i][j]是X_i={x₁，x₂，x₃，…，x_i}和Y_j={y₁，y₂，y₃，…，y_j}的编辑距离最优解。这个假设很重要，我们都是这样假设已经知道了最优解。

那么两个序列无论怎么对齐，其右侧只可能有如下3种对齐方式：

• 如图4-19所示。需要删除x_i，付出代价1，那么我们只需要求解子问题{x₁，x₂，x₃，…，x_i−1}和{y₁，y₂，y₃，…，y_j}的编辑距离再加1即可，即d[i][j]=d[i−1][j]+1。d[i−1][j]是X_i−1和Y_j的最优解。

反证法证明： 设d[i−1][j]不是X_i−1和Y_j的最优解，那么它们一定存在一个最优解d’，d’<d[i−1][j]。如果在X_i−1的后面添加一个字符x_i，d’+1也是X_i和Y_j的最优解，因为d’+1<d[i−1][j]+1=d[i][j]，所以d[i][j]不是X_i和Y_j的最优解，这与假设d[i][j]是X_i和Y_j的最优解矛盾，问题得证。

• 如图4-20所示。需要插入y_j，付出代价1，那么我们只需要求解子问题{x₁，x₂，x₃，…，x_i}和{y₁，y₂，y₃，…，y_j−1}的编辑距离再加1即可，即d[i][j]=d[i][j−1]+1。d[i][j−1]是X_i和Y_j−1的最优解。

同理可证。

• 如图4-21所示。如果x_i=y_j，付出代价0，如果x_i≠y_j，需要替换，付出代价1，我们用函数diff(i，j)来表达，x_i=y_j时，diff(i，j)=0；x_i≠y_j时，diff(i，j)=1。那么我们只需要求解子问题{x₁，x₂，x₃，…，x_i−1}和{y₁，y₂，y₃，…，y_j−1}的编辑距离再加diff(i，j)即可，即d[i][j]=d[i−1][j−1]+ diff(i，j)。d[i−1][j−1]是X_i−1和Y_j−1的最优解。

同理可证。

（2）建立最优值递归式

设d[i][j]表示X_i和Y_j的编辑距离，则d[i][j]取以上三者对齐方式的最小值。

编辑距离递归式：

（3）自底向上计算最优值，并记录最优值和最优策略

i=1时：{x₁}和{y₁，y₂，y₃，…，y_n}中的字符一一比较，按递归式求解并记录编辑距离。

i=2时：{x₂}和{y₁，y₂，y₃，…，y_n}中的字符一一比较，按递归式求解并记录编辑距离。

……

i=m时：{x_m}和{y₁，y₂，y₃，…，y_n}中的字符一一比较，按递归式求解并记录编辑距离。

（4）构造最优解

如果仅仅需要知道编辑距离是多少，上面的求解过程得到的编辑距离就是最优值。如果还想知道插入、删除、替换了哪些字母，就需要从d[i][j]表格中倒推，输出这些结果。