git 对 patience diff 算法的实现是否正确？

Question

seemed to be a good candidate for the application of the patience diff algorithm. However, while testing my potential answer, I found that 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() 及其自己的文档块和以下空行。

Answer 1

一段时间以来还没有其他人解决过这个问题，所以我来试一试。不过，这完全是高层次的理论，因为我还没有阅读有关原始耐心算法的论文。

LCS（最长公共子序列）算法都是为了减少寻找最小编辑距离解决方案所花费的时间。标准（动态规划）解决方案是 O(MN) 其中 M 是原始字符串中的符号数，N 是目标字符串中的符号数。在我们的例子中，"symbols" 是行，"string" 是行的集合，而不是带有字符的字符串（符号所在的位置，例如 ASCII 代码）。我们简单地填入一个M x N矩阵"edit costs"；完成后，我们通过向后跟踪生成的矩阵的最小路径来生成实际的编辑。有关示例，请参见 https://jlordiales.me/2014/03/01/dynamic-programming-edit-distance/。（通过 Google 搜索找到的网页：这与我无关，只是现在高速扫描它以确保正确性。它似乎是正确的。:-)）

实际上计算这个矩阵对于大文件来说是相当昂贵的，因为 M 和 N 是源代码行的数量（通常大约等于): ~4k 行文件导致矩阵中有~16M 条目，在我们可以追溯最小路径之前必须将其完全填充。此外，比较 "symbols" 不再像比较字符那样简单，因为每个 "symbol" 都是一个完整的行。（通常的技巧是在矩阵生成期间对每一行进行散列并比较散列，然后在回溯期间重新检查，如果散列误导了我们，则将 "keep unchanged symbol" 替换为 "delete original and insert new"。即使在哈希冲突的存在：我们可能会得到一个非常次优的编辑序列，但它实际上永远不会糟糕。）

LCS 通过观察保持长的公共子序列 ("preserve all these lines") 几乎总是导致大赢来修改矩阵计算。找到一些好的 LCS-es 后，我们将问题分解为 "edit the non-common prefix, keep the common sequence, and edit the non-common suffix"：现在我们计算两个动态规划矩阵，但对于较小的问题，因此速度更快。（当然，我们可以在前缀和后缀上递归。如果我们有一个 ~4k 行的文件，我们发现~2k 完全不变，靠近中间的公共行，在顶部留下~0.5k 行， ~1.5k 在底部，我们可以检查 ~0.5k "top has a difference" 行中的长公共子序列，然后在 ~1.5k "bottom has a difference" 行中再次检查。）

LCS 表现不佳，因此导致可怕的差异，当 "common subsequences" 是像 } 这样的微不足道的行时，有很多匹配项但并不真正相关。 patience diff 变体只是丢弃这些来自初始 LCS 计算的行，因此它们不是 "common subsequence" 的一部分。这使得剩余的矩阵更大，这就是为什么你必须耐心等待。 :-)

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

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

（不插入任何内容）与删除的成本相同：

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

任何一个的成本都只是 "delete 5 symbols"。即使我们对每个符号进行加权——让非空行 "more expensive" 比空行删除——成本保持不变：我们正在删除 相同的 五行，在结束。

相反，我们需要的是基于 "visual clustering" 对线进行加权的一些方法：在边缘 处的短线 比短线 [=32] 更容易删除=]在中间。添加到 Git 2.9 的压缩启发式尝试在事后执行此操作。它显然至少有一点缺陷（只有空白行才算数，而且它们必须实际存在，而不仅仅是通过到达边缘来暗示）。在矩阵填充期间进行加权可能会更好（假设在进行 LCS 消除后剩下的，实际上是通过完整的动态规划矩阵）。不过，这很重要。

Answer 2

我发现了 Bram Cohen 的更新 post，其中 his description of the patience diff algorithm 支持观察到的 git diff 输出：

... how Patience Diff works -

Match the first lines of both if they're identical, then match the second, third, etc. until a pair doesn't match.

Match the last lines of both if they're identical, then match the next to last, second to last, etc. until a pair doesn't match.

Find all lines which occur exactly once on both sides, then do longest common subsequence on those lines, matching them up.

Do steps 1-2 on each section between matched lines

所以算法对独特线条的强调被步骤 1. 和 2. 破坏了，它们检测公共前缀和后缀，即使它们是由嘈杂的线条组成的。

这样的表述与我之前看到的有点不同，Bram 承认他稍微修改了一下：

I've previously described it with the ordering a bit different ...

我的问题实际上重复了 this comment 中表达的对 Bram 的 post 的关注。

git 对 patience diff 算法的实现是否正确？

Is git's implementation of the patience diff algorithm correct?

git

git-diff