OpenBSD 上的实现diff
有一个非标准-d
选项,包含以下文档:
-d
努力产生尽可能小的差异。在处理包含许多更改的大文件时,这可能会消耗大量处理能力和内存。
GNUdiff
实现具有相同的选项,但文档较短
-d
,--minimal
努力寻找较小的一组更改
有时,我使用此选项只是为了看看它是否生成diff
与没有该选项的同一命令不同的任何形状或形式的输出,但我已经绝不看到任何差异(没有双关语意图)。
有人可以提供或指出一个示例,其中此选项实际上会从相同的命令产生不同的结果,而不需要-d
?或者,如果有人可以解释此选项启动所需的情况。我也不确定“最小”是否意味着“更少的输出行”或“更少的大块头”。
一个未经证实的猜测是,这与非常大的帅哥有关。
答案1
在 GNU diff
(也用于 FreeBSD)中,该--minimal
标志触发了 Paul Eggert 的算法变体,导致它“将成本限制在O(N**1.5 log N)
为具有差异的大输入生成次优输出的价格”。更具体地说,它导致不是应用几种启发式方法来仅仅寻找关闭寻找最佳解决方案并丢弃“令人困惑的”线条作为额外的差异。
在 OpenBSD 中diff
,它使用 20 世纪 70 年代较旧的 Unixdiff
算法,所采用的算法归功于 Harold Stone,并且旗帜--minimal
触发一个搜索,该搜索(实际上是非)受无符号整数的最大值限制,而不是受比较行范围大小的平方根(如果更大,则为 256)。
进一步阅读
- 尤金·W·迈尔斯(Eugene W. Myers,1986 年 11 月)。 ”O(ND) 差分算法及其变体”。算法。第 1 卷。第 1-4 期。第 251–266 页。 DOI10.1007/BF01840446。
- JW 亨特和 MD 麦克罗伊(1976 年 6 月)。 ”一种差异文件比较算法”。报告 41。计算科学。贝尔实验室。
- 理查德·哈特曼(1988-01-13)。 Unix diff(1) 算法。 [电子邮件受保护]。 comp.unix.问题。
- https://github.com/openbsd/src/blob/d1e24f318523607c98dc6fbe5a06a5d9e5c87293/usr.bin/diff/diffreg.c#L93
- https://github.com/freebsd/freebsd/blob/40ec4fdc9a74bfdb83f13672acdb88af5c91ab46/contrib/diff/src/analyze.c#L23
- 全面回顾 diff 算法、其历史和实现