更快加速

Question

我正在研究区分较大的二进制文件。我已经实现了着名的Myers Diff算法，它产生了一个最小差异。然而，它是O（ND），所以要区分两个非常不同的1 MB文件，我预计需要100万平方= 1万亿的时间。这不好！

我想要的是一种算法，可以产生一个潜在的非最小差异，但速度更快。我知道一个人必须存在，因为Beyond Compare会这样做。但我不知道如何！

可以肯定的是：有些工具如xdelta或bdiff，但是这些工具会生成一个用于计算机消耗的补丁，这与人类可消耗的diff不同。补丁涉及将一个文件转换为另一个文件，因此它可以执行诸如从文件的以前部分进行复制的操作。一个人类可消费的差异是在视觉上显示差异，并且只能插入和删除。例如，该变换：

“puddi” - > “puddipuddipuddi”

将产生一小片 “拷贝[0,4]到[5,9]和[10，14]”，但更大的差异“追加'puddipuddi'”。我对产生更大差异的算法感兴趣。

谢谢！

Answer 1

Diffining与生物信息学中用于比对DNA序列的算法基本相同。这些序列往往很大（百万甚至上亿个核苷酸长的），和一个策略，有行之有效的长基因组所使用的程序MUMmer：

1. 迅速找到所有最大独特的匹配出现在（子两个文件并且不能在该条件下沿任一方向扩展仍然保持）使用后缀树
2. 快速找到使用最长增加的子序列动态编程算法在两个文件中以连续顺序出现的MUM的最长子集
3. 修正MUM中的这个子集（即标记那些区块作为匹配）
4. 如果认为有必要，执行较慢（例如，迈尔斯）在MUM区域之间进行区分。在你的情况下，如果你发现最长的MUM的长度低于某个阈值（你会认为这两个文件无关），那么你可能会完全忽略这一步。

只要没有太多差异，这往往会给出一个非常好的（虽然不是保证最佳的）对齐区域集合（或等价地，一组非常小的差异）。我不确定每一步的确切时间范围，但我知道没有n^2或更高的条件。我相信MUMMER程序需要DNA或蛋白质序列，所以它可能不适合你，但这些概念当然适用于一般字符串（如文件），所以如果你准备自己重新实现它，会推荐这种方法。

Answer 2

从性能的角度来看，随着文件大小的增加，GNU Diffutils可能是最稳健的选择。对于你的情况，我可能会使用它的side-by-side comparison format，这可能是该地段最友善的人群。否则，你不得不以另一种格式输出它的输出，并且做一些工作来使它更漂亮。

一个好的竞争者，其表现一直在稳步提高，包括众多的加速，diff-match-patch。它以几种不同的语言实现了Myers Diff算法，包括Java和JavaScript。请看online demo，以获得漂亮的打印结果。如果你想做线差异研究wiki的技巧，如何使用它的目的。