有没有人知道或者知道C#中的二进制补丁生成算法实现？
基本上,比较两个文件(指定旧的和新的),并生成一个补丁文件,可用于升级旧文件以具有与新文件相同的内容.
实现必须相对较快,并使用大文件.它应该表现出O(n)或O(logn)运行时.
我自己的算法往往是糟糕的(快速但产生巨大的补丁)或缓慢(产生小补丁但具有O(n ^ 2)运行时).
任何建议或实施指针都会很好.
具体来说,该实现将用于使我们拥有一台主服务器的各种大型数据文件保持服务器同步.当主服务器数据文件发生更改时,我们还需要更新多个异地服务器.
我所做的最天真的算法,仅适用于可以保存在内存中的文件,如下所示:
这有点像压缩,没有窗口,所以它会占用大量内存.然而,它是相当快的,并且产生非常小的补丁,只要我尝试使代码输出最小.
更节省内存的算法使用窗口,但会产生更大的补丁文件.
我在本文中跳过了上述算法的细微差别,但如果有必要,我可以发布更多细节.但是,我确实觉得我需要一个不同的算法,所以改进上述算法可能不会让我足够远.
编辑#1:以下是对上述算法的更详细描述.
首先,组合这两个文件,这样你就有了一个大文件.记住两个文件之间的切点.
其次,这样做可以抓取4个字节并将其位置添加到整个文件中的所有内容的字典步骤中.
第三,从新文件开始的地方开始,尝试定位4字节的现有组合,并找到最长匹配.确保我们只考虑旧文件中的位置,或者来自新文件中较早的位置.这确保了我们可以在补丁应用期间重用旧文件和新文件中的材料.
编辑#2:上述算法的源代码
您可能会收到有关证书存在问题的警告.我不知道如何解决这个问题,因此暂时只接受证书.
源使用了我库中其余部分的许多其他类型,因此文件不是全部,但这就是算法实现.
@lomaxx,我试图为subversion中使用的算法找到一个很好的文档,叫做xdelta,但除非你已经知道算法是如何工作的,否则我发现的文件无法告诉我需要知道什么.
或者也许我只是密集...... :)
我快速浏览了你所提供的网站上的算法,遗憾的是它无法使用.二进制diff文件中的注释说:
找到一组最佳差异需要相对于输入大小的二次时间,因此它很快就会变得无法使用.
我的需求并不是最优的,所以我正在寻找更实用的解决方案.
谢谢你的答案,如果我需要它们,他会为他的工具添加一个书签.
编辑#1:注意,我会查看他的代码,看看我是否能找到一些想法,稍后我还会给他发一封电子邮件,但我已经阅读了他所引用的那本书,虽然解决方案适用于找到最佳解决方案,由于时间要求,它在使用中是不切实际的.
编辑#2:我肯定会追捕python xdelta实现.