【首发】【Myers Diff】【差异纯算法】文章差异劲爆算法

明天自然醒 · 发表于 2022-12-5 22:45:18

什么是直观的 diff

我们先简单定义一下，什么是 diff：diff 就是目标文本和源文本之间的区别，也就是将源文本变成目标文本所需要的操作。

Myers算法由Eugene W.Myers在1986年发表的一篇论文中提出，是一个能在大部分情况产生”最短的直观的“diff的一个算法。

diff 与图搜索

”寻找最短的直观的diff”是一个非常模糊的问题，首先，我们需要把这个问题抽象为一个具体的数学问题，然后再来寻找算法解决。抽象的过程交给算法科学家了，抽象的结果是：寻找diff的过程可以被表示为图搜索

什么意思呢？还是以两个字符串，src=ABCABBA，dst=CBABAC为例，根据这两个字符串我们可以构造下面一张图，横轴是src内容，纵轴是dst内容，那么图中每一条从左上角到右下角的路径，都表示一个diff。向右表示删除，向下表示新增，对角线则表示原内容保持不动

根据图中形成的线路，我们可以选择一条路径看看它的效果

(0, 0) -> (1, 0)
(1, 0) -> (2, 0) -> (3, 1)
(3, 1) -> (3, 2) -> (4, 3) -> (5, 4)
(5, 4) -> (6, 4) -> (7, 5)
(7, 5) -> (7, 6)

这条路径代表的 diff 如下：
- A- B C+ B A B- B A+ C

现在，“寻找 diff” 这件事，被抽象成了“寻找图的路径”了。那么，“最短的直观的” diff 对应的路径有什么特点呢？
- 路径长度最短（对角线不算长度）
- 先向右，再向下（先删除，后新增）

三个概念

根据 Myers 的论文，他提出了三个概念：

snake: 一条snake代表走一步。例如从(0,0)->(0,1) / (0,0)->(1,0) / (0,1)->(0,2)->(2,4) 这分别为三条snake，走对角线不计入步数。
k line: 定义 k = x - y （我们可以写成 y = x - k，是相同斜率的平行斜线组成的一个集合)
d contour: 走一步算一个d

Myers 算法

Myers 算法就是一个能在大部分情况产生”最短的直观的“ diff 的一个算法，算法原理如下。

首先，定义参数 d 和 k，d 代表路径的长度，k 代表当前坐标 x - y 的值。定义一个”最优坐标“的概念，最优坐标表示 d 和 k 值固定的情况下，x 值最大的坐标。x 大，表示向右走的多，表示优先删除。
还是用上面那张图为例。我们从坐标 (0, 0) 开始，此时，d=0，k=0，然后逐步增加 d，计算每个 k 值下对应的最优坐标。
因为每一步要么向右（x + 1），要么向下（y + 1），对角线不影响路径长度，所以，当 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=2，k=2 时，最优坐标是 (3, 1)。
以此类推，直到我们找到一个 d 和 k 值，达到最终的目标坐标 (7, 6)。
下图横轴代表 d，纵轴代表 k，中间是最优坐标，从这张图可以清晰的看出，当 d=5，k=1 时，我们到达了目标坐标 (7, 6)，因此，”最短的直观的“路径就是 (0, 0) -> (1, 0) -> (3, 1) -> (5, 4) -> (7, 5) -> (7, 6)，对应的 diff 如下。

现在我们可以知道，其实 Myers 算法是一个典型的”动态规划“算法，也就是说，父问题的求解归结为子问题的求解。要知道 d=5 时所有 k 对应的最优坐标，必须先要知道 d=4 时所有 k 对应的最优坐标，要知道 d=4 时的答案，必须先求解 d=3，以此类推。

实现

算法原理知道以后，实现便是一件简单的事情了，基本流程如下：

最后补充一句，市面上使用的是标准 Myers 算法的一个变体。标准的算法有一个很大的缺点，就是空间消耗很大，因为我们需要存储每一个 d 对应的 v 字典。如果输入文件比较大，这样的空间开销是不能接受的。因此 Myers 在他的论文中，同时提供了一个算法变体，这个变体需要的空间开销要小得多。但是在某些情况下，变体产生的 diff 会和标准算法有所不同。也就是说，如果你按照上面的算法实现的程序，出来的结果和市面上的结果有所不同是正常的。

参考资料
The Myers diff algorithm: part 1

源码下载
两个版本：
版本1 无窗口：

Myers diff 无窗口.e (24.2 KB, 下载次数: 210)

已注销103181 · 发表于 2023-11-29 14:15:51

支持开源~！感谢分享

154251406 · 发表于 2023-11-29 04:04:22

支持开源~！感谢分享

天籁夕阳 · 发表于 2023-11-21 14:27:25

支持开源~！感谢分享

116154801 · 发表于 2023-11-14 12:00:58

6666666666666666666666666666666

lytsz · 发表于 2023-11-3 23:11:46

支持开源~！感谢分享

D名俾人改晒 · 发表于 2023-10-30 17:42:29

6666666666666666666666666

asasqwwq · 发表于 2023-10-10 22:30:02

感谢分享支持开源~！

shiqi123 · 发表于 2023-9-27 08:14:27

支持开源~！感谢分享支持开源~！感谢分享支持开源~！感谢分享

玄易 · 发表于 2023-9-18 11:49:15

支持开源~！感谢分享支持开源~！感谢分享支持开源~！感谢分享

		自动登录	找回密码
密码			注册

[2022开源大赛(第七届)] 【首发】【Myers Diff】【差异纯算法】文章差异劲爆算法