Git Myers diff 笔记 参考文章链接：
Myers diff paper
Myers diff algorithm blog
Diff Usage：
尚未提交时可以检查 单个commit 节点的变更
merge 前比较两个分支的不同
可选择性地打 patch： merge 时通常会使用两个及以上的变更历史（往往是针对同一文件）进行调和来生成新的 tree (git的Bolb 和 tree 对象)，这就意味着可以有选择地对change进行应用变更，而不是直接拷整个文件。并且因为这点，很多版本系统都采用了非快照而是存 变更 地方式。
GIst 阐述该算法使用的基本模型，并实现一个简单的版本转换样例
Example 现假设存在两个串(git 以行为单位，这里串的每个字符代表一行)
最蠢的全量插删法这里就不提了。
这里先罗列几种将 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
正常人一般喜欢第一种吧，因为这种合乎人类直觉，符合代码结构，比较清纯。 [在下不喜欢第一种，在下就喜欢骚的]
如果喜欢第一种的话那么 Myers diff 就很适合你，因为它采用的是贪心的策略，也就是先吃掉尽可能多的行然后才会 make changes, 这样的话就不会出现第二种 bad end.
Build Graph Myers paper 核心 idea 就是旨在找出 shortest edit script (SES)， 也就是最短活动单元，然后在此之上构建图搜。
现在来构建一种图来阐述这个变换关系：
存在一个这样的坐标系，它的 x 轴分布对应 a 串， y 轴分布对应 b 串， x 的 increase 代表对 a 的删除， y 的 increase 代表对 b 的插入。
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 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
【方便观看再列一下】
注意这里的删除是指在A的位置上删除，而插入是指在B的位置上插入，理解这个位置很关键
如上图所示，来举例说明下就是：开始时都是在(0, 0), 现在移动到(1, 0), 那么代表 a 删除了第一个字符，串就变成了 BCABBA, 然后 (1,0) 移动到 (1, 1)，串就变成了 CBCABBA, 就这样推进下去不断地使 a 的前缀逼近 b 的前缀，最终会在 (7, 6) 得到需要的串。
此外除了横向纵向的移动外还有图中的斜线移动，比如(2, 0) CABBA 【第一个 C 是 a串的】 到 (3, 1) CABBA 【第一个 C 是 b 串的】，这种情况下就可以走斜线，因为二者是等价的【即相当于从两个串中消耗等同的字符，既不插入也不删除】
Myers algorithm 的算法就是找到上述的这种路径中移动次数最少的那一条。【这里的移动指的是一次单独的删a或者一次单独的添加b】。最多的移动数是 7 + 6 = 13, 也就是俩串的长度和，也就是最蠢的全量增删。
上述在找最小的移动数的过程中要注意的是 斜向的移动 是白嫖的，因为它不进行变动花费(即不增加也不删除),所以找的过程中就是这么个原则：在你最终地移动数中应该尽可能多地包含 斜线向 而尽可能少地包含 横纵 向。上面也提到过了，其实最小的移动数就是 5，Myers 的目的就是要找到这个最短路。
Try 如图，二选一。
先假设选 (0, 1), 那么从 (0, 0) 到 (2, 4) 就相当于只移动了两次 [(0, 1)-> (0, 2) |-> (1, 3) |-> (2, 4)] ，因为斜线没有消耗。同样的到 (2, 2) 也只要两步。记录下这些移动路径和花费。
然后开始考虑 (1, 0) 的方案，同上，同样记录下从该点出发一次移动最多能移动多远。
上面两种方案中 到 (2, 2) 点的经历花费是一样的，但是更倾向选择 (1, 0)而非 (0, 1), 因为我们采取的方案更倾向于 先删后插(即先增x后增y)【更符合直觉】 而非先插后删。
上面的记录了出行两步能达到的节点，大致反馈图如下
1 2 3 4 5 6 7 0,0 --- 1,0 --- 3,1 | | | | 0,1 2,2 | | 2,4
对上述的(2, 4), (2, 2), (3, 1) 重复前面的步骤【即移动一步后最终可达多远】，得到反馈图如下
1 2 3 4 5 6 7 8 9 10 0,0 --- 1,0 --- 3,1 | | | | 0,1 2,2 --- 5,4 | \ | \ 2,4 - 2,3 | \ | 4,5 3,6
如果是常见的图搜，那么上面的 (2, 4) 右移 和 (2, 2) 的下移都是要记录移动结果【也就是 (4, 5), (2, 3) 都要记录】，但 (2, 3) 实际上可以抛弃，因为这俩都是经历了一次对 a 删除 和 两次对 b 插入，但是明显 (4, 5) 的结果更优【in any order】，因而抛弃掉 (2, 3) 的路径。【因为这个图模型的结构代表着仅存储经过 一组特定编辑 即可 达到 的 最佳位置 就足够了】继续跟进反馈如下
1 2 3 4 5 6 7 8 9 10 0,0 --- 1,0 --- 3,1 | | | | 0,1 2,2 --- 5,4 | | 2,4 --- 4,5 | | 3,6
同样的从 (3, 1) 出发可以过(3, 2) 到(5, 4)，因而舍弃 [(2, 2) -> (3,2) |-> (5, 4)]【因为倾向 先删后插】
1 2 3 4 5 6 7 8 9 10 0,0 --- 1,0 --- 3,1 --- 5,2 | | | | | | 0,1 2,2 5,4 | | 2,4 --- 4,5 | | 3,6
从上图开始加速，经过前面的整理我们可以得到这样的路线：
(3, 6) -> (4, 6) || (4, 5) -> (4, 6) => (4, 5) -> (4, 6)
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 0,0 --- 1,0 --- 3,1 --- 5,2 | | | | | | 0,1 2,2 5,4 | | 2,4 --- 4,5 --- 5,5 | | | | 3,6 4,6 0,0 --- 1,0 --- 3,1 --- 5,2 | | | | | | 0,1 2,2 5,4 --- 7,5 | | | | 2,4 --- 4,5 5,5 | | | | 3,6 4,6 0,0 --- 1,0 --- 3,1 --- 5,2 --- 7,3 | | | | | | 0,1 2,2 5,4 --- 7,5 | | | | 2,4 --- 4,5 5,5 | | | | 3,6 4,6
经过如上步骤来到了第 5 步，因为已经知道了最少就是 5 步，所以这一次步进目的就是要找到 (7， 6)
(4, 6) -> (5, 6) || (5, 5) -> (5, 6) => (5, 5) -> (5, 6)
(7, 5) -> (7, 6)
1 2 3 4 5 6 7 8 9 10 0,0 --- 1,0 --- 3,1 --- 5,2 --- 7,3 | | | | | | 0,1 2,2 5,4 --- 7,5 | | | | | | 2,4 --- 4,5 5,5 7,6 | | | | | | 3,6 4,6 5,6
Basic Summary 由上可得算法的基本 idea：给定两个字符串，找到代表这两个之间的图模型的最短路径。【其实就是广度优先的图搜最短路】
Implementation 将上述得到的图旋转 45 degrees 得到如下图：
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 | / 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
水平轴就不用说了，就是树的深度，而纵轴其实就是 (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
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】。
1 2 3 4 5 6 7 8 | 0 1 2 ----+---------------------- | 1 | 1,0 | / \ 0 | 0,0 ( 2,2 ) | \ -1 | 0,1
以上述为例，(d, k) = (1, 0) or (0, 1) => (2, 2) ，但是选 (1, 0) 【因为 highest x】, 所以我们采用了上图的路径。
也有时候两个 previous position 有着相同的 x， 这个时候就采用下一步移动【highest x】 的。比如 (x, y) = [(2, 2) -> (2, 3) || (2, 4) -> (2, 3) ] =|> (4， 5)
1 2 3 4 5 6 7 8 9 10 11 12 | 0 1 2 3 ----+---------------------------- | 2 | 3,1 | / 1 | 1,0 | / \ 0 | 0,0 2,2 | \ -1 | 0,1 ( 4,5 ) | \ / -2 | 2,4
tips: 这里说几个算法中用到的简化手段：1是存储 k 索引对应的 (x, y) 时可以不保存 y，因为y 可以用 x-k 算出. 2是不需要存储每次移动的方向，只需要存 best x 的值即可。 此过程结束后可找到最小的通往 (7,6) 的 depth, 并且通过回溯说明这条路径。
经过上述的信息简化如下【移除了 y 和 路径方向】
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)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 做出以下的演变：
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), 迭代结束。
Show me code 现在开始进行代码实现：首先创建一个方法，方法包含了两个list，也就是前面说的 a 和 b， 他们都各自包含了Diff::Line 对象集。
1 2 3 4 5 6 7 8 module Diff 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 module Diff 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 class Myers def self .diff(a, b) new(a, b).diff end def initialize (a, b) @a , @b = a, b end def diff end end
标注下 a，b 串的长度和最长移动步数【ab的长度和】
1 2 3 def shortest_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 v[k] = x
在上面的基础上，如果最终到达 (7. 6) 则停止
1 2 3 4 return d if x >= n and y >= m end end end
上面算出来了最小的移动数但是没有记录移动路径也就是实际的变更记录。
Record Path 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 def shortest_edit n, m = @a .size, @b .size max = n + m v = Array.new(2 * max + 1 ) v[1 ] = 0 (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 while x < n and y < m and @a [x].text == @b [y].text x, y = x + 1 , y + 1 end v[k] = x return d if x >= n and y >= m end end end
由上面得到最小的编辑数，在这之后需要做的就是回溯来找出最短路。
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)，所以我们可以track back 到 (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
可以看到 (d, k) = (4, 2), 有着更高的 x = 7, 也就是说 (7, 5) -> (7, 6). 同样的 (d, k) = (3, 1) or (3, 3) 后者的x并不大于 前者，因此取 (3, 1)， 也就是 (x, y) = (5, 4) -> (7, 5).
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) 路径为 (0,0) -> (1,0) -> (3,1) -> (5,4) -> (7,5) -> (7,6)。 这几个点上也很好推算斜线移动，只要同时对 x–, y– 然后到一方值达到相同后，就可以知道移动的上一步是啥了。
之前只保存了 x 的最新值是不够的，这里需要微调下，我们创建一个数组 trace 用来在每次 d 增时保存 v 的快照，并最终返回这个数组。这也对应在上述的图中其实每轮 d 变就是一列 v copy。
1 2 3 4 5 6 7 8 9 10 11 v = Array.new(2 * max + 1 ) v[1 ] = 0 trace = [] (0 .. max).step do |d| trace << v.clone (-d .. d).step(2 ) do |k| return trace if x >= n and y >= m
这样 trace 就可以保存足够的信息用来按照前面所提到推演方式来推演实际的最佳路径【也就是对于每个 (d, k) 最佳的x】。
这样就可以构建一个方法，接受 shortest_edit function 和 最终点(x, y) 这俩参数，然后在每次移动前后把 (x, y) yield 出去。
1 2 3 4 def backtrack x, y = @a .size, @b .size shortest_edit.each_with_index.reverse_each do |v, d|
上面的 each_with_index 用来为 v 配上索引号(也就是d的值)，而reverse_each 就是反向遍历。在遍历时采用和 shortest_edit 一样的逻辑来整活，计算出 k的值，并推算出前一个 k的值, 进而通过 prev_k 找回对应的 prev_x 并算出 prev_y 的值.
1 2 3 4 5 6 7 8 9 10 11 k = x - y if k == -d or (k != d and v[k - 1 ] < v[k + 1 ]) prev_k = k + 1 else prev_k = k - 1 end prev_x = v[prev_k] prev_y = prev_x - prev_k
如果说当前的 prev_x 和 prev_y 同时小于 x， y，那么必然走过了斜线。因此开始除斜线，并把去除过程中每个经过的 x， y yield 出去。
1 2 3 4 while x > prev_x and y > prev_y yield x - 1 , y - 1 , x, y x, y = x - 1 , y - 1 end
斜线除掉后的回退应该是一次单独的 x 或 y 增步进。但是考虑到边界值即 d 为0的时候，没有可以回退的 x， y，因此continue 掉。最后把获取到的prev值赋值给当前 x,y 然后开始新一层的循环，最终得到如下结果
1 2 3 4 5 6 7 8 9 (7, 5) -> (7, 6) (6, 4) -> (7, 5) (5, 4) -> (6, 4) (4, 3) -> (5, 4) (3, 2) -> (4, 3) (3, 1) -> (3, 2) (2, 0) -> (3, 1) (1, 0) -> (2, 0) (0, 0) -> (1, 0)
到这一步就可以把前面的都粘合起来了，我们将提供一个这样的方法：这个方法接两个文本并把它们转换成两个 list<line> 后传给 shortest_edit 以此来通过 backtrack 来生成一系列 删除，增加，不变的 diff.
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 def diff diff = [] backtrack do |prev_x, prev_y, x, y| a_line, b_line = @a [prev_x], @b [prev_y] if x == prev_x diff.unshift(Diff::Edit.new(:ins , nil , b_line)) elsif y == prev_y diff.unshift(Diff::Edit.new(:del , a_line, nil )) else diff.unshift(Diff::Edit.new(:eql , a_line, b_line)) end end `` ` 上述方法首先提供了一个 diff 数组用来在每次yield 时保存 diff line。如果 x 在两次变更中相等，那么就意味着是一次 y 增，也就是 b插入，同理 y同 x增 即 a删除，除此之外都是同行。这里也把 Diff.edit 简单说明下，就是一个简单的输出模块，方便日志审查。 ` `` rubymodule Diff Edit = Struct.new(:type , :old_line , :new_line ) do def old_number old_line ? old_line.number.to_s : "" end def new_number new_line ? new_line.number.to_s : "" end def text (old_line || new_line).text end end end
然后我们就可以用 Diff::Edit objects 做一些实际的应用，比如terminal 上打红绿。
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 module Diff class Printer TAGS = {eql: " " , del: "-" , ins: "+" } COLORS = { del: "\e[31m" , ins: "\e[32m" , default: "\e[39m" } LINE_WIDTH = 4 def initialize (output: $stdout ) @output = output @colors = output.isatty ? COLORS : {} end def print (diff) diff.each { |edit| print_edit(edit) } end def print_edit (edit) col = @colors .fetch(edit.type, "" ) reset = @colors .fetch(:default , "" ) tag = TAGS[edit.type] old_line = edit.old_number.rjust(LINE_WIDTH, " " ) new_line = edit.new_number.rjust(LINE_WIDTH, " " ) text = edit.text.rstrip @output .puts "#{col} #{tag} #{old_line} #{new_line} #{text} #{reset} " end end end
大致会得到这样的回显：(+ 是绿色行， -是红色行，其他是白行)
1 2 3 4 5 6 7 8 9 - 1 A - 2 B 3 1 C + 2 B 4 3 A 5 4 B - 6 B 7 5 A + 6 C
到此一个简易的diff 就已经实现了，Blog 的作者提议是可以对此做进一步的改进，例如只显示已更改的区域，在它们周围保留一定数量的不变上下文，像git diff一样格式化它们之类的。
此外尽管git diff并未显示每行的数字，但它确实在每个change节之前包含一个标头，其中包含该节的偏移量，并且需要行号来计算该行。 这意味着行号其实非常重要，通过这个行号求出的偏移量可以帮助git apply找到正确的位置来应用每个更改，这也意味着这个行号在git merge算法中有着很重要的作用。
作者用 ruby 写的，这里自己用 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 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 package club.qqtim.diff.algorithm;import club.qqtim.common.ConstantVal;import club.qqtim.diff.LineObject;import lombok.extern.slf4j.Slf4j;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;import java.util.Stack;@Slf4j public class MyersDiff implements DiffAlgorithm { @Override public List<LineObject> diff (List<LineObject> fromLineObjects, List<LineObject> targetLineObjects) { int finalStep = 0 ; final int fromLineCount = fromLineObjects.size(); final int targetLineCount = targetLineObjects.size(); final int totalLineCount = targetLineCount + fromLineCount; int vSize = Math.max(fromLineCount, targetLineCount) * 2 + 1 ; int [][] vList = new int [totalLineCount + 1 ][vSize]; final int [] v = new int [vSize]; v[v.length / 2 + 1 ] = 0 ; boolean foundShortest = false ; for (int step = 0 ; step <= totalLineCount; step++) { 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; 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 ; } } 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); 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(); result.addAll(compareSnakePoint(realStartPoint, start, fromLineObjects, targetLineObjects)); result.addAll(compareSnakePoint(start, middle, fromLineObjects, targetLineObjects)); result.addAll(compareSnakePoint(middle, end, fromLineObjects, targetLineObjects)); realStartPoint = end; } return result; } fromLineObjects.forEach(line -> line.setAction(ConstantVal.MINUS)); targetLineObjects.forEach(line -> line.setAction(ConstantVal.PLUS)); result.addAll(fromLineObjects); result.addAll(targetLineObjects); return result; } private static Stack<Snake> generateSnakes (int fromLineCount, int targetLineCount, int [][] vList, int finalStep) { Stack<Snake> snakeStack = new Stack <>(); int fromEndX = fromLineCount; int targetEndY = targetLineCount; for (int step = finalStep; fromEndX > 0 && targetEndY > 0 ; step--) { final int [] 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; int xEnd = v[kIndex]; int yEnd = xEnd - k; boolean down = (k == negativeStep || (k != positiveStep && v[kIndex - 1 ] < v[kIndex + 1 ])); int xStart = v[down? kIndex + 1 : kIndex - 1 ]; int yStart = xStart - (down? k + 1 : k -1 ); int xMid = down? xStart: xStart + 1 ; int yMid = xMid - k; final Snake snake = new Snake (); snake.setStart(new SnakePoint (xStart, yStart)); snake.setMiddle(new SnakePoint (xMid, yMid)); snake.setEnd(new SnakePoint (xEnd, yEnd)); snakeStack.push(snake); fromEndX = xStart; targetEndY = yStart; } return snakeStack; } public static List<LineObject> compareSnakePoint (SnakePoint from, SnakePoint end, List<LineObject> fromLineObjects, List<LineObject> targetLineObjects) { if (from.equals(end)) { return Collections.emptyList(); } List<LineObject> result = new ArrayList <>(); 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 { if (!from.getX().equals(end.getX())) { final LineObject lineObject = fromLineObjects.get(from.getX()); lineObject.setAction(ConstantVal.MINUS); result.add(lineObject); } else if (!from.getY().equals(end.getY())) { final LineObject lineObject = targetLineObjects.get(from.getY()); lineObject.setAction(ConstantVal.PLUS); result.add(lineObject); } } return result; } public static void main (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())); } }
