git 的耐心差异算法的实现是否正确？

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.
  */

根据我的理解，在这种情况下，独特的共同点是提到的两行bar，这些行周围最长的公共上下文应该是函数bar()连同它的文档块，这意味着差异应该归结为已删除的函数foo()连同它自己的文档块和下面的空行。

暂时没有其他人解决这个问题，所以我会尝试一下。不过，这纯粹是高级理论，因为我还没有阅读有关原始耐心算法的论文。

LCS（最长公共子序列）算法旨在减少寻找最小编辑距离解决方案所花费的时间。标准（动态规划）解决方案是 O(MN) where M是原始字符串中的符号数，N是目标字符串中的符号数。在我们的例子中，“符号”是行，“字符串”是行的集合，而不是带有字符的字符串（其中符号是，例如 ASCII 代码）。我们只需填写一个M x N“编辑成本”矩阵；完成后，我们通过向后追踪结果矩阵的最小路径来生成实际的编辑。看https://jlordiales.me/2014/03/01/dynamic-programming-edit-distance/举个例子。 （通过谷歌搜索找到的网页：这与我无关，除了现在高速扫描它以确保其正确性之外。它似乎是正确的。:-)）

实际上，对于大文件来说，计算这个矩阵是相当昂贵的，因为M and N是源代码行数（通常大约相等）：约 4k 行文件会在矩阵中产生约 16M 条目，必须将其完全填充，然后才能追踪最小路径。而且，比较“符号”不再像比较字符那么简单，因为每个“符号”都是完整的一行。 （通常的技巧是在矩阵生成期间对每一行进行散列并比较散列，然后在回溯期间重新检查，如果散列误导了我们，则将“保持不变符号”替换为“删除原始符号并插入新符号​​”。即使这样也可以正常工作在存在哈希冲突的情况下：我们可能会得到一个稍微次优的编辑序列，但实际上永远不会awful.)

LCS 通过观察保留长公共子序列（“保留所有这些行”）几乎总是会带来巨大胜利来修改矩阵计算。找到一些好的LCS-es后，我们将问题分解为“编辑非公共前缀，保留公共序列，并编辑非公共后缀”：现在我们计算two动态规划矩阵，但对于较小的问题，所以速度更快。 （当然，我们可以在前缀和后缀上递归。如果我们有一个约 4k 行的文件，我们发现中间附近有约 2k 条完全未更改的公共行，在顶部留下约 0.5k 行，在底部的 ~1.5k 处，我们可以在 ~0.5k“顶部有差异”行中检查长公共子序列，然后在 ~1.5k“底部有差异”行中再次检查。）

LCS 表现不佳，因此当“公共子序列”是像这样的琐碎行时，会导致可怕的差异     }，有很多匹配项，但并不真正相关。这耐心差异简单地变体discards这些线来自初始 LCS 计算，因此它们不是“公共子序列”的一部分。这使得剩余的矩阵larger，这就是为什么你必须要有耐心。 :-)

结果是，耐心 diff 在这里没有帮助，因为我们的问题与公共子序列无关。事实上，即使我们完全放弃 LCS 并只做一个大矩阵，我们仍然会得到不理想的结果。我们的问题是删除的成本：

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

（并且不插入任何内容）是same作为删除的成本：

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

任何一种的成本都只是“删除 5 个符号”。即使我们对每个符号进行加权——使非空行的删除比空行“更昂贵”——成本仍然是相同的：我们正在删除same最后五行。

相反，我们需要的是某种基于“视觉聚类”来对线条进行加权的方法：短线在边缘删除短线比删除便宜在中间。 Git 2.9 中添加的压缩启发式尝试在事后执行此操作。显然，它至少有一点缺陷（只有空行才算，而且它们必须实际存在，而不仅仅是到达边缘时暗示）。在矩阵填充期间进行加权可能会更好（假设在进行 LCS 消除后剩下的内容实际上是在经历完整的动态规划矩阵）。不过，这并不简单。