是否有类似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.txtto 更改b.txt可以表示为"取前三行并将它们移动到最后",但是diff显示移动的行块的完整内容两次,错过了非常简短地描述这个大变化的机会.

请注意,diff -e仅显示一次文本块,但这是因为它不显示已删除行的内容.

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

Answer 1

由于您要求的是算法而不是应用程序,请查看Walter Tichy撰写的"块移动的字符串到字符串校正问题".还有其他的,但这是原始的,所以你可以寻找引用它来找到更多的论文.

本文引用了Paul Heckel的论文"一种隔离文件之间差异的技术"(在这个问题的答案中提到),并提到了它的算法:

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

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 diff库,它实现了这个算法并对其进行了改进.它还包括用于编译文本输出的代码,其中插入,删除,移动块和插入到新文本版本中的原始块位置.有关详细信息,请参阅项目页面或广泛注释的代码.对于测试,您还可以使用在线演示.

Answer 3

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

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

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

diff: 支撑锚固线

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

现在的文档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 年第 3 季度）中，命令行补全 (in contrib/) 了解到 " git diff" ^{( man )}接受该--anchored选项。

请参阅Thomas Braun ( ) 的commit d1e7c2c（2021 年 5 月 30 日）。^{（由Junio C Hamano合并-- --在commit 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 完成脚本没有了解新旗帜。
添加它。

Answer 4

这是一些可行的草图。为了清楚起见，暂时忽略diff插入/删除。

这似乎包括找出最佳阻塞，类似于文本压缩。我们想要找到两个文件的公共子字符串。一种选择是构建一个通用后缀树，并迭代地获取最大的公共子字符串，将其删除并重复直到没有某个大小为$ 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算法，忽略所有不会在原始diff中输出的文本，然后运行上述算法。