算法 – 更快地扩散

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

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

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

“puddi” – > “puddipuddipuddi”

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

谢谢!

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

>使用后缀树快速查找所有极大唯一匹配(出现在两个文件中的子字符串,并且在该条件仍然保持的情况下无法在任一方向上扩展)
>使用增长最长的子序列动态编程算法快速找到两个文件中以连续顺序出现的最长MUM子集
>修复MUM的这个子集在对齐中(即将这些区域标记为匹配)
>如果认为有必要,在MUM间区域执行较慢(例如Myers).在您的情况下,如果您发现最长MUM的长度低于某个阈值(您可能认为这两个文件不相关的证据),您可能会完全省略此步骤.

只要不存在太多差异,这往往会给出非常好的(尽管不是保证最优的)一组对齐区域(或等效地,一组非常小的差异).我不确定每一步的确切时间限制,但我知道没有n ^ 2或更高的术语.

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

相关文章
相关标签/搜索