标准(Myers)算法、最小化算法、耐心算法和直方图差异算法产生不同结果的示例

Question

Git提供了这4种差异算法，但没有进一步的信息来说明它们之间的区别。

每种算法的优点是什么？是否有各种情况下算法表现不同的比较？

- Petr

Answer 1

我认为有多个算法被支持，因为在所有情况下没有一个算法是最好的选择。

差异在于修补程序输出的易读性和生成修补程序所需的处理时间。

总的来说，这就是我理解的区别：

• Myers：原始算法在xdiff中实现 (http://www.xmailserver.org/xdiff-lib.html 和 http://www.xmailserver.org/diff2.pdf)，优化更改行的“编辑距离”。
• Minimal：Myers加上尝试使修补程序大小最小化。
• Patience：试图在修补程序的易读性与修补程序大小和处理时间之间进行权衡。有关说明，请参见什么是 `git diff --patience`？和http://bramcohen.livejournal.com/73318.html或http://alfedenzo.livejournal.com/170301.html。
• Histogram：主要是为了速度而创建的。比Myers和Patience更快，最初是在jgit中开发的 (http://eclipse.org/jgit/)

这里是Myers、Patience和Histogram速度的比较: http://marc.info/?l=git&m=133103975225142&w=2

这里是直方图与迈尔斯算法的diff输出对比: http://marc.info/?l=git&m=138023003519837&w=2

- jelle foks

---

Myers算法不是原始算法。原始的差异算法来自Douglas McIlroy，于1974年，他也是管道的发明者。 - schily

@schily 这就是为什么它说“原始算法在xdiff中实现”，而不是原始的diff可执行文件。在Git开始使用自己的版本的xdiff时，为了避免分叉diff的开销，xdiff的算法是由Myers进行了大量修改，并被称为Myers'算法。 - underscore_d

Answer 2

尽管只比较了Myers和Histogram两种算法，但这可能会有所帮助。Nugroho等人的研究揭示了这两种diff算法之间的差异程度。该研究进行了3次比较，即指标、SZZ算法和补丁。从指标和SZZ的比较中，我们可以看到Myers和Histogram在识别不同代码更改数量方面存在很大差异。虽然这些diff都没有错误地描述变化，但从手动补丁的比较中，Histogram算法提供了一个更好地描述人类变更意图的合理diff输出。

- YusufUMS