最小编辑距离问题：递归与动态规划
youngwind opened this issue · 13 comments
继上一篇 #104 ，本来是在研究虚拟 DOM 算法的，看到了 livoras 的这篇文章，觉得写得很好！珠玉在前，我便不再赘述了。该文章中提到：列表更新本质上是一个最小编辑距离问题，不过并未就此详细展开。今天，我们来具体看看这个问题。
问题
给定两个字符串 a 和 b，只允许以下三种操作：
- 插入一个字符；
- 删除一个字符；
- 替换一个字符。
求：把 a 转换成 b 的最小操作次数，也就是所谓的最小编辑距离。
举例： "xy" => "xz"，只需要把 y 替换成 z，因此，最小编辑距离为 1。
"xyz" => "xy"，只需要删除 z ，因此，最小编辑距离为 1。
求解这个问题，一般有两种思路：递归和动态规划。
递归
所谓递归，便是把大问题”分治“成类似的小问题。
假设，a 的长度是 m，b 的长度是 n，要求 a[1]a[2]...a[m] => b[1]b[2]...b[n] 的最小编辑距离，记为 d[m][n]。
- 如果 a[m] === b[n]，那么问题转化为求解：a[1]a[2]...a[m-1] => b[1]b[2]...b[n-1] 的最小编辑距离，因此 d[m][n] === d[m-1][n-1]。比如，"xyz" => "pqz" 的最小编辑距离等于 "xy" => "pq" 的最小编辑距离。
- 如果 a[m] !== b[n]，又分为三种情况：
- 比如，"xyz" => "efg" 的最小编辑距离等于 "xy" => "efg" 的最小编辑距离 + 1（因为允许插入操作，插入一个 "z"），抽象的描述便是 d[m][n] === d[m-1][n] + 1。
- 比如，"xyz" => "efg" 的最小编辑距离等于 "xyzg" => "efg" 的最小编辑距离 + 1，且因为最后一个字符都是 "g"，根据第一个判断条件，可以再等于 "xyz" => "ef" 的最小编辑距离 + 1，因此，得到结论："xyz" => "efg" 的最小编辑距离等于 "xyz" => "ef" 的最小编辑距离 + 1，抽象的描述便是：d[m][n] === d[m][n-1] + 1。
- 比如，"xyz" => "efg" 的最小编辑距离等于 "xyg" => "efg" 的最小编辑距离 + 1（因为允许替换操作，可以把 "g" 换成 "z"），再等于 "xy" => "ef" 的编辑距离 + 1（根据第一个判断条件），抽象的描述便是： d[m][n] === d[m-1][n-1] + 1。
- 上述三种情况都有可能出现，因此，取其中的最小值便是整体上的最小编辑距离。
- 如果 a 的长度为 0，那么 a => b 的最小编辑距离为 b 的长度；反过来，如果 b 的长度为 0，那么 a => b 的最小编辑距离为 a 的长度。
代码实现
/**
* 递归算法
* @param {string} a
* @param {string} b
* @param {number} i 字符串 a 的长度
* @param {number} j 字符串 b 的长度
* @returns {number} 从 a → b 的最小编辑距离
*/
function recursion(a, b, i, j) {
if (j === 0) {
return i;
} else if (i === 0) {
return j;
} else if (a[i - 1] === b [j - 1]) {
return recursion(a, b, i - 1, j - 1);
} else {
let m1 = recursion(a, b, i - 1, j) + 1;
let m2 = recursion(a, b, i, j - 1) + 1;
let m3 = recursion(a, b, i - 1, j - 1) + 1;
return Math.min(m1, m2, m3);
}
}动态规划
动态规划看起来跟递归很像，不过推理逻辑正好是反过来的。递归的逻辑是：“要求得 d[m][n]，先要求得 d[m-1][n-1]……”，动态规划的逻辑是：“先求得 d[m-1][n-1]，再求 d[m][n]……”这是它们的主要区别。
举个例子，在已知 d[0][0]，d[0][1]，d[1][0] 的前提下，要求 d[1][1]：
- 如果 a[1] === b[1]，那么 d[1][1] 等于 d[0][0]，也就是 0；
- 如果 a[1] !== b[1]，那么 d[1][1] 等于 d[0][1]、d[1][0] 和 d[0][0] 三者中的最小值 + 1，也就是 1。
接着用同样的方式，可以求得 d[1][2]、d[1][3]、……、d[1][n]，然后继续求得 d[2][1]、d[2][2]、……、d[2][n]，一直到 d[m][n]。代码实现如下：
/**
* 动态规划算法
* @param {string} a
* @param {string} b
* @returns {number} 从 a → b 的最小编辑距离
*/
function dynamicPlanning(a, b) {
let lenA = a.length;
let lenB = b.length;
let d = [];
d[0] = [];
for (let j = 0; j <= lenB; j++) {
d[0].push(j);
}
for (let i = 0; i <= lenA; i++) {
if (d[i]) {
d[i][0] = i;
} else {
d[i] = [];
d[i][0] = i;
}
}
for (let i = 1; i <= lenA; i++) {
for (let j = 1; j <= lenB; j++) {
if (a[i - 1] === b[j - 1]) {
d[i][j] = d[i - 1][j - 1];
} else {
let m1 = d[i - 1][j] + 1;
let m2 = d[i][j - 1] + 1;
let m3 = d[i - 1][j - 1] + 1;
d[i][j] = Math.min(m1, m2, m3);
}
}
}
return d[lenA][lenB];
}对比与实证
这两种算法哪一个更快呢？
我不知道如何从理论上去计算其时间复杂度和空间复杂度，因为对于复杂度的计算，我只能应付那种简单的，比如 n 重循环，我知道其时间复杂度是 n 次方。但是，对于这种稍微复杂一些的程序，我便不知所措了。
怎么办呢？ → 我决定从实证的角度去得到答案，也就是说，通过实际测量程序的运行时间，来衡量其时间复杂度。
我使用 jsPerf，建了一个 Test Case，从链接进去点击“Run Tests”，稍等片刻，便能看到程序运行的速度（指标 ops/sec 为 1s 内程序重复执行次数，数值越高代表程序运行越快），具体执行结果如下图所示。
从图中我们可以看到：递归的时间复杂度是指数级的，动态规划的时间复杂度是线性级的。
为什么动态规划快那么多呢？ → 从代码上我们能猜测一二：**动态规划需要存储一个矩阵d[m][n]，随着规模的增大，矩阵变得越来越大，对内存的占用也是越来越多的。这本质上是在用空间换时间。**当然，也是有办法可以优化其占用空间的，具体的可以看参考资料中明无梦的文章。另外，目前我还不知道该如何实际测量程序的空间复杂度，如果有知道的朋友，还望不吝赐教。
参考资料
@shadeofgod 已更新完毕。
看jsperf的图愣了一下，应该是单位时间内的运算次数成10倍，100倍下降，运算时间是增长的吧。
有点容易引起困惑。
@shadeofgod 此处确实写得不对，多谢指出，已更正。
preact的出现是为了解决了什么问题呢？单纯只是一个精简版的React吗?
@youngwind 那两者内部实现的方式差异大吗？
@MrErHu Preact除了只是实现一个精简版的React之外，内部还做了很多的hack，提升了较大的性能，虽然没有React的体系那么庞大，比如没有event system， 但是总体的经常使用的核心API是一致的，加之体积比较小，在一定的程度上更加利于移动端的使用场景，具体内部的实现差异不是很大，preact在内部的diff算法和react部部分不同，生命周期函数内部唤起的机制也有所不同，针对text node做了很多的优化。 我自己分析过preact的源码，通过注释的形式分析的， 需要的话你可以看看 preact_analyse
@wangning0 解释的真不错，谢谢了~去了解一下
动态规划，对于两个串，"abcdef" -> "abccde"
求出最小距离是2之后，react还需要如何判断移动哪些字符呢？
**空 a b c d e f
空 0 1 2 3 4 5 6
*a 1 0 1 2 3 4 5
*b 2 1 0 1 2 3 4
*c 3 2 1 0 1 2 3
*c 4 3 2 1 1 2 3
*d 5 4 3 2 1 2 3
*e 6 5 4 3 2 1 2
肉眼判断肯定是把abcdef中间插入c，末尾移除f，就可以转成abccde
程序怎么写？
动态规划和分治法（使用递归）的最大区别应该是子问题是否重叠，动态规划应用于子问题重叠（意味着可以使用缓存），而分治法子问题互不相交。
动态规划的两个特性：最优子结构和重叠子问题；
你的递归方法进行简单的修改也可以变为动态规划，它其实是自顶向下的求解问题，在递归到达递归边界时出栈并进行问题的计算，但是你没有对子问题进行缓存查询的逻辑，只是单纯的递归了；
你的动态规划方法，它其实是自底向上求解问题，对子问题进行了缓存和查询的逻辑；
@demonbibi 说的没错，画一个递归的图，就可以看出比如i-1，j-1的情况算了三次，
时间复杂度：动态规划优于递归