C# 中的二进制补丁生成

题

有谁拥有或知道 C# 中的二进制补丁生成算法实现吗？

基本上，比较两个文件（指定老的和新的），并生成可用于升级的补丁文件老的文件的内容与新的文件。

实施必须相对较快，并且可以处理大文件。它应该表现出 O(n) 或 O(logn) 运行时间。

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

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

具体来说，该实现将用于使我们拥有一台主服务器的各种大型数据文件的服务器保持同步。当主服务器数据文件发生变化时，我们也需要更新多个异地服务器。

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

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

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

我在这篇文章中跳过了上述算法的更多细微差别，但如果需要，我可以发布更多详细信息。然而，我确实觉得我需要一个完全不同的算法，所以改进上述算法可能不会让我走得足够远。

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

首先，合并两个文件，这样就得到一个大文件。记住两个文件之间的切点。

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

第三，从哪里来新的文件开始时，执行循环尝试定位现有的 4 个字节组合，并找到最长的匹配项。确保我们只考虑旧文件中的位置，或者来自 新文件中的位置比当前位置早. 。这确保了我们可以在补丁应用期间重复使用旧文件和新文件中的材料。

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

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

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

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

或许我只是太笨了...:)

我快速浏览了您提供的那个网站上的算法，不幸的是它不可用。二进制差异文件的注释如下：

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

但我的需求不是最佳的，所以我正在寻找更实用的解决方案。

不过，谢谢您的回答，如果我需要的话，请在他的实用程序中添加一个书签。

编辑#1: ：请注意，我会查看他的代码，看看是否可以找到一些想法，稍后我还会向他发送一封包含问题的电子邮件，但我已经阅读了他引用的那本书，尽管该解决方案对于寻找最佳解决方案很有帮助，由于时间要求，它在使用中是不切实际的。

编辑#2: ：我一定会找到 python xdelta 实现。

解决方案

抱歉我无法提供更多帮助。我肯定会继续关注 xdelta，因为我已经多次使用它来对我们为分发产品而生成的 600MB 以上 ISO 文件生成质量差异，并且它的性能非常好。

其他提示

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

最初的实现是用 C 编写的，但描述了 C# 端口这里并可用这里.

你见过吗 VCD差速器？它是杂项库的一部分，该库似乎相当活跃（最新版本 r259，2008 年 4 月 23 日）。我没有使用过它，但认为它值得一提。

可能值得看看其他一些人在这个领域所做的事情，不一定是在 C# 领域。

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

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

这是一个粗略的指南，但以下内容适用于 rsync 算法，可用于创建二进制补丁。

许可以下： CC-BY-SA 和归因