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

Question

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()及其docblock,这意味着diff应该归结为已删除的函数foo()以及它自己的docblock和以下空白行.

Answer 1

没有人在一段时间内解决这个问题,所以我会对它进行一次尝试.这完全是纯粹的高级理论,因为我还没有阅读关于原始耐心算法的论文.

LCS(最长公共子序列)算法都是为了减少寻找最小编辑距离解决方案所花费的时间.标准(动态编程)解决方案是O(MN),其中M是原始字符串中的符号数,N是目标字符串中的符号数.在我们的例子中,"符号"是行,"字符串"是行的集合,而不是带有字符的字符串(符号将是,例如,ASCII代码).我们只需填写"编辑成本" 的M × N矩阵; 当我们完成时,我们通过在结果矩阵中向后追踪最小路径来产生实际编辑.有关示例,请参阅https://jlordiales.me/2014/03/01/dynamic-programming-edit-distance/.(通过谷歌搜索找到的网页:这不是我有什么关系,除了现在高速扫描它是正确的.这似乎是正确的.:-))

实际上计算这个矩阵对于大文件是相当昂贵的,因为M和N是源行的数量(通常大致相等):~4k行文件在矩阵中产生~16M条目,必须在我们能够完全填充之前跟踪最小路径.而且,比较"符号"不再像比较字符那样微不足道,因为每个"符号"是一个完整的行.(通常的技巧是在矩阵生成期间散列每一行并比较散列,然后在追溯过程中重新检查,如果散列误导了我们,则将"保持不变符号"替换为"删除原始并插入新".这甚至可以正常工作在存在哈希冲突的情况下:我们可能会得到一个非常次优的编辑序列,但它实际上永远不会太糟糕.)

LCS通过观察保持长公共子序列("保留所有这些线")几乎总是导致大赢,来修改矩阵计算.找到一些好的LCS-es之后,我们将问题分解为"编辑非公共前缀,保持公共序列,并编辑非公共后缀":现在我们计算两个动态编程矩阵,但对于较小的问题,所以它走得更快 (当然,我们可以对前缀和后缀进行说明.如果我们有一个~4k行文件,我们发现~2k完全没有变化,中间靠近共线,在顶部留下~0.5k行在〜1.5k的底部,我们可以检查长的常见子序列在~0.5k"顶部有差异"线,然后再在~1.5k"底部有差异"线.)

当"常见的子序列"是微不足道的线条时,LCS表现不佳,因而导致可怕的差异,这些线条     }有很多匹配,但并不真正相关.在耐心DIFF变种简单地丢弃从最初的LCS计算这些线条,让他们不是"通用序列"的一部分.这使得剩余的矩阵更大,这就是你必须耐心的原因.:-)

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

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

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

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

任何一个的成本只是"删除5个符号".即使我们对每个符号进行加权 - 使非空行"删除"比空行"更昂贵" - 成本保持不变:我们最后删除相同的五行.

相反,我们需要的是基于"视觉聚类"对线进行加权的一些方法:边缘处的短线比中间的短线更便宜.添加到Git 2.9的压缩启发式尝试在事后执行此操作.它显然至少有一点点缺陷(只有空行计数,它们必须实际存在,而不仅仅是通过达到边缘来暗示).在矩阵填充期间进行加权可能更好(假设在执行LCS消除之后剩下的内容实际上是通过完整的动态编程矩阵).不过,这是非常重要的.

Answer 2

我发现了 Bram Cohen 的一篇新文章，其中描述了支持观察到的输出的耐心差异算法git diff：

... Patience Diff 的工作原理 -

1. 如果两者相同，则匹配它们的第一行，然后匹配第二行、第三行等，直到一对不匹配。
2. 如果两者的最后一行相同，则匹配它们的最后一行，然后匹配倒数第二行、倒数第二行等，直到一对不匹配。
3. 找到所有在两侧都只出现一次的行，然后在这些行上执行最长公共子序列，将它们匹配。
4. 对匹配线之间的每个部分执行步骤 1-2

因此，算法对独特线路的强调被步骤 1. 和 2. 破坏，步骤 1. 和 2. 检测公共前缀和后缀，即使它们是由噪声线路组成的。

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

我之前已经描述过它的顺序有点不同......

我的问题实际上重复了对布拉姆帖子的评论中表达的担忧。