有没有一种类似于diff的算法，可以处理移动的行块？

Question

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.txt 到 b.txt 的变更可以表示为“取前三行并将其移动到末尾”，但是 diff 显示了移动的文本块的完整内容两次，错过了一个非常简短地描述这个大变化的机会。请注意，diff -e 只显示一次文本块，但这是因为它不显示已删除行的内容。是否有 diff 算法的变体，既保留了 diff 表示插入和删除的能力，又能有效地表示移动文本块而无需显示其全部内容？

- Keith Thompson

---

可能可以使用另一个搜索词“语义差异算法”。 - Kimball Robinson

请参阅 https://dev59.com/cGcs5IYBdhLWcg3ww2xP 和 https://dev59.com/zXM_5IYBdhLWcg3wcCnc。 - reinierpost

在 Git 2.16 (2018年第一季度) 中，git diff --anchored=<text> 也应该被考虑。请参见我的下面的答案。 - VonC

我记得十年前从Subversion迁移到Git时，我曾经错过这个功能。所以我认为当时我使用的工具WinDiff和/或Tortoise SVN可以做到这一点。（我不确定是SVN本身提供了它，还是这些GUI工具在其上面实现了该功能。） - scipilot

Answer 1

既然您要求的是算法而不是应用程序，可以查看Walter Tichy所写的"The String-to-String Correction Problem with Block Moves"。虽然还有其他文章，但这是最早的一篇，您可以查找引用它的论文以获取更多信息。

该论文引用了Paul Heckel的文章"A technique for isolating differences between files"(在此问题的答案中提到)并谈到了它的算法：

Heckel[3]指出了LCS技术中类似的问题，并提出了一种线性时间的算法来检测块移动。如果字符串中有很少的重复符号，则该算法表现良好。但是，否则该算法会给出较差的结果。例如，对于两个字符串aabb和bbaa，Heckel的算法无法发现任何公共子字符串。

- Zoë Peterson

---

我想我本来是想问一个应用程序的，但你说得对，我确实问了一个算法。如果有人能够黑掉diff并使用它，那就太好了。 - Keith Thompson

Answer 2

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

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差异库，实现了这个算法并进行了改进。它还包括编译文本输出所需的代码，其中包括插入、删除、移动块和原始块位置插入到新的文本版本中。请参见项目页面或详细注释的代码以获取详细信息。为了测试，您还可以使用在线演示。

- Cacycle

---

这对于导致我提出这个问题的特定差异非常有效。 - Kenny Evitt

Answer 3

Git 2.16 (2018年第一季度)将引入另一种可能性，即忽略某些指定的移动行。

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

请参见提交2477ab2(2017年11月27日)，作者为Jonathan Tan (jhowtan)。
^{(由Junio C Hamano -- gitster --在提交d7c6c23中合并，2017年12月19日)}

diff: 支持锚定行

教diff一个新的算法，该算法试图防止用户指定的行出现在最终结果中作为删除或添加。
最终用户可以通过在使用Git命令（如“diff”和“show”）时指定“--anchored=<text>”一次或多次来使用它。

git diff的文档现在如下所示：

--anchored=<text>:

Generate a diff using the "anchored diff" algorithm.

This option may be specified more than once.

If a line exists in both the source and destination, exists only once, and starts with this text, this algorithm attempts to prevent it from appearing as a deletion or addition in the output.
It uses the "patience diff" algorithm internally.

See the tests for some examples:

pre post
 a   c
 b   a
 c   b

normally, c is moved to produce the smallest diff.

但是：

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

Diff将会是a。

---

在Git 2.33（2021年第三季度）中，命令行完成（位于contrib/目录下）学会了 "git diff"^(man) 命令使用 --anchored 选项。

请参见 提交记录 d1e7c2c（2021年5月30日），作者是 Thomas Braun (t-b)。
^{（由Junio C Hamano -- gitster --于2021年7月8日合并至提交记录 3a7d26b）}

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

^{签名作者：Thomas Braun}

这个标志是在2477ab2中引入的（“diff:支持锚定行”，2017年11月27日，Git v2.16.0-rc0 - 合并列在批次＃10中），但当时bash完成脚本不知道这个新标志。
请添加它。

- VonC

Answer 4

这里是一个可能有效的草图。为了清晰起见，暂时忽略差异插入/删除。

这似乎是围绕着寻找最佳阻塞进行的，类似于文本压缩。我们想要找到两个文件的公共子字符串。一种选择是构建广义后缀树，并迭代地获取最大的公共子串，然后将其删除并重复，直到没有某个尺寸的子字符串。这可以在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算法，省略所有在原始diff输出中不会出现的文本，然后再运行上述算法。

- dfb

---

我们的智能差异分析器使用后缀树来查找代码的最大公共段，包括已移动的代码。 - Ira Baxter

所以这只是程序应该做什么的概述，但还没有解决方案，对吗？ - xeruf

Answer 5

SemanticMerge 是一款“语义 scm”工具，这篇评论中提到了它可以处理移动一个代码块（对于支持的编程语言）的“语义差异”。我没有找到其算法的详细信息，但是可能差异算法本身并不特别有趣，因为它依赖于编程语言源代码文件的单独解析输出。以下是SemanticMerge实现（外部）语言解析器的文档，这可能会揭示一些关于其差异的工作原理：

• 外部解析器 - SemanticMerge

我刚刚测试了它，它的差异非常好。它比我使用此答案中提到的算法演示产生的差异要显着得多（那个差异本身就比Git的默认差异算法产生的要好得多），而且我怀疑它仍然比此答案中提到的算法产生的差异更好。

- Kenny Evitt

---

需要繁琐的注册 :c - xeruf

Answer 6

我们的智能差异工具在计算同一编程语言两个程序源文本之间的差异时，正是如此。差异以程序结构（标识符、表达式、语句、块）准确到行/列号和可行编辑操作（删除、插入、移动、复制 [超出OP仅请求"复制"的要求]、重命名块中的标识符）的形式报告。

智能差异分析器需要一个结构化的构件（例如编程语言），因此它无法用于任意文本。(我们可以将结构定义为“只是文本行”，但认为与标准差异相比，这并不特别有价值)。

- Ira Baxter

---

我最近也发现了另一个工具，语义SCM，在http://blog.bartdemeyer.be/2013/04/new-merge-tool-semanticmerge-tested-on-svn/上。 - Kimball Robinson

看起来不错，但是获取一份副本对我来说太痛苦了，甚至都不想尝试... - xeruf

@xeruf：评估版本可以简单下载。 - Ira Baxter

不好意思，我必须先填写一个烦人的旧表格。 - xeruf

@xeruf：大部分都是可选的。你的兴趣可能不是很大。 - Ira Baxter

Answer 7

请注意此在线工具simtexter，基于SIM_TEXT算法。它看起来是最好的。

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

- Revious

---

C源代码以zip文件形式提供，可在此网页链接中下载sim_3_0_2.zip。 - Keith Thompson

我尝试在我的系统（Ubuntu 18.04）上构建和安装它，但遇到了一些问题 - 编译器警告，Makefile 中的拼写错误。看起来它是专门针对源代码（C或其他语言）的。 - Keith Thompson

@KeithThompson：你有尝试使用JS移植版吗？https://people.f4.htw-berlin.de/~weberwu/simtexter/assets/js/app.min.js - Revious

注意：我跟踪了网络日志，似乎没有进行任何网络请求，一切都是在设备上使用 JS 处理的。 - xeruf

Answer 8

在我日常编码中遇到这种情况时，当我真正将一整块代码移动到源代码的另一个位置时，因为它在逻辑上更合理或更易读，我所做的是：

- 清除所有现有的差异并提交它们，以便文件只需要我们寻找的移动操作 - 从源代码中删除整个代码块 - 保存文件 - 并暂存该更改 - 将代码添加到新位置 - 保存文件 - 并暂存该更改 - 将两个暂存的补丁作为一个提交，并使用合理的消息进行提交

- Jay Day Zee

---

这听起来很有趣，但我还没有看到它的好处。用这种方式是否可以创建更易读的不同差异？ - Rob Bednark

基本上，你似乎将移动操作与源代码控制历史中的其他更改隔离开来 - 这是一个好主意。 - Kenny Evitt