关于最小编辑问题的算法学习

[Copyes]

开始

在写 snabbdom 复刻版的时候，发现里面有个很有趣的东西，就是在做移动节点的这个操作的时候并不是真正的去把节点移动了，而是通过插入节点，然后再把新的节点删掉。这个做法让想起了一个求最小编辑距离的问题。再 virtual dom 的节点更新就可以抽象成为一个求最小编辑距离的问题。那么这个问题具体是怎么样的，它对应的解法有具体是怎么样的，接下来就来具体看看。

正文

1、问题

给定 2 个字符串 a, b. 编辑距离是将 a 转换为 b 的最少操作次数，操作只允许如下 3 种：

插入一个字符，例如：xy -> xzy
删除一个字符，例如：xzy -> xy
替换一个字符，例如：xzy -> xwy

上面的求 a 转换为 b 的最少操作次数 就是所谓的最小编辑距离问题。

2、� 解法

递归

递归的本质就是用分治的思想将大的问题分成若干类似的小问题去解决。

假设字符串 a, 共 m 位，从 a[1] 到 a[m]
字符串 b, 共 m 位，从 b[1] 到 b[n]
d[m][n] 表示字符串 a[1]-a[m] 转换为 b[1]-b[n] 的编辑距离

看到上面的说法就可以转化成下面的递归规律：

• 1、当 a[m] === b[n]的时候

  • 那么实际的问题就相当去转化成为 a[1]...a[m-1] => b[1]...b[n-1]的问题了

• 2、当 a[m] !== b[n]的时候,又可以分成下面三种情况了：

  • xyz => lmn 可以看作是 xy => lmn 的最小编辑距离 + 1（因为允许插入一个字符的操作）。� 所以就是抽象成为求 d[m][n] => d[m-1][n] + 1
  • xyz => lmn 可以看作是 xyzn => lmn 的最小编辑距离 + 1，并且因为最后一个字符是一样的，根据第一个判定条件又可以转化成为 xyz => lm 的最小编辑距离 + 1。所以就是抽象成为 d[m][n] => d[m][n-1] + 1
  • xyz => lmn 可以看作是 xyn => lmn 的最小编辑距离 + 1（� 因为可以替换一个字符串），再根据第一个判定条件又可以转化成为 xy => lm 的最小编辑距离 + 1。所以就是抽象成为 d[m][n] => d[m-1][n-1] + 1

• 3、边界条件

  • 字符串 b 为空，那么 d[m][0]就是字符串 a 的长度
  • 字符串 a 为空，那么 d[0][n]就是字符串 b 的长度

代码实现：

function recursion(a, b, m, n) {
  if (m === 0) {
    return n
  } else if (n === 0) {
    return m
  } else {
    let d1 = recursion(a, b, m - 1, n) + 1
    let d2 = recursion(a, b, m, n - 1) + 1
    let d3 = recursion(a, b, m - 1, n - 1) + 1
    return Math.min(d1, d2, d3)
  }
}

动态规划

上面的递归的解法是从后面到前面的解法，比如我想知道 d[m][n],那么我可能就必须要知道 d[m-1][n-1],依次类推。那么动态规划就是从前到后面的解法。就是我先知道了若干字问题了，那么我根据这些子问题可以求到对应的原问题。举个 🌰：

我知道了 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[2][1]、d[2][2]、......、� 一直到 d[m][n]为止

代码实现：

function dynamicDistance(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]
}

最后

感谢：

1、编辑距离
2、最小编辑距离问题：递归与动态规划
3、动态规划求编辑距离