是否有类似diff的algorithm来处理移动块的行？
diff程序在其各种版本中相当擅长计算两个文本文件之间的差异，并且比显示两个文件都更加紧凑。 它显示了作为一系列插入和删除行（或在某些情况下更改的行，但相当于删除，然后插入）的序列的区别。 patch和源代码控制系统使用相同或非常相似的程序或algorithm来最小化表示同一文件的两个版本之间的差异所需的存储。 algorithm在这里和这里讨论。
但是当文件在文件内被移动时，它会下降。
假设你有以下两个文件， 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仅显示一次文本块，但这是因为它不显示已删除行的内容。
是否有diffalgorithm的变体（a）保留diff表示插入和删除的能力，（b）有效地表示移动的文本块而不必显示其全部内容？
既然你问了一个algorithm，而不是一个应用程序，请看Walter Tichy的“带有块移动的string到string校正问题” 。 还有其他的，但这是原来的，所以你可以找引用它来find更多的文件。
这篇论文引用了Paul Heckel的论文“隔离文件之间差异的技术”（在这个问题的答案中提到），并提到了它的algorithm：
Heckel [3]指出了与LCS技术相似的问题，并提出了线性灰度algorithm来检测块移动。 如果string中没有重复的符号，则该algorithm可以充分执行。 但是，algorithm给出的结果很差，否则。 例如，给定两个stringaabb和bbaa ，Heckel的algorithm无法发现任何常见的子string。
以下方法可以检测块移动：
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差异库，它实现了这个algorithm并对其进行了改进。 它还包括编译文本输出的代码，插入，删除，移动的块和插入到新的文本版本中的原始块位置。 有关详细信息，请参阅项目页面或广泛注释的代码。 为了testing，你也可以使用在线演示 。
下面是一些可能起作用的草图。 为了清楚起见，暂时忽略差异插入/删除。
这似乎是找出最好的阻塞，类似于文本压缩。 我们想find两个文件的公共子string。 一种select是build立一个通用的后缀树，迭代地取最大的公共子string，删除它并重复，直到没有一些大小为$ s $的子string。 这可以在O（N ^ 2）时间（ https://en.wikipedia.org/wiki/Longest_common_substring_problem#Suffix_tree ）中使用后缀树来完成。 贪婪的最大似乎是最佳的（作为压缩字符的函数），因为从其他子string中获取字符序列意味着在别处添加相同数量的字符。
然后，每个子string将被该块的符号replace，并作为一种“字典”显示一次。
$ diff a.txt b.txt 1,3d0 < $ 6a4,6 > $ $ = 1,2,3
现在我们必须重新引入差异化的行为。 简单的（可能是非最优的）答案是首先简单地运行diffalgorithm，省略原始diff中不会输出的所有文本，然后运行上述algorithm。
我们的智能差分工具在计算两种程序的源文本在相同的编程语言中的差异时完成这个工作。 差异是根据对行/列号精确的程序结构（标识符，expression式，语句，块）和合理的编辑操作（删除，插入，移动，复制[超出OP对单纯“复制” ]，重命名块标识符）。
SmartDifferencers需要一个结构化的工件（例如，一种编程语言），所以它不能对任意文本执行此操作。 （我们可以将结构定义为“只是文本行”，但是与标准差异相比，并不认为这是特别有价值的）。
SemanticMerge是这个评论中提到的“语义scm”工具，其中包括一个“语义差异”（semantic diff），用于处理移动一行代码块（用于支持的编程语言）。 我还没有find关于该algorithm的任何细节，但可能diffalgorithm本身并不特别有趣，因为它依赖于单独parsing编程语言源代码文件本身的输出。 这里是SemanticMerge关于实现（外部）语言parsing器的文档，这可能会揭示它的差异如何工作：
- 外部parsing器 – SemanticMerge
我刚才testing了它，它的差异太棒了 。 这比我在这个答案中提到的algorithm的演示所产生的要好得多（并且diff本身比Git的默认diffalgorithm所产生的要好得多），而且我怀疑还是比algorithm可能产生的更好在这个答案中提到。
