编辑距离解法及证明

前言

最近我邀请了我们团队的同事来分享他们在日常工作中的一些知识沉淀（主要还是我自己懒）。今天这篇的作者是我司内部 redis-proxy 的 maintainer libo，清华高材生，也是我们目前系统工程方面非常厉害的专家。未来的话他也会来分享一下我们遇到的诸如 kernel 的坑，redis cluster mget 性能调优等经验。

你看上去是面试题，其实还是比面试题难一点的，当然啦我们的面试中不会出这种难度的，所以大家还是可以放心的投简历啦~

问题介绍

给定字符串 w1 ， w2 ， 以及如下对字符串的操作：

• 删除字符串中指定位置的字符

• 在字符串中插入指定字符

• 将字符串中指定字符替换为另外的字符

使用上述操作将 w1 变为 w2 所需要的最少操作次数即为 w1 与 w2 的编辑距离

解法介绍

编辑距离是一道经典的动态规划的题目，定义 f(i, j) 为 w1[0, i] => w2[0, j] 的编辑距离，则有状态转移方程为：

f(i, j) = f(i - 1, j - 1) if w1[i] == w2[j] else  min(f(i - 1, j), f(i - 1, j - 1), f(i, j - 1)) + 1#边界条件f(0, 0) = 0  if w1[0] == w2[0] else  1f(0, j) = j if w1[0] == w2[j] else f(0, j - 1) + 1f(i, 0) = i if w1[i] == w2[0] else f(i - 1, 0) + 1

证明

当 w1[i] == w2[j] 时， 显然有 f(i, j) = f(i - 1, j - 1) 。当 w1[i] != w2[j] 时， 不妨将两个单词分别记为： w1 a 与 w2 b 。

假设 w1 a => w2 b 最少需要 x 个步骤， w1 a => w2 最少需要 y1 个步骤， w1 => w2 最少需要 y2 个步骤， w1 => w2 b 最少需要 y3 个步骤。

则有推论：y1 + 1 >= x; y2 + 1 >= x; y3 + 1 >= x ，使用反证法即可证明。

接下来我们证明：x == min(y1 + 1, y2 + 1, y3 + 1)

首先我们容易证明所有的操作序列都可以统一调整顺序为先进行删除操作(记为 d 操作)，然后进行插入操作(记为 i 操作)，最后进行替换操作(记为 r 操作)，并且我们可以把同类操作进行调整顺序使得操作从前往后进行。这样的调整操作顺序不会导致操作的数量发生改变，可以方便我们讨论。

考察 w1 a => w2 b 所有可能的操作序列的组合:

如果 w1 a => w2 b 全部是 d 操作，那么最后一步一定是 d last a ，即 w1 a => w2 b a => w2 b ，那么就有 x - 1 个步骤一定能把 w1 变成 w2 b

所以有 x - 1 >= y3 && x >= y3 + 1 ，于是有 x == y3 + 1

如果 w1 a => w2 b 全部是 i 操作，那么最后一步一定是 i last b ，即 w1 a => w2 => w2 b ，那么就有 x - 1 个步骤可以把 w1 a 变成 w2

所以有 x - 1 >= y1 && x >= y1 + 1 ，于是有 x == y1 + 1

如果 w1 a => w2 b 全部是 r 操作，那么最后一步一定是 r last a to b ，即 w1 a => w2 a => w2 b ，那么就有 x - 1 个步骤可以把 w1 变成 w2

所以有 x - 1 >= y2 && x >= y2 + 1 ，于是有 x == y2 + 1

如果 w1 a => w2 b 是 d i 操作，分别讨论：

• 如果 d 操作没有在 a 上执行过，那么就是 w1 a => [一系列 d 操作] => w1' a => [一系列 i 操作] => w2 => [i] => w2 b

我们构造 w1 a => [同样的 d 操作] => w1' a => [同样的 i 操作] => w2 ，所以 x - 1 个步骤可以把 w1 a => w2 ，所以有 x - 1 >= y1 && x <= y1 + 1 故而 x == y1 + 1

• 如果 d 操作过 a ，那么就是 w1 a => [一系列 d 操作] => w1' a => [d] => w1' => [一系列 i 操作] => w2 b

我们构造 w1 => [同样的 d 操作] => w1' => [一系列的 i 操作] => w2 b , 所以 x - 1 个步骤可以实现 w1 => w2 b ，所以有 x - 1 >= y3 && x <= y3 + 1 故而 x == y3 + 1

如果 w1 a => w2 b 是 d r 操作, 分别讨论：

• 如果 d 操作没有在 a 上执行，那么就是 w1 a => [一系列 d 操作] => w1' a => [一些列 r 操作] => w2 a => [r] => w2 b

我们构造 w1 => [一系列 d 操作] => w1' => [一系列 r 操作] => w2 ，所以 x - 1 个步骤可以把 w1 => w2 ，所以有 x - 1 >= y2 && x <= y2 + 1 故而 x == y2 + 1

• 如果 d 操作过 a ，那么就是 w1 a => [一系列 d 操作] => w1' a => [d] => w1' => [一系列 r 操作] => w2 b

我们构造 w1 => [一系列 d 操作] => w1' => [一系列 r 操作] => w2 b ，所以 x - 1 个步骤可以把 w1 => w2 b ,所以有 x - 1 >= y3 && x <= y3 + 1 故而 x == y3 + 1

如果 w1 a => w2 b 是 i r 操作，分别讨论：

• 如果 i 操作没有越过 a ，那么就是 w1 a => [一系列 i 操作] => w1' a => [一系列 r 操作] => w2 a => [r] => w2 b

我们构造 w1 => [一系列 i 操作] => w1' => [一系列的 r 操作] => w2 ，所以 x - 1 个步骤可以把 w1 => w2 ，所以有 x - 1 >= y2 && x <= y2 + 1 故而 x == y2 + 1

• 如果 i 操作过 a ，那么就是 w1 a => [一系列 i 操作] => w1' a => [一系列的 i 操作] => w1' a w1'' => [ i 操作，最后的 b ] => w1' a w1'' b => [一系列的 r 操作]（r 操作肯定不会超过 w1'a 的位置, 因为后面的字符都是 i 操作插入的新字符） => w2 b

我们构造 w1 a => [一系列 i 操作] => w1' a => [一系列 i 操作] => w1' a w1'' => [一系列的 r 操作] => w2 ，所以 x - 1 个步骤可以把 w1 a => w2 ，所以有 x - 1 >= y1 && x <= y1 + 1 故而 x == y1 + 1

如果 w1 a => w2 b 是 d i r 操作，分别讨论：

1. 如果 d 操作没有操作过 a ，那么就是 w1 a => [一系列 d 操作] => w1' a => [一系列 i 操作] => [一系列 r 操作] => w2 b ，现在我们知道 w1' a => [一系列 i 操作] => [一系列 r 操作] => w2 b ，类比上面的方法，分开讨论：

• 如果 i 操作没有超过 a ，那么就是 w1 a => [一系列 d 操作] => w1' a => [一系列 i 操作] => w1'' a => [一系列 r 操作] => w2 a => [r] => w2 b

我们构造 w1 => [一系列 d 操作] => w1' => [一系列 i 操作] => w1'' => [一系列 r 操作] => w2 ，所以 x - 1 个步骤可以把 w1 => w2 ，所以有 x - 1 >= y2 && x <= y2 + 1 故而 x == y2 + 1

• 如果 i 操作超过 a , 那么就是 w1 a => [一系列 d 操作] => w1' a => [一系列 i 操作] => w1'' a => [一系列 i 操作] => w1'' a w1''' => [i 操作，最后的 b ] => w1'' a w1''' b => [一系列 r 操作] => w2 b

我们构造 w1 a => [一系列 d 操作] => w1' a => [一系列 i 操作] => w1'' a => [一系列 i 操作] => w1'' a w1''' => [一系列 r 操作] => w2 ，所以 x - 1 个步骤可以把 w1 a => w2 ，所以有 x - 1 >= y1 && x <= y1 + 1 故而 x == y1 + 1

1. 如果 d 操作操作过 a ，那么就是 w1 a => [一系列 d 操作] => w1' a => [d] => w1' => [一系列 i 操作] => [一系列 r 操作] => w2 b

我们构造 w1 => [一系列 d 操作] => w1' => [一系列 i 操作] => [一系列 r 操作] => w2 b ，所以 x - 1 个步骤可以把 w1 => w2 b ，所以有 x - 1 >= y3 && x <= y3 + 1 故而 x == y3 + 1

通过枚举所有的操作序列组合，得到结论：x 的取值一定是 y1 + 1 ， y2 + 1 ， y3 + 1 中的一个，所以根据定义有：x == min(y1 + 1, y2 + 1, y3 + 1)。

因此得出最终的状态转移方程。