git - git的耐心差异算法实现正确吗？

Question

This question on Stackoverflow似乎是耐心差异算法应用的不错选择。但是，在测试我的潜在答案时，我发现 git diff --patience 不能达到我的期望(在这种情况下，它与默认的diff算法没有区别):

$ cat a
/**
 * Function foo description.
 */
function foo() {}

/**
 * Function bar description.
 */
function bar() {}

$ cat b
/**
 * Function bar description.
 */
function bar() {}

$ git diff --no-index --patience a b
diff --git a/a b/b
index 3064e15..a93bad0 100644
--- a/a
+++ b/b
@@ -1,9 +1,4 @@
 /**
- * Function foo description.
- */
-function foo() {}
-
-/**
  * Function bar description.
  */
 function bar() {}

我希望差异是:

diff --git a/a b/b
index 3064e15..a93bad0 100644
--- a/a
+++ b/b
@@ -1,8 +1,3 @@
-/**
- * Function foo description.
- */
-function foo() {}
-
 /**
  * Function bar description.
  */

以我的理解，在这种情况下，唯一的公共(public)行是提到 bar 的两行，并且这些行周围最长的公共(public)上下文应该是bar()函数及其docblock，这意味着diff应该归结为已删除的函数foo()连同其自己的docblock和以下空白行。

Answer 1

暂时没有人解决过这个问题，因此我将对其进行介绍。由于我还没有阅读有关原始耐心算法的文章，因此，这全都是纯粹的高级理论。

LCS(最长公共(public)子序列)算法都是为了减少寻找最小编辑距离解决方案所花费的时间。标准(动态编程)解决方案是O(MN)，其中M是原始字符串中的符号数，N是目标字符串中的符号数。在我们的例子中，“符号”是行，“字符串”是行的集合，而不是带有字符的字符串(其中的符号是例如ASCII码)。我们只需填写一个M x N的“编辑成本”矩阵即可；完成后，我们通过在生成的矩阵中向后追溯一条最小路径来产生实际的编辑。有关示例，请参见https://jlordiales.me/2014/03/01/dynamic-programming-edit-distance/。 (通过Google搜索找到的网页:除了我现在要对其进行高速扫描以确保正确性之外，这与我无关，这似乎是正确的。:-))

实际上，对于大文件而言，计算此矩阵是相当昂贵的，因为M和N是源行的数量(通常近似相等):〜4k行文件会在矩阵中产生约1600万个条目，必须先完全填写该行追溯最小路径。而且，比较“符号”不再像比较字符那样琐碎，因为每个“符号”都是完整的一行。 (通常的技巧是在矩阵生成过程中对每一行进行散列并比较散列，然后在回溯期间进行重新检查，如果散列误导了我们，则将“保留不变的符号”替换为“删除原始并插入新的”。即使这样，效果也很好在存在哈希冲突的情况下:我们可能会得到一个稍微次优的编辑序列，但实际上绝不会糟透了。)

LCS通过观察保持较长的公共(public)子序列(“保留所有这些行”)几乎总是会取得重大胜利来修改矩阵计算。找到一些好的LCS-es后，我们将问题分解为“编辑非公共(public)前缀，保留公共(public)序列并编辑非公共(public)后缀”:现在我们计算两个动态编程矩阵，但是对于较小的问题，因此跑得更快。 (当然，我们可以递归前缀和后缀。如果我们有〜4k行文件，并且在中间附近找到了约2k完全不变的不常见线，在顶部和顶部留了〜0.5k行，在底部〜1.5k，我们可以在〜0.5k“顶部具有差异”行中检查较长的公共(public)子序列，然后在〜1.5k“底部具有差异”行中进行检查。)

当“公共(public)子序列”是琐碎的行(如     })具有很多匹配项但并不真正相关时，LCS的表现不佳，从而导致糟糕的差异。耐心diff变体只是从初始LCS计算中丢弃这些行，因此它们不属于“公共(public)子序列”。这会使剩余的矩阵更大，这就是为什么您必须要有耐心的原因。 :-)

结果是，耐心差异在这里没有帮助，因为我们的问题与常见子序列无关。实际上，即使我们完全放弃了LCS并只做了一个大矩阵，我们仍然会得到不理想的结果。我们的问题是删除的代价:

- * Function foo description.
- */
-function foo() {}
-
-/**

(并且不插入任何内容)与删除的费用相同:

-/**
- * Function foo description.
- */
-function foo() {}
-

任一个的成本都只是“删除5个符号”。即使我们对每个符号进行加权(使非空行比空行都“昂贵”地删除)，费用也保持不变:最后，我们将删除相同的五行。

相反，我们需要的是一种基于“视觉聚类”对线进行加权的方法:删除边缘的短线比中间的短线便宜。事实之后，Git 2.9中添加的压缩启发式方法尝试执行此操作。显然至少有一点瑕疵(只有空白行才算在内，而且它们必须实际存在，而不仅仅是达到边缘就意味着存在缺陷)。最好在矩阵填充过程中进行加权(假设在消除LCS之后剩下的实际上是经过完整的动态编程矩阵)。但是，这是不平凡的。