迈尔斯差分算法

作者: 躺在家里干活 | 来源:发表于2019-10-08 09:47 被阅读0次

说点什么

最近在关注Git diff的原理，其实就是将一个文件转换成另一个相似文件的过程。再简化一定就是如何将一个字符串转化成另一个字符串的问题。只不过文件转换的时候操作的原子是一行数据，字符串转换操作的原子是一个字符。

算法简介

来源：Eugene W. Myers的一篇论文，于1986年11月发表在“Algorithmica”杂志上
An O(Nd) difference Algorithm and Its Variations
思想：贪心算法 + 动态规划

算法

名词解释

字符串A 和字符串B
我们的目标是将A转换成B，这里要注意，A和B应该比较相似，这样才能体现出diff，如果两个字符串毫无关系，那么这个算法是没有意义的。
Shortest Edit Script（SES）
最短编辑次数，就是我们最少经过几次删除（删除的是A中的字符）和新增（新增B中的字符）操作，才能完成转换
Longest Common Subsequence ( LCS )
最长公共序列，不同于Longest Common Substring（最长公共子串），LCS不要求相同字符必须相连，比如AdB和ABC的LCS是AB。

不难发现，2和3之间是有关联的，一般一个LCS会对应一个SES，而LCS也可能有多个（比如ABC和ACB，AB和AC都是LCS），所以这个算法，并不是唯一解的。

将字符串转换用图表示出来

图表示

字符串A：ABCABBA
字符串B：CBABAC
其中，x轴代表字符串A，长度N = 7，y轴代表字符串B，长度M = 6。

图的基本操作：

横着走：表示删除字符串A中的元素
竖着走：表示增加字符串B中的元素
斜着走：表示此处A和B的元素是一致的，不需要删除也不需要新增

算法中的几个定义

1. Snake（蛇形线）

蛇形线

图解:

左上角当作是（0， 0）

从（0，0）到（0，1）是蛇形线（竖着走一步）

从（0，0）到（1，0）也是蛇形线（横着走一步）

从（1，0）到（2，0）再到（3，1）整体也是蛇形线

通俗的讲：蛇形线就是单个长度的横着走或者竖着走 + 任意长度的斜着走
数学角度来讲：单个删除或插入，后跟零个或多个对角线。

2. d contours（d步轮廓线）

1步到达轮廓

可以看出，从（0，0）开始，走一步，分别可以到达（1，0）和（0，1）

2步到达轮廓

在第一步的基础上，再走一步（一个蛇形线）发现可以到达三个地点，到达点的连线就是所说的轮廓

d表示一个量词，表示1，2，3...
d contours表示d步可以走到的点的连线，横着走一格或者竖着走一格都是一步，斜着走不算步数（其实就是走一个蛇形线）

3. K线

与对角线平行的直线，不要受坐标限制，注意是直线
（0，0）点的K线定义成 $K = 0$ ，K向右增加，向左减少，（0，1）处 $K = -1$ ，（1，0）处 $K = 1$
数学表示： $k = x - y$

解释看不懂，一看图就明白了：

K线

算法的原理

ZERO：怎样才能解决问题

如何解决问题

当到达上图中的右下角时就找到了一个解决方案，但是不能随便走，只有字符串相同时才能够走斜线。d的最大值时 $N + M$ （即字符串A和字符串B完全不同），这个时候就需要N个删除和M个插入

这里需要特别注意的是：

d步的起点是d-1步的终点，即走下一步的时候是以上一步的终点为起点的。

确定了解决问题的方式：

不断增加d直到，到达右下角，而我们找这个点，其实也就是找在K线上最远的距离

第一步：如何走（迭代）

迭代的计算，不同的d在K线上到达的最远距离。当到达右下角时就找到了一个解决方案。d的最大值时 $N + M$ （即字符串A和字符串B完全不同），这个时候就需要N个删除和M个插入

这里需要特别注意的是：

d步的起点是d-1步的终点，即走下一步的时候是以上一步的终点为起点的。

// 我们确认使用迭代的方式寻找能走到右下角的步数，0 开始，最大是 （N + M）
for (int d = 0; d <= N + M; d++)

第二步：每一步如何走

定理：对于给定的d，可以到达的唯一 $k$ 行位于 $[-d .. +d]$ 范围内
当所有移动都向下时，最远会有 $k = -d$ ，而当所有移动都在右边时， $k = d$ 是最远的边界

多想一点：d如果是奇数，那么是不是只能走到奇数值的K线上？？？

如何解决问题
如图，走1步的话，只能走到K = 1 或者 k = -1处，走两步只能走到-2，0，2处

//  我们确认了要计算多少条K线
for ( int k = -d; k <= d; k += 2)

第三步：每条K线上如何走到最远点

思考：

想要走到一个 $K$ 线上，只能从 $K+1$ 向下走，或者从 $K-1$ 向右走
$d$ 步的起点是 $d - 1$ 步的终点，即走下一步的时候是以上一步的终点为起点的。（回忆一下）

如果我们知道 $d - 1$ 中，到达各个K线的最远距离，那么我们就能知道d步可以到达的最远点

如何走：

如果 $K = -d$ ，只能通过往下走

如果 $K = d$ ，只能往右走
这是两种边缘的情况，试想走d步，想要到达K或者-K，只能一直朝着一个方向走

如果 $K$ 位于 $-d$ 和 $d$ 之间，我们遵循先删除的原则，如果 $（k -1）$ 处的ｘ值小于 $（k + 1）$ 的ｘ值，就向下移动（因为此时，在 $d-1$ 步的时候，发生了删除）
当然这里也可以遵循先增加的原则，那么就需要选择向右移动

// V[K - 1]表示在K-1这条线上，x轴的值
bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
// 要注意的是，无论向哪个方向走，都需要判断接下来是否有相同的字符，如果有就能走的更远

第四步：走好前两步

如何解决问题

走第一步的时候， $d = 1$ ，根据上面第二步的分析，我们需要考虑 $k = -1，1$ ， $k = -1$ 时向下（（0，0）=> （0，1））， $k = 1$ 向右（（0，0）=>（1，0））

走第二步的收， $d = 2$ ，需要考虑 $k = -2，0，2$ 。

当 $k = -2$ 时，需要往下（0，1）=>（0，2），但是这时候还不算结束，因为两个字符串中有相同的字符，可以斜着走，所以最终是（0，1）=>（0，2）=>（2，4）

当 $k = 0$ 时， $V[ K - 1]$ = $V[ -1 ]$ = 0， $V[ k + 1 ]$ = $V[ 1 ]$ = 1，根据我们第三步的想法，需要向下（（1，0）=>（1，1）），此时发现还可以斜着走，最终（1，0）=>（1，1）=>（2，2）

当 $k = 2$ 时，k = d，所以向右，也可以斜着走，所以（1，0）=>（2，0）=>（3，1）
......

最后一个问题：我们能走出第一步吗？

从上面了解到每次走都需要依靠上一步的最远到达点，但是第一步怎么办，去依赖谁？

为了解决这个问题，我们需要为 $d = 0$ 设定一个起点，我们设置 $V[1]= 0$ ，这表示 $k = 1$ 线上， $x = 0$ 的点，所以这个点是（0，-1）。
我们需要做的就是保证从这一点向下移动，把我们带到（０，０）点
结合上面的分析，当 $d = 0$ 时， $k = 0$ ，这个时候向下移动，发现是可以将我们带回（０，０）点的

就是那个点

引用，参考

CodeProject - Investigating Myers' diff algorithm

我的个人博客,有空来坐坐