问题

有没有人在C#中实现或知道二进制补丁生成算法?

基本上,比较两个文件(指定的旧文件和新文件),并生成一个补丁文件,可用于升级旧文件,使其与新文件具有相同的内容。

实现必须比较快,并且使用大文件.它应该显示O(n)或O(logn)运行时间.

我自己的算法往往很糟糕(快但产生大量补丁)或慢(生成小补丁但有O(n^ 2)运行时).

任何建议或实现指针都会很好.

具体来说,实现将用于为我们有一个主服务器的各种大型数据文件保持服务器的同步.当主服务器数据文件发生变化时,我们也需要更新几个非站点服务器.

我制作的最天真的算法只适用于可以保存在内存中的文件,如下所示:

  1. 从旧文件中抓取前四个字节,调用键
  2. 将这些字节添加到字典中,其中键 – >位置,其位置是我抓住这4个字节的位置,从0开始
  3. 跳过这四个字节中的第一个,抓取另外4个字节(3个重叠,1个),并以相同的方式添加到字典中
  4. 对旧文件中的所有4字节块重复步骤1-3
  5. 从新文件的开始,抓住4个字节,并尝试在字典中查找它
  6. 如果找到,通过比较两个文件中的字节,找到最长的匹配数
  7. 在旧文件中编码对该位置的引用,并跳过新文件中匹配块
  8. 如果没有找到,从新文件中编码1字节,并跳过它
  9. 为新文件的其余部分重复步骤5-8

这有点像压缩,没有窗口,所以它会使用很多内存.但是,它相当快,只要我尝试使代码输出最小,就会生成相当小的补丁.

一个更有记忆效率的算法使用窗口,但会产生更大的补丁文件。

上面的算法有更多微妙之处,我在this post中跳过,但如果需要,我可以发布更多细节.但是,我确实认为我需要一个完全不同的算法,因此上面的算法改进可能不足以让我得到太多.


编辑#1:这是对上述算法的更详细描述.

首先,组合两个文件,以便有一个大文件。记住两个文件之间的切点。

其次,这样做会抓住4个字节,并将它们的位置添加到字典步骤中的所有内容在整个文件中。

第三,从新文件开始的位置,执行循环,尝试找到现有的4字节组合,并找到最长的匹配.确保我们只考虑旧文件中的位置,或者比我们目前更早的新文件中的位置.这确保我们可以在补丁应用程序中重用旧文件和新文件中的材料.


编辑#2:上述算法的源代码

您可能会收到关于证书有一些问题的警告.我不知道如何解决这个问题,所以目前只是接受证书.

源代码从我的其他库中使用了很多其他类型,以便文件不是所有需要的,但这是算法实现.


@lomaxx,我试图为subversion中使用的算法找到一个很好的文档,称为xdelta,但除非你已经知道算法是如何工作的,我发现的文档无法告诉我我需要知道什么.

或者也许我只是很密集...:)

我从你给出的网站上快速了解了算法,不幸的是它不可用.来自二进制diff文件的评论说:

找到一组最优的差异需要相对于输入大小的二次时间,因此它很快就无法使用。

我的需求不是最佳的,所以我正在寻找更实际的解决方案.

但是感谢回答,如果我需要他的实用程序,我会添加一个书签.

编辑#1:注意,我将查看他的代码,看看我是否可以找到一些想法,我稍后还会发送一封带有问题的电子邮件,但我已经阅读了他引用的书,虽然解决方案有助于找到最佳解决方案,但由于时间需求,它不切实际.

编辑#2:我肯定会捕获python xdelta实现.

  最佳答案

对不起,我无法提供更多的帮助.我将确定地继续查看xdelta,因为我已经使用它多次在我们生成的600MB ISO文件上生成质量衍射,用于分发我们的产品并且它执行得很好.

  相同标签的其他问题

c#filepatch