diff算法用于比较文本间的差异，通常用于版本控制系统，例如 git( $git diff)。
什么是diff diff算法的目的是计算出文本间的差异，那么首先介绍下什么是文本差异。文本差异就是目标文本和源文本之间的区别，也就是将源文本变成目标文本所需要的操作。这里的操作包括插入(insert)和 删除(delete)。
假设我们要计算下面两个字符串之间的差异：
一种可能的结果是删除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种差异都是拥有最小更改数量的方案。但是第二种和第三种没有第一种看起来“直观”。“直观”有两个特点。
删除后新增，比新增后删除要好。例如上面的例子 2 比例子 3 看起来要直观 当修改一块代码时，整块的删除然后新增，比删除新增交叉在一起要好，例如: 1 2 3 4 5 6 Good: - one Bad: - one - two + four - three - two + four + five + five + six + six - three
新增或删除的内容应该和代码结构相呼应，例如下面的例子，左边我们可以很直观地看出新增了一个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= 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))，对应于从两个字符串中使用一个相等的字符，既不删除也不插入任何东西。 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,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
因为k=x−y，所以我们不需要存储y值，因为它可以从k和x的值中计算出来。 我们不需要存储每一步移动的方向，只需要存储在每个点上我们能达到的最佳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(); int MAX = N + M; int size = 1 + 2 * MAX; int middle = size / 2 ; int [] V = new int [size]; int [][] trace = new int [MAX + 1 ][size]; V[middle] = 0 ; int x, y; for (int D = 0 ; D <= MAX; D++) { for (int k = D; k >= -D; k -= 2 ) { 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 ; } 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; } }
参考