基于 Levenshtein distance 算法求解字符串最小编辑步骤

[weijieblog]

基于 Levenshtein distance 算法的字符串 diff 算法

之前的博文介绍了如何利用 Levenshtein distance 算法求解从一个字符串到另外一个字符串的编辑距离。在博文的结尾提到了一种通过回溯 Levenshtein distance 算法生成的表格，求得从一个字符串到另外一个字符串变化步骤的算法，算法有如下效果。

diff('saturday', 'sunday')
/* output
[{
  content: 'n',
  index: 4,
  type: 'UPDATE'
}, {
  content: 't',
  index: 2,
  type: 'REMOVE',
}, {
  content: 'a',
  index: 1,
  type: 'REMOVE',
}]
*/

在之前的博文中，levenshteinDistance 函数将 matrix 的最后一个单元格的值返回，而这里所说的 levenshteinDistance 填满的表格，指的是整个 matrix 。

注释部分表示算法输出的结果，输出的数组表示：

• 将 saturday 中 index 为 4 的字符替换为 n。（即 r 替换为 n）
• 将 saturday 中 index 为 2 的字符删除。（即删除 t）
• 将 saturday 中 index 为 1 的字符删除。（即删除 a）

回溯法求解编辑路径

之前的博文通过自底向上法完成了一个表格，如下：

-	-	s	a	t	u	r	d	a	y
-	0	1	2	3	4	5	6	7	8
s	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

回溯的路径

既然是回溯，那么就要从这个表格的最后一个单元格出发，按照一定的路径向第一个单元格移动，即从右下角向左上角移动。在这里，如何选择回溯的路径将是这个算法成功的关键。Levenshtein distance 的数学定义描述了每个单元格的值都是根据其左边的单元格，左上方的单元格，上方的单元格的值的关系确定的，具体的确定方式可以看之前的博文。同样的我们在回溯的时候也要考虑当前单元格和其左边的单元格，左上方的单元格，上方的单元格的值的关系。图例如下：

-	-	s	a	t	u	r	d	a	y
-	0	1	2	3	4	5	6	7	8
s	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3 (leftOver)	4 (over)
y	6	5	4	4	5	5	5	4 (left)	3 (origin)

起点 origin 可以往 left 方向， leftOver 方向， over 方向出发。但我们的目的既然是求解从一个字符串到另外一个字符串最少编辑的步骤，那么在选择方向的时候得满足两点。

1. 朝着 left ， leftOver 和 over 中编辑距离（也就是值）最小的方向出发。
2. 而当这几个方向的编辑距离有相同的时候，优先往 leftOver 方向出发。

关于第 2 点，是因为 leftOver 方向代表了更改或是不操作， 而 left 和 over 则分别代表删除和插入，一次删除加一次插入的效果才相当于一次更改，所以优先选择更改编辑成本较小。而不操作没有编辑成本。移动的方向和其编辑操作的关系，下个小节会说明。

根据这两条规则，很快就可以确定回溯的路径，如下，加粗字体表示回溯时会走的路径：

-	-	s	a	t	u	r	d	a	y
-	0	1	2	3	4	5	6	7	8
s	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

回溯的方向和相应的编辑操作

在回溯的路径上，单元格里边的数字每发生一次变化，就代表发生了一次编辑操作，比如。

-	-	s	a	t	u	r	d	a	y
-	0	1	2	3	4	5	6	7	8
s	1	0(1,1)	1(2,1)	2(3,1)	3	4	5	6	7
u	2	1	1	2	2(4,2)	3	4	5	6
n	3	2	2	2	3	3(5,3)	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

• 从 (5,3) 到 (4,2)
• 从 (3,1) 到 (2,1)
• 从 (2,1) 到 (1,1)

可以看到，路径上数字的变化次数是 3 次，这和我们执行 levenshteinDistance 的结果是一致的。那么每一次变化分别都代表了什么操作呢。可以通过观察数字变化前的单元格（[(5,3),(3,1),(2,1)]）得出些头绪，如下：

其中 - 后面的是编辑好的字符串，而 - 之前的是待编辑的字符串。

// (5,3) ：下一步往 `leftOver` 方向走到 (4,2)

// from (5,3)
satur - day
sun - day

// to (4,2)
satu - nday
su - nday

// 可见将 r 改为 n 即可



// (3,1)：下一步往 `left` 方向走到 (2,1)

// from (3,1)
sat - unday
s - unday

// to (2,1)
sa - unday
s - unday

// 可见删掉 t 即可



// (2,1)：下一步往 `left` 方向走到 (1,1)

// from (2,1)
sa - unday
s - unday

// to (1,1)
s - unday
s - unday

// 可见删掉 a 即可

总结一下，就是：

• 往 left 方向走是删除操作。
• 往 over 方向走是插入操作。
• 往 leftOver 方向走是更新操作或是不操作，由当前字符决定，比如从 (1,1) 到 (0,0) 就是不操作。

diff 算法的 Javascript 实现

我认为是时候贴代码了

// 定义三种编辑方式
var REMOVE = 'REMOVE',
    INSERT = 'INSERT',
    UPDATE = 'UPDATE'

// 求解从 list1 到 list2 的最小编辑步骤
// 这里的 levenshteinDistance 不再是返回 matrix 的最后一个单元格，而是返回整个 matrix
// diff('saturday', 'sunday', levenshteinDistance('saturday', 'sunday', match))
/* output
[{
  content: 'n',
  index: 4,
  type: 'UPDATE'
}, {
  content: 't',
  index: 2,
  type: 'REMOVE',
}, {
  content: 'a',
  index: 1,
  type: 'REMOVE',
}]
*/
var diff = function (list1, list2, matrix) {
  var len1 = list1.length,
      len2 = list2.length,
      edits = [],
      minimus,
      current,
      over,
      left,
      leftOver,
      x,
      y

  // 设置最后一个单元格为起点
  x = len1
  y = len2
  current = matrix[x][y]

  // 开始回溯
  while (x > 0 || y > 0) {
    // 路径到达了最左边的一列，就只能往上走，于是出现了要往 list1 开头连续添加元素的情况。
    // 例如： def => abcdef 会连续进入下方的 if 三次，每次进入分别插入 c，b，a。
    if (x === 0) {
      edits.push({type: INSERT, index: x-1, content: list2[y-1]})
      y--
      continue
    }
    // 路径到达了最上面的一行，就只能横着往左走，于是出现了要往 list1 开头连续删除元素的情况。
    // 例如：abcdef ＝> def 会连续进入下方的 if 三次，每次进入分别删除 c，b，a。
    if (y === 0) {
      edits.push({type: REMOVE, index: x-1, content: list1[x-1]})
      x--
      continue
    }

    // 找到有可能会前往的三个方向的的值
    over = matrix[x][y-1]
    left = matrix[x-1][y]
    leftOver = matrix[x-1][y-1]

    // 总是忘三个方向中值最小的方向前进
    minimus = Math.min(over, left, leftOver)    
    switch (minimus) {
      // 优先往左上方前进，更新操作或不操作
      case leftOver:
        // 当值变化，表示有编辑操作发生
        if (current > minimus) {
          edits.push({type: UPDATE, index: x-1, content: list2[y-1]})
        }
        current = leftOver
        x--
        y--
        break

      // 往上方前进，插入操作
      case over:
        // 当值变化，表示有编辑操作发生
        if (current > minimus) {
          edits.push({type: INSERT, index: x-1, content: list2[y-1]})
        }
        y--
        current = over
        break

      // 往左方前进，删除操作
      case left:
        // 当值变化，表示有编辑操作发生
        if (current > minimus) {
          edits.push({type: REMOVE, index: x-1, content: list1[x-1]})
        }
        x--
        current = left
        break
    }
  }
  return edits
}

小结

这个 diff 函数，除了可以用来比较以外还可以用来比较列表，像下面一样。

diff(['jquery', 'reactjs', 'redux', 'require'], ['jquery', 'react', 'reflux', 'webpack', 'elm'], 
            levenshteinDistance(['jquery', 'reactjs', 'redux', 'require'], ['jquery', 'react', 'reflux', 'webpack', 'elm'], match))

另外，通过自定义的 match 函数（见之前的博文），它可以用来比较更多的东西，比如嵌套的数组。如果你乐意，这个 diff 函数也可以扩写为比较 DOM 树的函数，就像 React 的那个一样。

当然，这个 diff 方法还有很多不完善的地方，比如：

diff('saturday', 'sunday', levenshteinDistance('saturday', 'sunday', match))

这样的接口，实在算不上优美，另外，它也没经过太多的优化。

[ghjagus]

非常感谢博主，很好的文章，浅显易懂

[p2227]

比较DOM树的情况有不一样的地方。因为创建和销毁dom的代价是昂贵的，如果两个dom没有特定的标识，要比较它们是否一样也挻昂贵的。所以在比较dom的时候更加偏向于移动dom的位置，然后如果没有Key就直接增或者删除了。你觉得应该到dom比较需要有什么改进的地方？