C#中的二进制补丁生成

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

基本上,比较两个文件(指定为 oldnew ),并生成一个可用于升级 old 文件的修补程序文件,与 new 文件相同的内容。

实施必须相对较快,并且需要处理大量文件。它应该显示O(n)或O(logn)运行时间。

我自己的算法往往要么很糟糕(快速但产生巨大的补丁),要么很慢(产生小的补丁,但有O(n ^ 2)运行时)。

任何建议,或指针实施将是很好的。

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

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

  1. Grab the first four bytes from the old file, call this the key
  2. Add those bytes to a dictionary, where key -> position, where position is the position where I grabbed those 4 bytes, 0 to begin with
  3. Skip the first of these four bytes, grab another 4 (3 overlap, 1 one), and add to the dictionary the same way
  4. Repeat steps 1-3 for all 4-byte blocks in the old file
  5. From the start of the new file, grab 4 bytes, and attempt to look it up in the dictionary
  6. If found, find the longest match if there are several, by comparing bytes from the two files
  7. Encode a reference to that location in the old file, and skip the matched block in the new file
  8. If not found, encode 1 byte from the new file, and skip it
  9. Repeat steps 5-8 for the rest of the new file

这有点像压缩,没有窗口,所以它会使用大量的内存。但是,它相当快速,并且只要我尽量使代码输出最小化,就会产生相当小的补丁。

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

在这篇文章中我跳过了上述算法的细微差别,但如果需要,我可以发布更多细节。然而,我确实认为我需要完全不同的算法,所以改进上述算法可能不会让我足够远。


Edit #1: Here is a more detailed description of the above algorithm.

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

其次,执行获取4个字节并将其位置添加到字典步骤,以查看整个文件中的所有内容。

第三,从 new 文件的开始位置,执行循环尝试定位4个字节的现有组合,并查找最长匹配。确保我们只考虑旧文件中的位置,或者从新文件中早于的位置,而不是当前位置。这确保了我们可以在修补程序应用程序中重新使用旧文件和新文件中的材料。


Edit #2: Source code to the above algorithm

您可能会收到关于证书有问题的警告。我不知道如何解决,所以暂时只接受证书。

源代码使用了我库中其他类型的很多其他类型,因此文件并非全部需要,但这是算法实现。


@lomaxx,我试图找到一个很好的用于颠覆的算法的文档,名为xdelta,但除非你已经知道算法是如何工作的,否则我发现的文档无法告诉我需要知道什么。

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

我快速浏览了您提供的该网站的算法,而且很遗憾不能使用。来自二进制diff文件的评论说:

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

尽管我的需求并不理想,所以我正在寻找更实用的解决方案。

谢谢你的回答,如果我需要他们的话,可以给他的工具增加一个书签。

Edit #1: Note, I will look at his code to see if I can find some ideas, and I'll also send him an email later with questions, but I've read that book he references and though the solution is good for finding optimal solutions, it is impractical in use due to the time requirements.

Edit #2: I'll definitely hunt down the python xdelta implementation.

0
这段代码是post,这里是我当前的版本,虽然我没有在年龄维护这个库: lassevk.kilnhg.com/Code/LVK-for-NET/net-40/trunk/Files/…
额外 作者 Lasse Vågsæther Karl,
源代码链接已死亡。你能更新吗?
额外 作者 lasseschou,

6 答案

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

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

0
额外

可能值得检查一下其他人在这个领域做了些什么,而不一定是在C#领域。

这是用c#编写的图书馆

SVN也有一个二进制差异算法,我知道有一个python实现,尽管我无法通过快速搜索找到它。他们可能会给你一些关于在哪里改进自己的算法的想法

0
额外
SVN使用xdelta算法(至少从源头上看)
额外 作者 Simon Buchan,

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

0
额外
是的,xdelta很好。但是,它确实在相对较小的窗口上工作(如果我没有弄错的话,它的工作量为100kb),但通过实施它可以轻松调整我们的数据。如果我没有弄错的话,窗口大小是为了颠覆速度而选择的,但只要它不需要整晚(我目前的实现就是这样),我们的代码可以轻松运行一段时间。
额外 作者 Lasse Vågsæther Karl,

bsdiff was designed to create very small patches for binary files. As stated on its page, it requires max(17*n,9*n+m)+O(1) bytes of memory and runs in O((n+m) log n) time (where n is the size of the old file and m is the size of the new file).

最初的实现是用C语言编写的,但C#端口在这里有描述,可在此处下载。

0
额外

你见过 VCDiff 吗?它是杂项图书馆的一部分,似乎相当活跃(2008年4月23日发布,最后一版r259)。我没有使用它,但认为它值得一提。

0
额外

这是一个粗略的指导原则,但以下是可用于创建二进制修补程序的rsync算法。

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

0
额外