一种diff算法：Myers

diff

git是我们日常工作中最经常使用到的工具，而其中diff又是最常用到的功能，我们使用这个功能去查看代码的变更信息，今天我们就来学习一下diff算法的实现。

diff算法可以对一个文件编辑前后的状态进行比较，计算出其中删除和新增的内容，这样我们就能够直观看出该文件的变更情况。

我们首先来看一个例子：

a = ABCABBA
b = CBABAC

假设我们对文本a进行一系列编辑操作之后，得到了文本b，而diff操作就是要计算出这些编辑操作。

一种可能的编辑序列是先把原来的内容全部删除，然后插入新的内容：

- A
- B
- C
- A
- B
- B
- A
+ C
+ B
+ A
+ B
+ A
+ C

然而，上面的信息无法有效展示a是如何一步步变更到b的，因此上面的diff并没有什么实际意义。通常源代码的变更，会保留原来的大部分内容，而只对其中部分内容做删除和添加，我们通过diff操作是希望看到其中被删除或者插入的代码段，而不是像上面这样，全部删除然后替换成新的内容。

我们更希望看到是diff是下面这种：

- A
- B
  C
+ B
  A
  B
- B
  A
+ C

这种使用最少的变更把a转换成b，我们可以很明显的看出a是如何一步步转变到b的。然后这并不是唯一：

1.  - A       2.  - A       3.  + C
    - B           + C           - A
      C             B             B
    - A           - C           - C
      B             A             A
    + A             B             B
      B           - B           - B
      A             A             A
    + C           + C           + C

上面几种都是经过最少的变更。我看可以看到，一段文本从a变更到b的编辑过程并不是唯一的。

diff算法的目的是提供一种在某些方法比较理想的diff生成策略。然而，我们除了希望diff的变更尽量少之外，也有其他方面的考量，我们希望生成的diff更够尽量直观，符合我们的操作逻辑。

比如，当我们修改文件的时候，我们总是先删除一些旧的内容，然后再添加一些新的内容，因此在上面的例子中，我们会觉得第2种会比第3种更加直观

而当我们更新一个代码块的时候，总数先全部删掉然后再插入新的内容，而不是删插交替。

Good:   - one         Bad:    - one
        - two                 + four
        - three               - two
        + four                + five
        + five                + six
        + six                 - three

我们可以看到上面的例子中，第一种会比第二种更加直观。

而如果对于代码的变更，我们也更希望能够符合代码的结构逻辑：

Good:   class Foo                   Bad:    class Foo
          def initialize(name)                def initialize(name)
            @name = name                        @name = name
          end                             +   end
      +                                   +
      +   def inspect                     +   def inspect
      +     @name                         +     @name
      +   end                                 end
        end                                 end

比如上面的例子种，我们新增了一个方法，我们希望新增的end是属于新增函数的一部分，而不是原来函数的一部分，这样我们就能够很直观的看出这里是新增了一个方法。

而Myers算法就是一个能够符合这些考量的生成策略。

Myers算法

myers通过贪心策略，在发现一个文本差异之前尽可能多的消费相同的内容，因此在上面新增inspect方法的例子中，第一次出现的end不会被识别为新增，这能有效防止第二种diff情况的发生。并且，删除操作总是优于插入操作，因此生成的diff中，删除操作总数能够先出现（除非没有内容被删除）。

Myers算法是基于查找最短编辑脚本（shortest edit script, SES）的思想提出的。

最短编辑脚本查找问题可以被建模成图搜索问题。

我们继续拿上面的文本a = ABCABBA和文本b = CBABAC来说明。

首先我们构建这样一个图：

在上面的坐标系中，当我们位于原点(0,0)时，表示我们现在有一个字符串a；

当我们向右走，也就是增加x坐标的时候，对应的从a中删除一个字符，比如我们从(0,0) - > (1,0)时，我们从a中删除字符A，这时候我们当前的文本就变成了BCABBA；

而当我们向下走，也就是增加y坐标的时候，对应的从b中插入一个字符，比如我们从(1,0) -> (1,1)的时候，对应的插入b中的字符C，这时候的文本变成了CBCABBA；

在上面的某些位置上面还有斜向下的虚线，比如从(1,1) -> (2,2)，这时候表示a[1]==b[1]，这时候保留该字符，并且同时增加x坐标和y坐标；

而当我们沿某一条路线从(0,0)走到(7,6)，就代表字符串a经过一系列编辑操作之后转换成了字符串b。

我们把上面的向右走记作del操作，向下走记为ins操作，沿虚线走记为mov操作，只有执行del操作和ins操作才会让字符串发生变更。我们可以看到，从(0,0)到(7,6)有很多条路径可达，最多需要7+6次del和ins操作，也就是执行全删全增操作。

myers算法的思想很简单，就是要找出一条从(0,0)到(7,6)的路径，让这条路径中的del和ins操作尽量的少，这就要求要尽量执行mov操作，并且当出现分支选择的时候，del操作能够优先于ins操作。

我们对上面的图，从(0,0)开始，按照次序进行遍历，最终可以可到下面的遍历结果：

首先执行第一次编辑操作，我们可以从(0,0) -> (1,0)，或者从(0,0) - > (0,1)

接着执行第二次编辑操作，我们要在第一次操作的基础上进行，因为del操作优先于ins操作，因此我们要优先扩展(1,0)这个点，从(1,0)可以走到(1,1)和(2,0)，又因为(1,1)到(2,2)以及(2,0)到(3,1)存在虚线，mov操作不会令文本内容发生变更，并不是编辑操作，还记得上面说的贪心策略吗？myers尽可能的消费相同文本内容，因此从(1,0)最终走到了(2,2)和(3,1)；接着扩展(0,1)这个点，(0,1)可以走到(2,2)和(2,4)

接着执行第三次、第四次…操作，直到第一次达到(7,6)这个坐标，第一次到达说明这时候的编辑次数是最少的，最终的遍历结果如上图所示。

我们可以看到，每一次的编辑都是基于上次的编辑结果进行的，我们在每次编辑中，都基于上次的结果选择向右或者向下走一步，然后再执行0次或者多次mov操作，从而达到当前编辑结果。

为了更直观的发现算法的规律，我们把上图逆时针旋装45°：

在上图中，横坐标d表示编辑次数，也就是目前为止已经执行了多少次del或者ins编辑操作，也即图的搜索深度；而纵坐标k = x - y，当我们向右移动时，k值会加1，当向下移动时，k值会减1，而当沿着虚线移动时，k值并不会变化。我们需要记录指定d时，每个k值可以达到的最远记录，只需要记录当前给定d和k时，对应的x就行了，因为y = x - k。

现在我们可以来看一下myers算法的执行过程：

我们首先从0到(len(a)+len(b))遍历d
每次迭代b时，我们以步长为2从-d到d遍历k；这里为什么步长是2呢？仔细观察上图，当前d的节点都是从d-1的节点扩展而来，d-1的节点要么向右走，k加1，要么向下走，k减1，这时候同一个d的相邻的两个k之间差值就是2。
对于给定的d和k值，我们根据上一轮遍历的结果，决定当前的最佳位置，这里的最佳位置意味着取x值最大的点，因为这就意味着优先执行del操作。当前(d,k)的点可以从(d-1,k-1)向右走一步，也可以从(d-1,k+1)向下走一步。当(d-1,k+1)的x值比(d-1,k-1)的大，则其优先级更高，因为它已经执行了更多的删除操作，而当具有相同的x值时，应该选择(d-1,k-1)，这时候向右走执行del操作。

Code

type Diffable interface {
	LenA() int           // length of src
	LenB() int           // length of dest
	Equal(int, int) bool // compare src[ai] and dest[bi]
}

func Myers(ab Diffable) EditScript {
	aLen := ab.LenA() // 获取原文本a的长度
	bLen := ab.LenB() // 目标文本b的长度
	max := aLen + bLen // 最大的编辑次数是aLen+bLen，即完全替换内容
    // 这里v是一个稀疏数组，并且这里空间分配实际上也过大，可以进一步优化
    v := make([]int, 2*max+1) // 保存指定d时，对应k的x值，因为k可能是负数，这里实际使用max作为0
	trace := make([][]int, 0) // 保存每个d的v
search:
	// myers
    // 从0到max遍历d
    // d==0的时候，可能执行MOV操作，即(d,v)=(0,0)的时候，x不一定为0
	for d := 0; d <= max; d++ {
        // 保存上一轮迭代的v
        // 第一次迭代的时候，保存一个空的v，方便后面的回溯
		vc := make([]int, 2*max+1)
		copy(vc, v)
        // trace[d]保存的是d-1轮的v
		trace = append(trace, vc)
		// 按照步长为2从-d到d迭代k
		for k := -d; k <= d; k += 2 {
            // 很容易发现，k最小是-bLen,最大是aLen，因此这里可以有一个判断，跳过无效的k值
			if k < -bLen || k > aLen {
				continue
			}
			var x int
            // 如果k==-d，这时候只能由(d-1,k+1)向下走
            // 如果k==d，这时候只能由(d-1,k-1)向右走
            // 如果 (d-1,k+1)的x值大于(d-1,k-1)，则说明优先级大，往下走
            // 否在 (d-1,k-1)往右走
			if k == -d || (k != d && v[max+k-1] < v[max+k+1]) {
				x = v[max+k+1]
			} else {
				x = v[max+k-1] + 1
			}

            // k=x-y，因此y=x-k
			y := x - k
            // 判断是否可以执行MOV操作
			for x < aLen && y < bLen && ab.Equal(x, y) {
				x++
				y++
			}

            // 设置当前(d,k)的x值
			v[max+k] = x
			// 判断是已经到到目标
			if x == aLen && y == bLen {
				break search
			}
		}
	}
 	
    // 回溯
	for d := len(trace) - 1; d >= 0; d-- {
		v := trace[d] // 获取前一轮的v
		k := x - y // 当前k

		var prevk int
		// 计算前驱结点的k值
		if k == -d || (k != d && v[max+k-1] < v[max+k+1]) {
			prevk = k + 1
		} else {
			prevk = k - 1
		}
		// 从历史状态获取x值并计算y值
		prevx := v[max+prevk]
		prevy := prevx - prevk
        // 判断是否执行了mov操作
		for x > prevx && y > prevy {
			script = append(script, OpMov)
			x--
			y--
		}
		// 如果当前d>0
		if d > 0 {
            // 如果x没有变化，则说明向下走，ins操作
			if x == prevx {
				script = append(script, OpInsert)
			} else {
                // 否在就是del操作
				script = append(script, OpDel)
			}
		}
		// 更新x,y的值
		x, y = prevx, prevy
	}
	// 回溯获取到的编辑顺序是逆序的
	return script.reverse()
}

完整代码

一种diff算法：Myers

diff

Myers算法

Code

参考