Myers算法文本差异纯算法文章差异易语言源码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,以此类推。

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

迭代 d,d 的取值范围为 0 到 n+m,其中 n 和 m 分别代表源文本和目标文本的长度(这里我们选择以行为单位)
每个 d 内部,迭代 k,k 的取值范围为 -d 到 d,以 2 为步长,也就是 -d,-d + 2,-d + 2 + 2…
使用一个字典 v,以 k 值为索引,存储最优坐标的 x 值
将每个 d 对应的 v 字典存储起来,后面回溯的时候需要用
当我们找到一个 d 和 k,到达目标坐标 (n, m) 时就跳出循环
使用上面存储的 v 字典(每个 d 对应一个这样的字典),从终点反向得出路径

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

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系贝贝进行处理。
本站默认解压密码:www.hibbba.com