研究 Myers 的 diff 算法：第 1 部分，共 2 部分
4.97/5 (18投票s)
基本的贪心算法。
目录
引言
本文旨在探讨 Eugene W. Myers 在其论文 "An O(ND) Difference Algorithm and Its Variations" 中所述的基本贪心 diff 算法。该论文发表于 1986 年 11 月的 "Algorithmica" 期刊。论文的 PDF 版本可在此处 获取[^]。
在其论文中，Myers 还通过 "线性空间优化" 扩展了他的基本算法。这需要对本文所述的基本算法有深刻的理解。它将在第二部分进行探讨，第二部分也可在 The Code Project 找到[^]。
下载中的应用程序是一个学习辅助工具。它以图形方式显示算法的各个阶段。我建议您在阅读本文时使用它来帮助理解算法。本文中的图表是应用程序的屏幕截图。
本文使用逐字符 diff，但该算法可用于任何具有相等运算符的数据类型。
背景
我开始研究 diff 算法是为了参加 2009 年 8 月在 The Code Project 举行的一场比赛。我越是了解 Myers 的算法，就越觉得它们很美妙。我强烈建议花些时间研究它们。我自己在学习和实现它们的过程中也感到非常高兴。
我写这篇文章是因为我花了大约一周的时间才从论文中理解并实现了这个算法。您可以在一小时内读完这篇文章，我希望这将让您对 Myers 的工作有一个大致的了解。我试图解释必要的原理和理论，而不给出证明。证明可以在 Myers 的论文中找到。
定义
文件 A 和文件 B
diff 算法以两个文件作为输入。第一个通常是较旧的文件，称为文件 A，第二个文件称为文件 B。算法会生成将文件 A 转换为文件 B 的指令。
最短编辑脚本 ( SES )
该算法找到将文件 A 转换为文件 B 的最短编辑脚本。SES 只包含两种命令：从文件 A 中删除和插入到文件 B 中。
最长公共子序列 ( LCS )
查找 SES 等同于查找两个文件的最长公共子序列。LCS 是通过删除一些字符可以从两个文件中生成的最长字符列表。LCS 与最长公共子串不同，后者必须是连续的。
对于任何两个文件，可能存在多个 LCS。例如，给定序列 "ABC" 和 "ACB"，长度为 2 的 LCS 有两个："AB" 和 "AC"。LCS 直接对应于 SES，因此对于任何两个文件，也可能存在多个相同长度的 SES。该算法只返回它找到的第一个 LCS / SES，因此它可能不是唯一的。
示例序列
本文使用了与论文相同的示例。文件 A 包含 "ABCABBA"，文件 B 包含 "CBABAC"。它们表示为两个字符数组：A[] 和 B[]。
A[] 的长度为 N，B[] 的长度为 M。
编辑图
这是示例的编辑图。数组 A 放置在顶部 x 轴上。数组 B 沿着向下读取的 y 轴放置。
|
|
|
图 1：示例编辑图
|
解决方案是从左上角 ( 0, 0 ) 到右下角 ( 7, 6 ) 的最短路径。
您始终可以水平或垂直移动一个字符。水平（向右）移动表示从文件 A 中删除，垂直（向下）移动表示插入到文件 B 中。如果存在匹配的字符，您也可以对角线移动，停在匹配处。
解决方案是包含最多对角线的轨迹。LCS 是轨迹中的对角线，SES 是其中的水平和垂直移动。对于示例，LCS 长度为 4 个字符，SES 长度为 5 个差异。
蛇形
该论文有些含糊不清，但我理解蛇形定义为单个删除或插入，后跟零个或多个对角线。
对于示例，有两个从左上角 ( 0, 0 ) 开始的蛇形。一个向右移动到 ( 1, 0 ) 并停止。另一个向下移动到 ( 0, 1 ) 并停止。从 ( 0, 1 ) 开始的下一个蛇形移动到 ( 0, 2 )，然后沿着对角线移动到 ( 2, 4 )。我将这些点称为起始点、中间点和终点。
k 线
您可以绘制从 x 轴和 y 轴上的点开始并平行于对角线的线。这些称为 k 线，将非常有用。从 ( 0, 0 ) 开始的线定义为 k = 0。k 在向右的线中增加，在向下的线中减小。因此，通过 ( 1, 0 ) 的 k 线具有 k = 1，通过 ( 0, 1 ) 的 k线具有 k = -1。
实际上，它们是由方程 y = x - k 表示的线。这也有用，因为我们只需要存储给定 k 线上的某个点的 x 值，然后就可以简单地计算 y 值。
d 等高线
差异由编辑图中的水平或垂直移动表示。一系列连续的蛇形具有一个 d 值，该值是该轨迹中的差异数量，与其中的对角线数量无关。可以创建 d 等高线来连接具有给定 d 值的轨迹的所有终点。
贪心算法
现在我们将探讨基本的贪心算法，即不带线性空间优化。
|
|
|
图 2：向前贪心解决方案
|
编辑图
这张图看起来令人生畏，但我将一层一层地讲解。
- k 线： 棕色线是奇数 k 值的 k 线。黄色线是偶数 k 值的 k 线。
- 蛇形： 深蓝色线是蛇形。红色蛇形显示了解决方案的轨迹。
- d 等高线： 浅蓝色线是差异等高线。例如，标有“2”的线上的三个终点都恰好有 2 个水平或垂直移动。
算法
该算法是迭代的。它计算连续 d 的每条 k 线上最远的路径。当路径到达右下角时找到解决方案。由于我们已经计算了所有具有较小 d 的可能性，因此这保证是 LCS / SES。最大 d 值是没有匹配的情况，即 N 次删除 + M 次插入。
for ( int d = 0 ; d <= N + M ; d++ )
在此循环内部，我们必须找到每条 k 线上最远的路径。对于给定的 d，可以到达的唯一 k 线位于范围 [ -d .. +d ] 内。当所有移动都是向下时，k = -d 是可能的，而 k = +d 是当所有移动都是向右时。实现的一个重要观察是，偶数 d 的终点位于偶数 k 线，反之亦然。因此，内循环是
for ( int k = -d ; k <= d ; k += 2 )
所以，缺失的部分是如何找到给定 k 线上最远的路径。
首先要注意的是，要到达 k 线，您必须要么从 k+1 线向下移动，要么从 k-1 线向右移动。如果我们保存前一个 d 的最远路径，我们可以选择能让我们在 k 线前进最远的移动。两个边缘情况是，当 k = -d 时，您只能向下移动，而当 k = +d 时，您只能向右移动。
d = 3 时的示例
我将以 d = 3 的示例为例，这意味着 k 线为 [ -3, -1, 1, 3 ]。为了提供帮助，我已将示例中的蛇形终点转录到下表中。
|
|
|
图 3：终点表
|
k = -3： 在 d = 2 时无法到达 k = -4 线，因此我们必须从 k = -2 线向下移动。我们从上一个 d = 2 保存的结果为我们提供了起始点 ( 2, 4 )。向下移动给出了中间点 ( 2, 5 )，然后我们有一个对角线将其带到 ( 3, 6 )。
k = -1： 这里我们有两个选择。我们可以从 k = -2 向右移动，也可以从 k = 0 向下移动。查看上一个 d = 2 的结果，k = -2 上的前一个点是 ( 2, 4 )，k = 0 上的前一个点是 ( 2, 2 )。从 k = -2 向右移动将我们带到 ( 3, 4 )，从 k = 0 向下移动将我们带到 ( 2, 3 )。因此，我们选择 k = -2，因为它能让我们在 k = -1 线上前进更远。我们再次有一个对角线，所以我们的蛇形是 ( 2, 4 ) -> ( 3, 4 ) -> ( 4, 5 )。
k = 1： 我们再次有两个选择。我们可以从 k = 0 向右移动，也可以从 k = 2 向下移动。之前结束的点是 ( 2, 2 ) 和 ( 3, 1 )，它们都将我们带到 ( 3, 2 )。我们将任意选择从 x 值较大的点开始，它与对角线一起给出了蛇形 ( 3, 1 ) -> ( 3, 2 ) -> ( 5, 4 )。
k = 3： 这是另一个边缘情况。d = 2 时无法到达 k = 4 线，因此我们必须从 k = 2 向右移动。我们上一个在 k = 2 上的结果是 ( 3, 1 )，所以向右移动将我们带到 ( 4, 1 )。我们再次有一个对角线，给出了终点 ( 5, 2 )。
实现
我们如何实现这一点？我们有两个循环，我们需要一个数据结构。
请注意，d(n) 的解仅取决于 d(n - 1) 的解。另外请记住，对于偶数 d，我们在偶数 k 线上找到终点，而这些终点仅取决于前一个终点，而前一个终点都在奇数 k 线上。对于奇数 d 也是如此。
因此，我们使用一个名为 V 的数组，以 k 作为索引，以终点的 x 位置作为值。我们不需要存储 y 位置，因为给定 x 和 k 我们可以计算出它：y = x - k。另外，对于给定的 d，k 位于 [ -d .. d ] 的范围内，这些是 V 的索引，因此限制了其大小。
这效果很好，因为当 d 为偶数时，我们使用不可变的奇数 k 值来计算偶数 k 索引的终点。对于奇数 d 也是如此。
因此，决定向下或向右移动以到达给定 k 线的决定可以写成一个布尔表达式
bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
如果 k = -d，我们必须向下移动，如果 k = d，我们必须向右移动。对于正常的中部情况，我们选择从 x 值较大的相邻线开始。这保证了我们到达 k 线上最远的点。
我们还需要一个 d = 0 的存根，所以我们设置 V[ 1 ] = 0。这代表 k = 1 线上 x = 0 的一个点。因此，这是点 ( 0, -1 )。我们保证从这一点向下移动，将其带到所需的 ( 0, 0 )。
所以，这是核心实现
V[ 1 ] = 0;
for ( int d = 0 ; d <= N + M ; d++ )
{
for ( int k = -d ; k <= d ; k += 2 )
{
// down or right?
bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
int kPrev = down ? k + 1 : k - 1;
// start point
int xStart = V[ kPrev ];
int yStart = xStart - kPrev;
// mid point
int xMid = down ? xStart : xStart + 1;
int yMid = xMid - k;
// end point
int xEnd = xMid;
int yEnd = yMid;
// follow diagonal
int snake = 0;
while ( xEnd < N && yEnd < M && A[ xEnd ] == B[ yEnd ] ) { xEnd++; yEnd++; snake++; }
// save end point
V[ k ] = xEnd;
// check for solution
if ( xEnd >= N && yEnd >= M ) /* solution has been found */
}
}
解决方案
上面的代码找到了到达两个序列末尾的第一个蛇形。然而，V 中的数据仅存储每条 k 线的最新终点。要找到导致解决方案的所有蛇形，需要为每个 d 的迭代拍摄 V 的快照，然后从 dsolution 向后计算到 0。
IList<V> Vs; // saved V's indexed on d
IList<Snake> snakes; // list to hold solution
POINT p = new POINT( N, M ); // start at the end
for ( int d = vs.Count - 1 ; p.X > 0 || p.Y > 0 ; d-- )
{
var V = Vs[ d ];
int k = p.X - p.Y;
// end point is in V
int xEnd = V[ k ];
int yEnd = x - k;
// down or right?
bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
int kPrev = down ? k + 1 : k - 1;
// start point
int xStart = V[ kPrev ];
int yStart = xStart - kPrev;
// mid point
int xMid = down ? xStart : xStart + 1;
int yMid = xMid - k;
snakes.Insert( 0, new Snake( /* start, mid and end points */ ) );
p.X = xStart;
p.Y = yStart;
}
需要注意的是，这种“贪心”算法在时间和空间上的复杂度都是 O( (N+M) D )。
结论
我希望您像我一样享受阅读这篇文章的乐趣。
本文的第二部分，探讨线性空间优化，也可在 The Code Project 找到[^]。
最后，请留下您的投票和/或评论。谢谢。
历史
- 2009 年 9 月：第一版。