diff算法-Myers算法
diff算法用于比较文本间的差异，通常用于版本控制系统，例如 git( $git diff)。
什么是diff
diff算法的目的是计算出文本间的差异，那么首先介绍下什么是文本差异。文本差异就是目标文本和源文本之间的区别，也就是将源文本变成目标文本所需要的操作。这里的操作包括插入(insert)和 删除(delete)。
假设我们要计算下面两个字符串之间的差异：
- a:
ABCABBA - b:
CBABAC
一种可能的结果是删除a中的全部字符，然后再插入b中的全部字符。
- A
- B
- C
- A
- B
- B
- A
+ C
+ B
+ A
+ B
+ A
+ C
上面的差异是有效的，但是并不是较好的差异。差异中的更改数量应该尽可能少。例如:
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种差异都是拥有最小更改数量的方案。但是第二种和第三种没有第一种看起来“直观”。“直观”有两个特点。
- 删除后新增，比新增后删除要好。例如上面的例子 2 比例子 3 看起来要直观
- 当修改一块代码时，整块的删除然后新增，比删除新增交叉在一起要好，例如:
Good: - one Bad: - one
- two + four
- three - two
+ four + five
+ five + six
+ six - three
- 新增或删除的内容应该和代码结构相呼应，例如下面的例子，左边我们可以很直观地看出新增了一个inspect 方法。
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= ABCABBA和b=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))，对应于从两个字符串中使用一个相等的字符，既不删除也不插入任何东西。
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）。
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）访问，因为直观的路径希望是先删除再插入，所以优先记录向右分支。
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值。
| 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
- 因为k=x−y，所以我们不需要存储y值，因为它可以从k和x的值中计算出来。
- 我们不需要存储每一步移动的方向，只需要存储在每个点上我们能达到的最佳x值。一旦我们知道最终位置出现在哪里，我们就可以回溯，找出我们探索过的众多路径中的哪一条会把我们带到那里。
删除这些信息会得到:
| 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索引。
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)时，迭代就停止了。
回溯路径
通过上面的算法我们可以找到到达终点所需的最小路径。一旦我们到达终点，我们可以反向查看我们记录的数据，找出导致结果的单一路径。
| 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）:
| 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）。
| 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
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;
}
}参考
相关内容
如果你觉得这篇文章对你有所帮助，请我一杯咖啡吧~
微信支付
支付宝