56

该diff程序在其各种化身中相当擅长计算两个文本文件之间的差异，并且比完整地显示两个文件更紧凑地表达它。它将差异显示为一系列插入和删除的行块（或在某些情况下更改的行，但这相当于删除后插入）。源代码控制系统使用相同或非常相似的程序或算法patch来最小化表示同一文件的两个版本之间的差异所需的存储空间。该算法在此处和此处进行了讨论。

但是当文本块在文件中移动时它会下降。

假设您有以下两个文件，a.txt并且b.txt（想象它们都有数百行而不是只有 6 行）：

a.txt   b.txt
-----   -----
1       4
2       5
3       6
4       1
5       2
6       3

diff a.txt b.txt显示了这一点：

$ diff a.txt b.txt 
1,3d0
< 1
< 2
< 3
6a4,6
> 1
> 2
> 3

从a.txtto的变化b.txt可以表示为“将前三行移到最后”，但是diff两次显示了移动的行块的完整内容，错过了非常简要地描述这个大变化的机会。

请注意，diff -e该文本块仅显示一次，但那是因为它不显示已删除行的内容。

算法的变体是否diff（a）保留diff了表示插入和删除的能力，以及（b）有效地表示移动的文本块而不必显示其全部内容？

4

8 回答 8

24

由于您要求的是算法而不是应用程序，请查看 Walter Tichy 的“The String-to-String Correction Problem with Block Moves”。还有其他的，但那是原始的，因此您可以查找引用它的论文以找到更多信息。

该论文引用了 Paul Heckel 的论文“一种用于隔离文件之间差异的技术”（在这个问题的答案中提到），并提到了它的算法：

Heckel[3] 指出了 LCS 技术的类似问题，并提出了一种线性石灰算法来检测块移动。如果字符串中的重复符号很少，则该算法可以充分执行。但是，否则该算法给出的结果很差。例如，给定两个字符串aabb和bbaa，Heckel 算法无法发现任何公共子字符串。

于 2012-04-09T15:11:29.753 回答
12

以下方法能够检测块移动：

Paul Heckel：一种隔离文件之间差异的技术
ACM 通信 21(4):264 (1978)
http://doi.acm.org/10.1145/359460.359467（访问受限）
镜像：http://documents.scribd。 com/docs/10ro9oowpo1h81pgh1as.pdf（开放获取）

wikEd diff是一个免费的 JavaScript diff 库，它实现了这个算法并对其进行了改进。它还包括编译文本输出的代码，其中插入、删除、移动块和插入新文本版本的原始块位置。有关详细信息，请参阅项目页面或广泛注释的代码。对于测试，您也可以使用在线演示。

于 2014-09-26T10:03:49.793 回答
8

Git 2.16（2018 年第一季度）将通过忽略一些指定的移动行来引入另一种可能性。

" git diff" 学习了 " --patience" 算法的变体，用户可以指定将哪条“唯一”线用作锚点。

请参阅Jonathan Tan ( )的提交 2477ab2（2017 年 11 月 27 日） 。（由Junio C Hamano 合并 -- --在d7c6c23 提交中，2017 年 12 月 19 日）jhowtan
gitster

diff: 支持锚定线

教授diff一种新算法，该算法试图防止用户指定的行在最终结果中显示为删除或添加。
最终用户可以在使用诸如“ ”和“ ”之--anchored=<text>类的 Git 命令时通过指定“ ”一次或多次来使用它。diffshow

现在的文档git diff内容如下：

--anchored=<text>:

使用“锚定差异”算法生成差异。

可以多次指定此选项。

如果一行在源和目标中都存在，只存在一次，并且以此文本开头，则此算法会尝试防止它在输出中显示为删除或添加。
它在内部使用“耐心差异”算法。

请参阅测试以获取一些示例：

pre post
 a   c
 b   a
 c   b

通常，c移动以产生最小的差异。

但：

 git diff --no-index --anchored=c pre post

差异将是a.

在 Git 2.33（2021 年第三季度）中，命令行补全（in contrib/）获悉“ git diff” （man）采用该--anchored选项。

请参阅Thomas Braun ( ) 的提交 d1e7c2c（2021 年 5 月 30 日）。（由Junio C Hamano 合并——在提交 3a7d26b中，2021 年 7 月 8 日）t-b
gitster

completion: 将 --anchored 添加到 diff 的选项中

签字人：Thomas Braun

这个标志是在2477ab2 (" diff: support anchoring line(s)", 2017-11-27, Git v2.16.0-rc0 -- merge列在第 10 批中) 但当时，bash 完成脚本没有了解新标志。
添加它。

于 2017-12-20T21:45:22.583 回答
5

这是可能有用的东西的草图。为了清楚起见，暂时忽略差异插入/删除。

这似乎包括找出最佳阻塞，类似于文本压缩。我们想找到两个文件的公共子字符串。一种选择是构建一个通用后缀树并迭代地获取最大公共子串，将其删除并重复，直到没有某个大小 $s$ 的子串。这可以在 O(N^2) 时间内使用后缀树来完成（https://en.wikipedia.org/wiki/Longest_common_substring_problem#Suffix_tree）。贪婪地取最大值似乎是最优的（作为压缩字符的函数），因为从其他子字符串中获取字符序列意味着在其他地方添加相同数量的字符。

然后，每个子字符串将被该块的符号替换，并作为一种“字典”显示一次。

$ diff a.txt b.txt 
1,3d0
< $
6a4,6
> $

 $ = 1,2,3

现在我们必须重新引入类似差异的行为。简单（可能不是最佳）的答案是首先简单地运行 diff 算法，省略所有不会在原始 diff 中输出的文本并运行上述算法。

于 2012-04-09T00:21:55.307 回答
4

当使用相同的编程语言计算两个程序的源文本之间的差异时，我们的Smart Differencer工具正是这样做的。在精确到行/列号的程序结构（标识符、表达式、语句、块）和合理的编辑操作（删除、插入、移动、复制[在 OP 对单纯“复制”的要求之上和之外）”方面报告了差异]，重命名块中的标识符）。

SmartDifferencers 需要结构化的工件（例如，编程语言），因此它不能对任意文本执行此操作。（我们可以将结构定义为“只是文本行”，但与标准差异相比，我们认为这不会特别有价值）。

于 2012-04-08T23:26:26.847 回答
4

SemanticMerge是本评论中提到的其他答案之一的“语义 scm”工具，包括一个“语义差异”，用于处理移动一行行（对于支持的编程语言）。我还没有找到有关该算法的任何详细信息，但 diff 算法本身可能并不是特别有趣，因为它依赖于对编程语言源代码文件本身进行单独解析的输出。这是 SemanticMerge 关于实现（外部）语言解析器的文档，它可能会阐明其差异的工作原理：

我刚才测试了它，它的差异很棒。它比我使用这个答案中提到的算法演示生成的要好得多（而且 diff 本身比 Git 的默认 diff 算法生成的要好得多），我怀疑仍然比算法可能生成的要好在这个答案中提到。

于 2017-01-12T18:04:13.750 回答
2

对于我在现实生活中编码的这种情况，当我实际上将整个代码块移动到源代码中的另一个位置时，因为它在逻辑上或可读性上更有意义，我所做的是：

  • 清理所有现有的差异并提交它们
    • 这样文件只需要我们正在寻找的移动
  • 从源代码中删除整个代码块
    • 保存文件
    • 和阶段改变
  • 将代码添加到新位置
    • 保存文件
    • 和阶段改变
  • 将两个分阶段的补丁作为一个提交提交，并带有合理的消息
于 2018-03-07T14:56:48.987 回答
1

还要检查这个基于SIM_TEXT算法的在线工具simtexter 。这似乎是最好的。

您还可以查看 Javascript 实现或 C/Java 的源代码。

在此处输入图像描述

于 2020-04-10T18:32:43.703 回答