最小编辑距离问题:递归与动态规划

@youngwind 2017-06-14 02:21:03发表于 youngwind/blog 算法

继上一篇 #104 ,本来是在研究虚拟 DOM 算法的,看到了 livoras 的这篇文章,觉得写得很好!珠玉在前,我便不再赘述了。该文章中提到:列表更新本质上是一个最小编辑距离问题,不过并未就此详细展开。今天,我们来具体看看这个问题。

问题

给定两个字符串 a 和 b,只允许以下三种操作:

  1. 插入一个字符;
  2. 删除一个字符;
  3. 替换一个字符。

求:把 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]。

  1. 如果 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" 的最小编辑距离。
  2. 如果 a[m] !== b[n],又分为三种情况:
    1. 比如,"xyz" => "efg" 的最小编辑距离等于 "xy" => "efg" 的最小编辑距离 + 1(因为允许插入操作,插入一个 "z"),抽象的描述便是 d[m][n] === d[m-1][n] + 1。
    2. 比如,"xyz" => "efg" 的最小编辑距离等于 "xyzg" => "efg" 的最小编辑距离 + 1,且因为最后一个字符都是 "g",根据第一个判断条件,可以再等于 "xyz" => "ef" 的最小编辑距离 + 1,因此,得到结论:"xyz" => "efg" 的最小编辑距离等于 "xyz" => "ef" 的最小编辑距离 + 1,抽象的描述便是:d[m][n] === d[m][n-1] + 1。
    3. 比如,"xyz" => "efg" 的最小编辑距离等于 "xyg" => "efg" 的最小编辑距离 + 1(因为允许替换操作,可以把 "g" 换成 "z"),再等于 "xy" => "ef" 的编辑距离 + 1(根据第一个判断条件),抽象的描述便是: d[m][n] === d[m-1][n-1] + 1。
    4. 上述三种情况都有可能出现,因此,取其中的最小值便是整体上的最小编辑距离。
  3. 如果 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]:

  1. 如果 a[1] === b[1],那么 d[1][1] 等于 d[0][0],也就是 0;
  2. 如果 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 内程序重复执行次数,数值越高代表程序运行越快),具体执行结果如下图所示。
result
从图中我们可以看到:递归的时间复杂度是指数级的,动态规划的时间复杂度是线性级的。
为什么动态规划快那么多呢? → 从代码上我们能猜测一二:**动态规划需要存储一个矩阵d[m][n],随着规模的增大,矩阵变得越来越大,对内存的占用也是越来越多的。这本质上是在用空间换时间。**当然,也是有办法可以优化其占用空间的,具体的可以看参考资料中明无梦的文章。另外,目前我还不知道该如何实际测量程序的空间复杂度,如果有知道的朋友,还望不吝赐教。

参考资料

  1. 编辑距离, By 明无梦
  2. 动态规划求编辑距离, By 残阳似血