一种diff算法:Myers

diff

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

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

我们首先来看一个例子:

  • a = ABCABBA
  • b = CBABAC

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
- A
- B
- C
- A
- B
- B
- A
+ C
+ B
+ A
+ B
+ A
+ C

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

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

1
2
3
4
5
6
7
8
9
- A
- B
C
+ B
A
B
- B
A
+ C

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

1
2
3
4
5
6
7
8
9
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种更加直观

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

1
2
3
4
5
6
Good:   - one         Bad:    - one
- two + four
- three - two
+ four + five
+ five + six
+ six - three

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

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

1
2
3
4
5
6
7
8
9
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+6delins操作,也就是执行全删全增操作。

myers算法的思想很简单,就是要找出一条从(0,0)(7,6)的路径,让这条路径中的delins操作尽量的少,这就要求要尽量执行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值可以达到的最远记录,只需要记录当前给定dk时,对应的x就行了,因为y = x - k

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

  1. 我们首先从0(len(a)+len(b))遍历d
  2. 每次迭代b时,我们以步长为2-dd遍历k;这里为什么步长是2呢?仔细观察上图,当前d的节点都是从d-1的节点扩展而来,d-1的节点要么向右走,k1,要么向下走,k1,这时候同一个d的相邻的两个k之间差值就是2
  3. 对于给定的dk值,我们根据上一轮遍历的结果,决定当前的最佳位置,这里的最佳位置意味着取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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
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()
}

完整代码

参考