变得更快

Question

我正在研究大型二进制文件.我已经实现了着名的Myers Diff算法,它可以产生最小的差异.但是,它是O(ND),所以为了区分两个非常不同的1 MB文件,我预计需要100万平方= 1万亿.这不好!

我想要的是一种产生潜在非最小差异的算法,但速度要快得多.我知道必须存在,因为Beyond Compare会这样做.但我不知道怎么做!

可以肯定的是:有像xdelta或bdiff这样的工具,但这些工具会产生一个用于计算机消耗的补丁,这与人类消耗差异不同.补丁涉及将一个文件转换为另一个文件,因此它可以执行诸如从文件的先前部分进行复制之类的操作.人类消耗品差异在那里可视地显示差异,并且只能插入和删除.例如,这个转换:

"puddi" - >"puddipuddipuddi"

会产生一小部分"复制[0,4]到[5,9]和[10,14]",但更大的差异是"追加'puddipuddi'".我对产生更大差异的算法感兴趣.

谢谢!

Answer 1

Diffing 基本上与生物信息学中用于对齐 DNA 序列的算法相同。这些序列通常很大（数百万或数十亿个核苷酸长），MUMmer程序使用了一种在较长基因组上运行良好的策略：

1. 使用后缀树快速找到所有最大唯一匹配项（出现在两个文件中并且在该条件仍然成立的情况下不能在任一方向扩展的子字符串）
2. 使用最长递增子序列动态规划算法快速找到在两个文件中以连续顺序出现的最长 MUM 子集
3. 在对齐中修复这个 MUM 子集（即将这些区域标记为匹配）
4. 如果认为有必要，在 MUM 间区域执行较慢的（例如 Myers）差异。在您的情况下，如果您发现最长 MUM 的长度低于某个阈值（您将其视为 2 个文件不相关的证据），则您可能会完全省略此步骤。

每当没有太多差异时，这往往会提供一组非常好的（虽然不能保证最佳）对齐区域（或等效地，一组非常小的差异）。我不确定每个步骤的确切时间范围，但我知道没有n^2或更高的条款。

我相信 MUMmer 程序需要 DNA 或蛋白质序列，所以它可能不适合你，但这些概念肯定适用于一般字符串（例如文件），所以如果你准备自己重新实现它，我会推荐这种方法.