algorithm - 差异化更快

Question

我正在研究比较大的二进制文件。我已经实现了著名的 Myers Diff 算法，它产生了最小的差异。但是，它是 O(ND)，因此要区分两个截然不同的 1 MB 文件，我预计需要 100 万平方 = 1 万亿的时间。那可不好!

我想要的是一种算法，它可以产生潜在的非最小差异，但速度要快得多。我知道必须存在一个，因为 Beyond Compare 做到了。但是我不知道怎么办!

可以肯定的是:有 xdelta 或 bdiff 之类的工具，但它们会生成供计算机使用的补丁，这与人类可使用的差异不同。补丁涉及将一个文件转换为另一个文件，因此它可以执行诸如从文件的先前部分复制之类的操作。那里有一个人类可消费的差异，可以直观地显示差异，并且只能插入和删除。例如，这个转换:

"puddi"-> "puddipuddipuddi"

会产生“将 [0,4] 复制到 [5,9] 和 [10, 14]”的小补丁，但会产生“附加‘puddipuddi’”的较大差异。我对产生更大差异的算法很感兴趣。

谢谢!

Answer 1

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

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

只要没有太多差异，这往往会给出一组非常好的(尽管不能保证最佳)对齐区域(或等效地，一组非常小的差异)。我不确定每个步骤的确切时间范围，但我知道没有 n^2 或更高的项。

我相信 MUMmer 程序需要 DNA 或蛋白质序列，因此它可能无法为您开箱即用，但这些概念肯定适用于一般字符串(例如文件)，因此如果您准备自己重新实现它，我会推荐这种方法。