可选择性地打 patch： merge 时通常会使用两个及以上的变更历史（往往是针对同一文件）进行调和来生成新的 tree (git的Bolb 和 tree 对象)，这就意味着可以有选择地对change进行应用变更，而不是直接拷整个文件。并且因为这点，很多版本系统都采用了非快照而是存 变更 地方式。
GIst
阐述该算法使用的基本模型，并实现一个简单的版本转换样例
Example
现假设存在两个串(git 以行为单位，这里串的每个字符代表一行)
1 2
a = ABCABBA b = CBABAC
最蠢的全量插删法这里就不提了。
这里先罗列几种将 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
blog 的作者这里没具体说三种方案是啥，但是看用例大致是以下三种：
a 与 b 比较，遇到不同的先删除，遇到相同则开始同步，最后将剩余的补足。
a 与 b 比较，遇到不同的先删除，若删除后的前缀能满足匹配则过渡，否则插入目标字符。
与 2 相同，但是是先插后删。
上面三种方案都是只活动了 5 个单位就将 a 转换成了 b，这三种方案里应该有一种是你的 diff preference 方案。
综上来看一个好的 diff 算法至少包含两个特性： a. 它仅仅需要活动最少的单元来完成变更 b. 它应该有 good taste
先来举两个例子表现下
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
水平轴就不用说了，就是树的深度，而纵轴其实就是 (x - y) 的值，这里方便后面说明取横轴为 d 轴，纵轴为 k 轴，注意的是 k 的取值范围取决于d，为 (-d, d), 且每次 k 的移动都是 2 步, 比如 (d, k) = (2, 0) -> (2, 2), k 的取值范围为 -2 … 2。
可见当 x 增长时， k + 1, y 轴增长 k - 1, 而斜轴使得 x , y 各增一步，所以 k 不变，换句话说 k 的增减 1 其实就是一次横纵移动。对这个图来说，需要 recording 的是记录不同的 k 值对应单次步进的最远距离。
d 代表步数，可以到达点 (i，j), 如果期间经过了对角线， i, j 必定同时加 1 由上可得 d 可到达的步数为 (i + diagonal, j + diagonal), 其中diagonal 为经过对角线的次数 那么k = x - y = i - j 的奇偶性就依赖于 d 当 d 为奇数， i + j 就是奇数，自然 i-j 就是奇数 => d 奇 k 奇, d 偶 k 偶
k 这里有个重点意识：任何抵达 k 线的点 必经过了至少 |k| 个 增或者删操作
Algorithm proceeds
目标是为了通过前一个节点的最佳移动来确认下一个 (d, k) 的最佳位置。最佳移动的特性很简单，就是有 highest x 的步进（而不是 y， 因为前面提过想先删后增）。
换句话说就是决策 从(d - 1, k - 1) 进行y++【会使 k - 1 + 1】, 或者从(d - 1, k + 1) x++【会使 k + 1 - 1】。
最后一个简化手段就是 dth 的 x 值只依赖于第 (d-1)th 的取值。 and because each round alternately modifies either the odd or the even k positions, each round does not modify the values it depends on from the previous round. 因为 x 可以存在以 k 为下标的一个扁平数组中. 在这个例子中，x 将随着 d 做出以下的演变：
现在开始进行代码实现：首先创建一个方法，方法包含了两个list，也就是前面说的 a 和 b， 他们都各自包含了Diff::Line 对象集。
1 2 3 4 5 6 7 8
moduleDiff Line = Struct.new(:number, :text)
def self.lines(document) document = document.lines if document.is_a?(String) document.map.with_index { |text, i| Line.new(i + 1, text) } end end
然后写个工具方法，用来对 串的每个字符转换成行后的对象 进行diff
1 2 3 4 5
moduleDiff def self.diff(a, b, differ: Myers) differ.diff(lines(a), lines(b)) end end
上述的准备工作中保存了看似无用的行号，其实是为了方便打印之类的后续操作。
现在开始实现 Myers Class, 首先给a b 打个样，把他们绑在 myers instance 上进行初始化，然后实现 diff
1 2 3 4 5 6 7 8 9 10 11 12 13
classMyers def self.diff(a, b) new(a, b).diff end
definitialize(a, b) @a, @b = a, b end
defdiff # TODO end end
标注下 a，b 串的长度和最长移动步数【ab的长度和】
1 2 3
defshortest_edit n, m = @a.size, @b.size max = n + m
然后安排一个这样的数组用来存对应不同 k 的最新 x 值，其中 k可以取值 (-max, max), 按理说用双向链表好一点，这里为了方便，把数组开大点就行。
1 2
v = Array.new(2 * max + 1) v[1] = 0
然后创建一个双重循环，外循环用来遍历 d 0...max 1step, 内循环用来遍历 k -d...d 2step，然后根据 k 决定是 x 的值。如果 k == -d || (k != d && v(k -1) < v(k-1))，那么我们向下移动，即 y++ ，将x不变视为等于上一轮的k + 1的值。否则，我们将向右移动，并将x 在 last `k 的基础上加 1。
1 2 3 4 5 6 7 8 9
(0 .. max).step do|d| (-d .. d).step(2) do|k| if k == -d or (k != d and v[k - 1] < v[k + 1]) x = v[k + 1] else x = v[k - 1] + 1 end
y = x - k
然后是斜线移动，只要 a b 的x y位置对应字母相同，那么就可以同时增长 x y持续到发生变更为止，并将停留点作为新的x。
1 2 3 4 5
while x < n and y < m and@a[x].text == @b[y].text x, y = x + 1, y + 1 end
/** * complexity of both time and space : O ((N + M)D) * k = x - y * 0 - 1 - 2 - 3 // x * | * 1 * | * 2 // y */ @Override public List<LineObject> diff(List<LineObject> fromLineObjects, List<LineObject> targetLineObjects){
// init step int finalStep = 0; // we set from as x anxious finalint fromLineCount = fromLineObjects.size();
// we set target as y anxious finalint targetLineCount = targetLineObjects.size();
// sum of from and target lines count finalint totalLineCount = targetLineCount + fromLineCount;
int vSize = Math.max(fromLineCount, targetLineCount) * 2 + 1;
// do snapshot for v while iterate step int [][] vList = newint[totalLineCount + 1][vSize];
// k can be zero, so plus one //todo optimize for minimize v.length finalint[] v = newint[vSize];
// set the previous start point v[v.length / 2 + 1] = 0;
// little trick, java can not use negative number as array index int negativeStep = v.length / 2 - step; int positiveStep = v.length / 2 + step; for (int k = negativeStep; k >= 0 && k <= positiveStep; k += 2) { int kAimD = k - v.length / 2; boolean down = (kAimD == -step || (kAimD != step && v[k - 1] < v[k + 1]));
int xStart = down? v[k + 1]: v[k - 1];
int xEnd = down? xStart: xStart + 1; int yEnd = xEnd - kAimD; // diagonal while ((0 <= xEnd && xEnd < fromLineCount) && (0 <= yEnd && yEnd < targetLineCount) && (fromLineObjects.get(xEnd).getLineContent().equals(targetLineObjects.get(yEnd).getLineContent()))){ xEnd++; yEnd++; } v[k] = xEnd; if (xEnd >= fromLineCount && yEnd >= targetLineCount) { foundShortest = true; } } // do snapshot for v vList[step] = Arrays.copyOf(v, v.length); if (foundShortest) { finalStep = step; break; } } List<LineObject> result = new ArrayList<>();
if (foundShortest) { Stack<Snake> snakeStack = generateSnakes(fromLineCount, targetLineCount, vList, finalStep);
// the final step, let's rock SnakePoint realStartPoint = new SnakePoint(0, 0); while(!snakeStack.empty()) { final Snake snake = snakeStack.pop(); final SnakePoint start = snake.getStart(); final SnakePoint middle = snake.getMiddle(); final SnakePoint end = snake.getEnd();
/** * let's do backtrack to generate the shortest path * now vList has total record we need: every step the (k, x) val * * start(K-1) -- mid(K) * \ * \ * end * * */ privatestatic Stack<Snake> generateSnakes(int fromLineCount, int targetLineCount, int[][] vList, int finalStep){
Stack<Snake> snakeStack = new Stack<>(); int fromEndX = fromLineCount; int targetEndY = targetLineCount; // step >= 0 or (fromEndX > 0 && targetEndY> 0) for (int step = finalStep; fromEndX > 0 && targetEndY > 0; step--) { finalint[] v = vList[step];
int negativeStep = v.length / 2 - step; int positiveStep = v.length / 2 + step;
int k = fromEndX - targetEndY; int kIndex = v.length / 2 + k;
// set current k as end point int xEnd = v[kIndex]; int yEnd = xEnd - k;
List<LineObject> result = new ArrayList<>(); // mid to end if (!from.getX().equals(end.getX()) && !from.getY().equals(end.getY())) { for (int fromX = from.getX(); fromX < end.getX(); fromX++) { final LineObject lineObject = fromLineObjects.get(fromX); lineObject.setAction(ConstantVal.SYNC); result.add(lineObject); } } else { // start to mid if (!from.getX().equals(end.getX())) { final LineObject lineObject = fromLineObjects.get(from.getX()); lineObject.setAction(ConstantVal.MINUS); result.add(lineObject); } elseif (!from.getY().equals(end.getY())) { final LineObject lineObject = targetLineObjects.get(from.getY()); lineObject.setAction(ConstantVal.PLUS); result.add(lineObject); } } return result; }
/** * test method */ publicstaticvoidmain(String[] args){ String a = "A-B-C-A-B-B-A"; String b = "C-B-A-B-A-C";
final String[] aArray = a.split("-"); final String[] bArray = b.split("-"); List<LineObject> fromLineObjects = new ArrayList<>(); List<LineObject> targetLineObjects = new ArrayList<>(); for (int i = 0; i < aArray.length; i++) { int index = i + 1; final LineObject lineObject = new LineObject(); lineObject.setIndex(index); lineObject.setLineContent(aArray[i]); fromLineObjects.add(lineObject); } for (int i = 0; i < bArray.length; i++) { int index = i + 1; final LineObject lineObject = new LineObject(); lineObject.setIndex(index); lineObject.setLineContent(bArray[i]); targetLineObjects.add(lineObject); } final List<LineObject> diff = new MyersDiff().diff(fromLineObjects, targetLineObjects); diff.forEach(line -> log.debug(line.toString())); }
