c# - C#中的二进制补丁生成

Question

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

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

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

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

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

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

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

抓取旧文件的前四个字节，将此键称为

将这些字节添加到字典中，其中key-> position，其中position是我抓取这4个字节的位置，0以

开头

跳过这四个字节中的第一个，获取另外4个字节(3个重叠，1个)，然后以与

相同的方式添加到字典中

对旧文件

中的所有4字节块重复步骤1-3

从新文件的开头开始，抓取4个字节，然后尝试在字典

中查找它

如果找到，则通过比较两个文件

中的字节来找到最长的匹配项(如果存在)

在旧文件中编码对该位置的引用，并在新文件中跳过匹配的块

如果找不到，请编码新文件中的1个字节，然后跳过它

对其余新文件

重复步骤5-8

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

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

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

编辑＃1 :这是上述算法的更详细描述。

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

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

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

编辑＃2 :Source code to the above algorithm

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

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

@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实现。

Answer 1

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