Git(2017)中使用的Myers Diff算法

2020-05-31 11:08:23

如果您喜欢这篇文章，我已经出版了一本书，通过实现解释了Git的内部结构：构建Git。

作为一名程序员，您可能会使用诸如Git这样的版本控制系统，并且花费大量时间查看不同之处。您可以使用它们来检查正在进行的未提交工作，查看在一次提交中发生了什么变化，在执行合并之前比较两个分支，等等。差异是一种语言，通过这种语言，您可以了解软件中的情况发生了怎样的变化。

但是，除了被人们读取之外，您的版本控制系统还使用Diffs来自动化更改。您可以通过电子邮件将diff发送给某人，他们可以使用补丁或git应用命令将其合并到他们的工作副本中。Git合并必须协调和合并两个或多个更改历史，以生成一个Singletree，通常会协调同一文件中的更改。Git Add--Patch允许您从工作副本文件中选择单个更改，而不是将整个文件添加到索引中，这涉及到您(阅读差异的用户)和Git有选择地将它们应用到文件的索引版本。一些版本控制系统使用版本之间的差异作为它们存储项目历史的主要方式，而不是在每次提交之前存储所有代码的快照。

因此，差异是版本控制的核心，但是您可能没有过多考虑它们是如何生成的。通常，当您阅读差异时，对您来说，哪些事情应该标记为更改似乎是显而易见的。对于在文件中插入新函数、删除冗余函数或重写一节意味着什么，您有一个直观的心理模型。然而，不同之处比看上去要多得多，而且有很多方法可以产生不同的结果。

想一想，你将如何计算差值，以及如何编写函数来计算差值。您可能已经注意到，DIFF程序只向您显示发生了什么变化，而不是什么保持不变。您如何确定文件的哪些部分没有更改？一旦您发现了它们之间的差异，您将如何在每个版本中找到文本再次匹配的下一行呢？这比看起来要复杂得多！

在本系列文章中，我想带您了解Git使用的默认扩散算法。它是由尤金·W·迈尔斯(Eugene W.Myers)开发的，原稿可以在网上获得。虽然这篇论文很短，但它的数学密度相当高，并专注于证明它是有效的。这里的解释将不那么严谨，但希望能更直观，给出算法实际做什么以及它是如何工作的详细演练。

在第一篇文章中，我们将介绍该算法要实现的基本模型，并通过一个示例说明它如何计算出从一个版本到另一个版本的最简单的编辑集。

为了使用论文中的示例，假设我们要计算两个字符串之间的差异：

我们所说的“差异”是指将字符串An转换为字符串b的编辑序列。一种可能的序列是简单地删除a中的每个字符，然后在b中插入每个字符，或者使用常见的diff表示法：

然而，我们不会认为这是一个高质量的差异，因为它不能告诉我们太多。对源代码的更改通常会使文件的大部分内容保持不变，我们确实希望看到插入或删除的代码部分。显示整个文件被删除并替换为新版本的差异对我们没有多大用处。

这使得为了生成b而对a进行尽可能少的更改，因此它更好地可视化了实际更改的内容。这不是唯一可能的解决方案，例如，这些也是有效的：

1.-A 2.-A 3.+C-B+C-A C B B-A-C-C B A A+A B-B A+C+C+C。

然而，它们都是最小的：它们使最小数量的编辑成为可能，在本例中是5。有趣的是，它们的不同之处在于它们认为字符串之间的哪些部分相同，以及它们执行编辑的顺序不同。通过观察不同之处，你可能会有一个直观的想法，即不同之处只显示了变化的东西，但这些例子表明，对两部电影之间的不同有许多可能的解释。

因此，差分算法的目的是提供一种产生差分的策略，其中差分具有某些理想的性质。我们通常希望差异尽可能小，但还有其他考虑因素。例如，当您更改某些内容时，您可能习惯于看到先删除后插入，而不是反过来。也就是说，您宁愿看到上面的解决方案2而不是解决方案3。而且，当您更改整个代码块时，您希望看到整个块被删除，然后插入新代码，而不是看到许多删除和插入相互交错。

好的：-一个坏的：-一-二+四-三-二+四+五+五+六+六-三。

您可能还希望看到删除或插入的代码与您对代码结构的想法一致，例如，如果您插入一个方法，您希望该方法的结尾被视为新的，而不是前面的方法的结尾：

好：类foo坏：类foo def initialize(Name)def initialize(Name)@name=name@name=name end+end+def check+def check+@name+@name+end end。

迈尔斯的算法就是这样一种策略，但它速度很快，而且它产生的差异往往质量都很好。它是通过贪婪的方式做到这一点的，即在进行更改之前尝试使用尽可能多的相同行(因此避免了“错误结束”问题)，并且在有选择的情况下更喜欢删除而不是插入，这样删除就会首先出现。

迈尔斯的论文基于这样一种想法，即寻找最短的编辑脚本(SES)可以建模为图搜索。让我们以两个字符串a=ABCABBA和b=CBABAC为例，构建一个从a到b的所有路径图。

下面显示的网格中的(x，y)坐标对应于编辑过程中的步骤；在(0，0)处，我们有字符串a，也就是说，我们还没有开始编辑。向右移动(增加x)对应于从a中删除一个字符，例如移动到(1，0)表示我们从a中删除了第一个A。向下移动(增加y)对应于从b插入一个字符，例如，如果我们现在从(1，0)向下移动到(1，1)，我们从b插入第一个C，因此我们的编辑字符串是CBCABBA。在位置(4，3)，我们已经将ABCA转换为CBA，但是我们仍然需要将BBA转换为BAC。右下角位置(7，6)对应于将字符串A完全转换为字符串B。

除了向右和向下移动之外，在某些位置，我们还可以沿对角线移动。当两个字符串在位置的索引处具有相同的字符时会发生这种情况，例如，a中的第三个字符和b中的第一个字符都是C，因此位置(2，0)具有指向(3，1)的对角线。这相当于从两个字符串中使用一个相等的字符，既不删除也不插入任何内容。

A B C A B A o-o 0|\|C|\|\|o。o 1||\|-o 2|\|\||\|A|\|。-o-o 3||\\|B||\||o-o 4|\|\|。|\|A|\|o-o 5|\|C|\|\|-o-o。-o-o 6 0 1 2 3 4 5 6 7。

Myers算法背后的思想非常简单：我们希望在尽可能少的移动中从(0，0)到(7，6)(右下角)。“移动”是向右的单步(从a删除)或向下的(从b插入)。从a到b，我们最多可以移动13次：两个字符串的长度总和。

然而，行走对角线路径是自由的，因为它们不对应于做出改变，因此我们希望最大化所采取的对角线步数，并最小化向右/向下移动的次数。上面的例子表明，我们实际上只需进行五次编辑就可以从a转到b，而myers提供了一种找到这条路径的策略。

为了直观地了解算法是如何工作的，让我们开始探索图表。为了找到到右下角位置的最短路径，我们将从(0，0)开始依次探索每条可能的路径，直到找到一条到达终点的路径。我建议您在执行此操作时，将上面的网格放在手边。

从这个位置我们有两个选择：我们可以向下移动到达(0，1)，或者向右移动到达(1，0)。

现在让我们考虑一下(0，1)。如果我们从这里向下移动，我们达到(0，2)，但是从那里到(1，3)和从(1，3)到(2，4)有一条对角线，既然对角线移动是自由的，我们可以说从(0，1)getsus向下移动只需要一次移动。因此，我们将从(0，1)移动到(2，4)标记为步行中的一步。

从(0，1)向右移动到(1，1)，从那里到(2，2)又有一条对角线。让我们在散步时标记这两个动作。

现在让我们考虑我们从(0，0)中提取的另一个分支，向右移动到(1，0)。从(1，0)向下移动将我们带到(1，1)，正如我们刚刚发现的那样，它将我们带到(2，2)。从(1，0)向右移动到与(3，1)成对角线的(2，0)。同样，我们将记录这两个步骤。

我将(2，2)记录为通过(1，0)而不是(0，1)访问，原因稍后将会清楚。直观地说，首先向右移动意味着首先执行删除，我们通常希望删除出现在插入之前。

现在我们已经充分研究了图形的两个步深，我们可以开始第三步了。从(2，4)向下移动到(2，5)，从那里到(3，6)是对角线。从(2，4)向右移动将我们带到(3，4)，在这里又是一条对角线将我们带到(4，5)。

0，0--1，0-3，1|0，1，2||2，4-4，5||3，6

接下来，我们考虑(2，2)。从那里向右移动就像我们以前看到的那样：我们移到(3，2)，然后沿着对角线从那里到(5，4)。然而，向下移动引入了一个新的情况：这个移动将我们带到(2，3)，并且从那里没有对角线。现在，如果我们要进行通用的图搜索，我们希望记录从(2，4)向右移动的结果和从(2，2)向下移动的结果，即：

0，0--1，0-3，1|0，1，2-5，4|\2，4-2，3|\|4，53，6。

然而，我们正在检查的特定图表的结构意味着，仅存储在特定编辑集之后可以到达的最佳位置就足够了。上面的记录显示，进行两次插入，然后进行删除(向下两次，然后向右)会得到(4，5)，而首先进行删除，然后再进行两次插入，就会得到(2，3)。因此，我们只保留(4，5)结果并丢弃(2，3)，表明(4，5)是按任意顺序删除一次和插入两次之后可到达的最佳位置。

0，0--1，0-3，1|0，1，2-5，4||2，4-4，5||3，6。

最后，在深度2扫描中，我们访问(3，1)。从那里向下移动到(3，2)，它沿对角线指向(5，4)，所以我们再次将其记录为从(3，1)向下移动，而不是从(2，2)向右移动。从(3，1)向右移动得到(4，1)，它与(5，2)对角线。

0，0--1，0-3，1--5，2|0，1，2，5，4||2，4-4，5||3，6。

你现在可能已经掌握了诀窍，所以让我们快速完成剩下的动作吧。我们不能从(3，6)向下移动，从那里向右移动给出(4，6)，它也可以从(4，5)向下到达，所以我们将其标记为这样。(4，5)的右边是(5，5)。

0，0--1，0--3，1--5，2|0，1，2，5，4||2，4-4，5-5，5|3，6，6

(5，5)也是向下的(5，4)，所以我们将其标记为，从(5，4)向右移动得到(6，4)，并有一条对角线通向(7，5)。

0，0--1，0--3，1--5，2|0，1，2，5，4-7，5|2，4-4，55，5|3，6，6。

从(5，2)向下也通向(7，5)，并从(5，2)领先向右移动到(7，3)，从而完成第四行扫描。

0，0--1，0--3，1-5，2-7，3|0，1，2，2，5，4-7，5|2，4-4，5，5|3，6，6。

现在我们开始第五排。因为我们知道从a到b的差异只需要五次编辑，所以我们预计扫描的这一行将找到右下角位置(7，6)。

从(4，6)开始没有向下的东西，向右是(5，6)，也是从(5，5)向下。(5，5)的右边是(6，5)。

0，0--1，0--3，1-5，2-7，3|0，1，2，2，5，4-7，5|2，4--4，5，5-6，5|3，6，4，6，6。