C#中的二进制补丁生成

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

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

实现必须相对较快,并使用大文件。 它应该表现出O(n)或O(logn)运行时。

我自己的算法往往是糟糕的(快速但产生巨大的补丁)或缓慢(产生小补丁但具有O(n ^ 2)运行时)。

任何建议或实施指针都会很好。

具体来说,该实现将用于使我们拥有一个主服务器的各种大型数据文件保持服务器同步。 当主服务器数据文件发生更改时,我们还需要更新多个场外服务器。

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

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

这有点像压缩,没有窗口,因此会占用大量内存。 然而,它是相当快的,并且产生非常小的补丁,只要我尝试使代码输出最小。

更节省内存的算法使用窗口,但会产生更大的补丁文件。

我在本文中跳过了上述算法的细微差别,但如果有必要,我可以发布更多详细信息。 但是,我觉得我需要一个完全不同的算法,因此改进上述算法可能不会让我足够远。


编辑#1 :以下是对上述算法的更详细描述。

首先,组合这两个文件,这样你就有了一个大文件。 记住两个文件之间的切点。

其次,这样做可以获取4个字节并将其位置添加到整个文件中的所有内容的字典步骤中。

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


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

您可能会收到有关证书存在问题的警告。 我不知道如何解决这个问题,因此暂时接受证书。

源使用了我库中其余部分的许多其他类型,因此文件不是全部​​,但这就是算法实现。


@lomaxx,我试图为subversion中使用的算法找到一个很好的文档,叫做xdelta,但除非你已经知道算法是如何工作的,否则我发现的文件无法告诉我需要知道的内容。

或者也许我只是密集…… 🙂

我快速浏览了你所提供的网站上的算法,遗憾的是它无法使用。 二进制diff文件中的注释说:

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

我的需求并不是最优的,所以我正在寻找更实用的解决方案。

谢谢你的回答,如果我需要它,他会为他的工具添加一个书签。

编辑#1 :注意,我会查看他的代码,看看我是否能找到一些想法,稍后我还会给他发一封电子邮件,但是我已经阅读了他引用的那本书,虽然解决方案对于找到最佳解决方案,由于时间要求,它在使用中是不切实际的。

编辑#2 :我肯定会追捕python xdelta实现。

对不起,我无法提供更多帮助。 我肯定会继续关注xdelta,因为我已经多次使用它来生成600MB + ISO文件的高质量差异,这些文件是我们为分发我们的产品而生成的,并且表现非常好。

bsdiff旨在为二进制文件创建非常小的补丁。 如其页面所述,它需要max(17*n,9*n+m)+O(1)字节的内存并以O((n+m) log n)时间运行(其中n是旧文件和m是新文件的大小)。

最初的实现是在C中,但这里描述了一个C#端口,可在此处获得 。

你见过VCDiff吗? 它是Misc库的一部分,似乎相当活跃(最新版本r259,2008年4月23日)。 我没有用它,但认为值得一提。

值得一看的是其他一些人在这个领域做了什么,而不一定是在C#领域。

这是一个用c#编写的库

SVN也有一个二进制diff算法,我知道python中有一个实现,虽然我用快速搜索找不到它。 他们可能会给你一些关于在哪里改进自己的算法的想法

如果这是用于安装或分发,您是否考虑过使用Windows Installer SDK? 它具有修补二进制文件的能力。

http://msdn.microsoft.com/en-us/library/aa370578(VS.85).aspx

这是一个粗略的准则,但以下是rsync算法,可用于创建二进制补丁。

http://rsync.samba.org/tech_report/tech_report.html