有没有人知道C＃中的二进制补丁生成算法实现？

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

该实现必须相对较快，并且可以处理大量文件。它应显示O(n)或者O(logn)运行时。

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

任何建议或者实现的指针都将是不错的。

具体而言，该实现将用于使服务器同步处理我们拥有一个主服务器的各种大型数据文件。当主服务器数据文件更改时，我们还需要更新多个异地服务器。

我做出的最幼稚的算法仅适用于可以保存在内存中的文件，如下所示：

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

这有点像没有窗口的压缩，因此它将占用大量内存。但是，只要我尝试使代码输出最小化，它就相当快，并且会产生很小的补丁。

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

我在这篇文章中略过了上述算法的更多细微差别，但如有必要，我可以发布更多详细信息。但是，我确实确实确实需要一个不同的算法，因此对上述算法进行改进可能不会使我走得足够远。

编辑1：这是上述算法的更详细说明。

首先，将两个文件合并，以使我们拥有一个大文件。记住两个文件之间的切入点。

其次，抓取4个字节并将其位置添加到整个文件中所有内容的字典步骤中。

第三，从新文件的开始处进行循环，尝试找到现有的4字节组合，并找到最长的匹配项。确保仅考虑旧文件中的位置，或者仅考虑新文件中当前位置以外的位置。这确保了我们可以在补丁应用期间重用旧文件和新文件中的材料。

编辑2：上述算法的源代码

我们可能会收到有关证书有问题的警告。我不知道该如何解决，因此暂时只接受证书。

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

@lomaxx，我试图找到一个很好的文档来介绍用于Subversion的算法xdelta，但是除非我们已经知道算法的工作原理，否则我发现的文档无法告诉我我需要知道的内容。

也许我只是很稠密... :)

我快速浏览了我们提供的那个站点上的算法，很遗憾，它不可用。来自二进制差异文件的注释说：

Finding an optimal set of differences requires quadratic time relative to the input size, so it becomes unusable very quickly.

我的需求并不是最优的，因此我正在寻找更实用的解决方案。

不过，感谢回答，如果需要，可以在其实用程序中添加书签。

编辑＃1：注意，我将查看他的代码，看看是否能找到一些想法，并且稍后我还会向他发送电子邮件询问问题，但是我已经阅读了他所引用的那本书，尽管该解决方案很适合为了找到最佳的解决方案，由于时间的限制，在实际应用中是不切实际的。

编辑＃2：我一定会追查python xdelta实现。

解决方案

回答

可能值得检查一下其他一些人在这个领域中正在做什么，而不一定是在Carena中。

这是用C＃编写的库

SVN也有一个二进制diff算法，我知道在python中有一个实现，尽管我无法通过快速搜索找到它。他们可能会给我们一些改进自己算法的想法

回答

抱歉，我帮不上什么忙。我一定会一直关注xdelta，因为我已经多次使用它来对我们为分发产品而生成的600MB + ISO文件产生质量差异。

回答

如果这是用于安装或者分发，我们是否考虑过使用Windows Installer SDK？它具有修补二进制文件的功能。

http://msdn.microsoft.com/zh-CN/library/aa370578(VS.85).aspx

回答

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

回答

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

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

回答

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

最初的实现是用C语言实现的，但此处描述了Cport，并在此处提供。