用于小二进制 blob 的二进制 diff 算法

Question

有很多关于相当大文件 (1MB+) 的二进制差异算法的信息。但是，我的用例不同。 这就是为什么它不是重复的。

我有很多对象的集合，每个对象都在 5-100 字节范围内。我想通过网络发送这些对象的更新。我想将更新编译成单独的 TCP 数据包（合理的 MTU 约为 1400）。我想尝试在每个数据包中安装尽可能多的更新：首先添加它们的 ID，然后将所有二进制对象的二进制差异合并。

用于此目的的最佳二进制差异算法是什么？

Answer 1

简单的答案是将许多小对象组合成一个大对象，然后使用现有的二进制差异算法有效地发送该组合对象的差异。

但是没有必要自己动手。我个人会通过将所有对象放入文件系统来解决这个问题，然后使用 rsync 发送差异。

这在理论上不是最优的。但是请考虑以下几点：

1. 实现很简单。
2. 代码经过实战测试 - 您的代码需要很长时间才能达到类似的可靠性水平。
3. 此实现涵盖了接收方的状态与发送方所期望的不同的边缘情况。如果接收者有一个 crash/restart.
就可能发生

在某些情况下，这是错误的解决方案。但我会坚持让这个简单的解决方案失败，然后再巧妙地解决它。

Answer 2

对于如此小的对象，您可以使用经典的 longest-common-subsequence 算法来创建 'diff'。

但是，这不是解决您的问题的最佳方法。 LCS 算法受限于在与目标序列匹配时每个原始字节仅使用一次的要求。你可能真的不需要那个约束来编码你的压缩数据包，所以它会导致 sub-optimal 除了有点慢之外的解决方案。

您的目标确实是使用原始对象的示例来压缩新对象，您应该从这些方面考虑。

有很多很多方法，但您可能对如何对这些新对象进行编码有所了解。您可能正在考虑将新对象的部分替换为对原始对象部分的引用。

在那种情况下，为每个原始对象（https://en.wikipedia.org/wiki/Suffix_array）制作一个后缀数组是可行的。然后当你对相应的新对象进行编码时，在每个字节处你可以使用后缀数组找到旧对象的最长匹配段。如果它足够长可以节省，那么你可以用引用替换相应的字节。