diff算法-Myers算法

Diff算法-Myers算法

diff算法用于比较文本间的差异,通常用于版本控制系统,例如 git( $git diff)。

什么是diff

diff算法的目的是计算出文本间的差异,那么首先介绍下什么是文本差异。文本差异就是目标文本和源文本之间的区别,也就是将源文本变成目标文本所需要的操作。这里的操作包括插入(insert)和 删除(delete)。

假设我们要计算下面两个字符串之间的差异:

  • a: ABCABBA
  • b: CBABAC

一种可能的结果是删除a中的全部字符,然后再插入b中的全部字符。

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

上面的差异是有效的,但是并不是较好的差异。差异中的更改数量应该尽可能少。例如:

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

上面的3种差异都是拥有最小更改数量的方案。但是第二种和第三种没有第一种看起来“直观”。“直观”有两个特点。

  1. 删除后新增,比新增后删除要好。例如上面的例子 2 比例子 3 看起来要直观
  2. 当修改一块代码时,整块的删除然后新增,比删除新增交叉在一起要好,例如:
1
2
3
4
5
6
Good: - one            Bad: - one
- two + four
- three - two
+ four + five
+ five + six
+ six - three
  1. 新增或删除的内容应该和代码结构相呼应,例如下面的例子,左边我们可以很直观地看出新增了一个inspect 方法。
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

diff算法-Myers

综上,diff算法的目的就是:寻找最短的直观的 diff(最短编辑距离)。Myers 算法将寻找最短编辑距离建模为图搜索。

对于a= ABCABBAb=CBABAC可以构建如下的图形(横轴是 a的内容,纵轴是b的内容)。

网格中的(x,y) 坐标对应于编辑过程中的步骤:

  • 在(0,0)我们有字符串a,因为尚未开始编辑。
  • 向右移动(增加x)对应于从a中删除一个字符,例如移动到(1,0)意味着从a中删除第一个A。
  • 向下移动(增加y)对应于从b插入一个字符,例如从(1,0)移动到(1,1),意味着插入b中的第一个C。
  • 右下角的位置(7,6)对应于将字符串a完全转换为字符串b。
  • 除了向右和向下移动,在某些位置我们也可以移动对角线。当两个字符串在某个位置的索引对应字符相同时(例如a中的第三个字符和b中的第一个字符都是C),图中会存在一条对角线((2,0)->(3,1)),对应于从两个字符串中使用一个相等的字符,既不删除也不插入任何东西。
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
       A     B     C     A     B     B     A

o-----o-----o-----o-----o-----o-----o-----o 0
| | | \ | | | | |
C | | | \ | | | | |
| | | \ | | | | |
o-----o-----o-----o-----o-----o-----o-----o 1
| | \ | | | \ | \ | |
B | | \ | | | \ | \ | |
| | \ | | | \ | \ | |
o-----o-----o-----o-----o-----o-----o-----o 2
| \ | | | \ | | | \ |
A | \ | | | \ | | | \ |
| \ | | | \ | | | \ |
o-----o-----o-----o-----o-----o-----o-----o 3
| | \ | | | \ | \ | |
B | | \ | | | \ | \ | |
| | \ | | | \ | \ | |
o-----o-----o-----o-----o-----o-----o-----o 4
| \ | | | \ | | | \ |
A | \ | | | \ | | | \ |
| \ | | | \ | | | \ |
o-----o-----o-----o-----o-----o-----o-----o 5
| | | \ | | | | |
C | | | \ | | | | |
| | | \ | | | | |
o-----o-----o-----o-----o-----o-----o-----o 6

0 1 2 3 4 5 6 7

迈尔斯算法的想法非常简单:希望从(0,0)到(7,6)的移动尽可能少。“移动”是向右移动一步(从a删除)或向下移动一步(从b插入)。从a到b最多可以移动13次:两个字符串的总长度。由于走对角线路径是免费的(因为它们对应于不改变),因此希望最大化对角线的数量,并最小化向右/向下移动的数量。

首先从初始位置(0,0)开始,从当前位置我们有两个选择:向下移动到达(0,1)或向右移动到达(1,0)。

1
2
3
4
0,0 --- 1,0
|
|
0,1

从(1,0)出发,向下可以到达(2,2)(从1,1通过对角线到达),向右可以到达(3,1); 从(0,1)出发,向右可以到达(2,2),向下可以到达(2,4)。注意,(2,2)记录为通过(1,0)而不是(0,1)访问,因为直观的路径希望是先删除再插入,所以优先记录向右分支。

1
2
3
4
5
6
7
0,0 --- 1,0 --- 3,1
| |
| |
0,1 -\- 2,2
|
|
2,4

通过广度遍历,可以找到所有的路径,并找到图中的最短路径。但是在广度遍历的过程中,会有很多分支是不必要的搜索。因此为了提高执行速度,可以进一步优化。

最短编辑距离

首先,定义参数 d 和 k,d 代表路径的长度,k 代表当前坐标 x - y 的值。最优坐标表示 d 和 k 值固定的情况下,x 值最大的坐标(x 大,表示向右走的多,优先删除)。还是以上面的图为例。我们从坐标 (0, 0) 开始,此时,d=0,k=0,然后逐步增加 d,计算每个 k 值下对应的最优坐标。每一步要么向右(x=x+1, k=k+1),要么向下(y=y + 1,k=k-1),对角线不影响路径长度

对于每个以0开头的d,我们以2为步骤填充k从−d到+d的每一次移动。我们在每个(d,k)位置的目标是确定我们可以从前一个位置做出的最佳移动。最佳移动是给我们最大x值的移动;最大化x而不是y意味着我们优先考虑删除而不是插入。为了发现最佳移动,我们需要决定是从(d−1, k+1)向下移动,还是从(d−1,k−1)向右移动。如果k是−d,那么移动必须是向下的,同样,如果k是+d,那么我们必须向右移动。对于k的所有其他值,我们从上一列中的两个相邻k值中选择x最高的位置。

当 d=1 时,k 只可能有两个取值,要么是 1,要么是 -1。

  • 当 d=1,k=1 时,最优坐标是 (1, 0)。
  • 当 d=1,k=-1 时,最优坐标是 (0, 1)。

因为 d=1 时,k 要么是 1,要么是 -1,当 d=2 时,表示在 d=1 的基础上再走一步,k 只有三个可能的取值,分别是 -2,0,2。

  • 当 d=2,k=-2 时,最优坐标是 (2, 4)。
  • 当 d=2,k=0 时,最优坐标是 (2, 2)。对于(d, k)=(2,0)处的移动。我们可以从(d,k)=(1,−1)(x,y)=(0,1)向右移动,也可以从(d,k)=(1,1)(x,y)=(1,0)向下移动,(1,0)的x值比(0,1)高,所以我们选择从(1,0)到(1,1)的向下移动,这将我们引向对角线上的(2,2)。
  • 当 d=2,k=2 时,最优坐标是 (3, 1)。

在(d, k)=(3,−1)时,可以从(x,y)=(2,2)向下移动或从(x,y)=(2,4)向右移动。向右移动会增加x,因此我们从(2,4)移动到(3,4),然后对角线移动到(4,5)。

下图横轴代表 d,纵轴代表 k。可以看到第n轮中的k值仅依赖于第(n−1)轮中的k值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    |      0     1     2     3     4     5
----+--------------------------------------
|
4 | 7,3
| /
3 | 5,2
| /
2 | 3,1 7,5
| / \ / \
1 | 1,0 5,4 7,6
| / \ \
0 | 0,0 2,2 5,5
| \ \
-1 | 0,1 4,5 5,6
| \ / \
-2 | 2,4 4,6
| \
-3 | 3,6
  1. 因为k=x−y,所以我们不需要存储y值,因为它可以从k和x的值中计算出来。
  2. 我们不需要存储每一步移动的方向,只需要存储在每个点上我们能达到的最佳x值。一旦我们知道最终位置出现在哪里,我们就可以回溯,找出我们探索过的众多路径中的哪一条会把我们带到那里。

删除这些信息会得到:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    |      0     1     2     3     4     5
----+--------------------------------------
|
4 | 7
|
3 | 5
|
2 | 3 7
|
1 | 1 5 7
|
0 | 0 2 5
|
-1 | 0 4 5
|
-2 | 2 4
|
-3 | 3

最后的简化是,第dth轮中的x值仅依赖于第(d−1)轮中的x值,并且由于每轮交替修改奇数或偶数k位置,因此每轮都不会修改它所依赖的前一轮的值,只会覆盖上上轮的值。因此,x值可以存储在一个一维数组中(而不是需要开辟二维数组记录所有历史值),由k索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
      k |   -3    -2    -1     0     1     2     3     4
--------+-----------------------------------------------
|
d = 0 | 0
|
d = 1 | 0 0 1
|
d = 2 | 2 0 2 1 3
|
d = 3 | 3 2 4 2 5 3 5
|
d = 4 | 3 4 4 5 5 7 5 7
|
d = 5 | 3 4 5 5 7 7 5 7

当我们发现我们可以在(d,k)=(5,1) 处到达(x,y)=(7,6)时,迭代就停止了。

回溯路径

通过上面的算法我们可以找到到达终点所需的最小路径。一旦我们到达终点,我们可以反向查看我们记录的数据,找出导致结果的单一路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    |      0     1     2     3     4     5
----+--------------------------------------
|
4 | 7
|
3 | 5
|
2 | 3 7
|
1 | 1 5 7
|
0 | 0 2 5
|
-1 | 0 4 5
|
-2 | 2 4
|
-3 | 3

最终位置在(x, y)=(7,6),从(d,k)=(5,1),我们可以追溯到(4,0)或(4,2):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    |      0     1     2     3     4     5
----+--------------------------------------
|
4 | 7
|
3 | 5
|
2 | 3 ( 7 )
|
1 | 1 5 [ 7 ]
|
0 | 0 2 ( 5 )
|
-1 | 0 4 5
|
-2 | 2 4
|
-3 | 3

看到(4,2)包含较高的x值,因此我们必须通过从那里向下移动到达(5,1)。这说明(7,6)之前的(x, y)位置是(7,5)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    |      0     1     2     3     4     5
----+--------------------------------------
|
4 | 7
|
3 | 5
|
2 | 3 7
| \
1 | 1 5 7
|
0 | 0 2 5
|
-1 | 0 4 5
|
-2 | 2 4
|
-3 | 3

实现

代码实现见MyersDiff.java

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public class MyersDiff {
private final Text textA;
private final Text textB;

public MyersDiff(Text textA, Text textB) {
this.textA = textA;
this.textB = textB;
}
/**
* 寻找最短编辑距离
*/
public EditScript getEditScript() {
// 获取两个文本的行数
int N = textA.size();
int M = textB.size();
// 最大编辑距离就是先删除A,再插入B
int MAX = N + M;
// K的最大取值范围范围
int size = 1 + 2 * MAX;
// 数组中间点
int middle = size / 2;
int[] V = new int[size];
// 记录V的快照,用于恢复路径
int[][] trace = new int[MAX + 1][size];
// 初始值为0
V[middle] = 0;
int x, y;
for (int D = 0; D <= MAX; D++) {
for (int k = D; k >= -D; k -= 2) {
// k 每轮都是修改奇数或偶数

// 如果K是左边界,x值为上一轮编辑距离的值,因为选择向下移动
// 如果K是右边界,x值为上一轮编辑距离的值+1,因为选择向右移动
// 否则,如果左边的值小于右边的值,选择向下移动,否则选择向右移动。
if (k == -D || (k != D && V[middle + k - 1] < V[middle + k + 1])) {
x = V[middle + k + 1];
} else {
x = V[middle + k - 1] + 1;
}
y = x - k;
while (x < N && y < M && textA.getLine(x).equals(textB.getLine(y))) {
// 对角线移动
x++;
y++;
}
V[middle + k] = x;
if (x >= N && y >= M) {
trace[D] = V.clone();
return backtrack(D, middle,trace);
}
}
trace[D] = V.clone();
}
return null;
}

/**
* 回溯路径,构建编辑脚本
*
* @param D 最大编辑距离
* @param trace 中间数组
* @param middle 初始点
* @return
*/
private EditScript backtrack(int D, int middle,int[][] trace) {
int N = textA.size();
int M = textB.size();
// 终点
int x = N;
int y = M;
int prev_x = x;
int prev_y = y;
EditScript script = new EditScript(textA,textB);
for (int d = D; d > 0; d--) {
int[] v = trace[d];
int k = x - y;
Operation operation = null;
// 恢复选择路径
if (k == -d || (k != d && v[middle + k - 1] < v[middle + k + 1])) {
// 向下移动
prev_x = v[middle + k + 1];
prev_y = prev_x - (k + 1);
operation = Operation.INSERT;
} else {
// 向右移动
prev_x = v[middle + k - 1];
prev_y = prev_x - (k - 1);
operation = Operation.DELETE;
}
while (x > prev_x && y > prev_y){
// 对角线移动
x = x-1;
y = y-1;
script.appendEqual(x,y);
}
if(operation == Operation.INSERT){
script.appendInsert(prev_x,prev_y);
}else {
script.appendDelete(prev_x,prev_y);
}
x= prev_x;
y= prev_y;
}
if(x !=0){
while (x > 0 && y> 0){
x = x-1;
y = y-1;
script.appendEqual(x,y);
}
}
return script;
}
}

参考