有很多关于非常大文件（1MB+）的二进制差异算法的信息。但是，我的用例不同。这就是为什么它不是重复的。
我有许多对象的集合，每个对象都在 5-100 字节范围内。我想通过网络发送这些对象的更新。我想将更新编译成单独的 TCP 数据包（合理的 MTU 约为 1400）。我想在每个数据包中尝试尽可能多的更新：首先添加它们的 ID，然后将所有二进制对象的二进制差异组合起来。
用于此目的的最佳二进制差异算法是什么？
问问题
851 次
2 回答
1
简单的答案是将许多小对象组合成一个大对象，然后使用现有的二进制差异算法有效地发送组合对象的差异。
但是没有必要自己动手。我个人会通过将所有对象放入文件系统中来解决这个问题，然后使用 rsync 发送差异。
这在理论上不是最优的。但是请考虑以下几点：
- 实现很简单。
- 代码经过实战测试 - 您的代码需要很长时间才能达到类似的可靠性水平。
- 这个实现涵盖了接收方的状态不是发送方期望的边缘情况。例如，如果接收器发生崩溃/重新启动，可能会发生这种情况。
在某些情况下，这是错误的解决方案。但我会坚持让这个简单的解决方案在变得聪明和复杂之前失败。
于 2018-02-19T17:51:46.673 回答
1
对于这么小的对象，您可以使用经典的最长公共子序列算法来创建“差异”。
但是，这不是解决问题的最佳方法。LCS 算法受到与目标序列匹配时每个原始字节仅使用一次的要求的限制。您可能并不真正需要该约束来对压缩数据包进行编码，因此除了有点慢之外，它还会导致次优解决方案。
您的目标实际上是使用原始对象的示例来压缩新对象，您应该从这些方面考虑。
有很多很多方法，但您可能对如何编码这些新对象有所了解。可能您正在考虑用对原始对象部分的引用替换新对象的部分。
在这种情况下，为每个原始对象创建一个后缀数组（https://en.wikipedia.org/wiki/Suffix_array）是可行的。然后，当您对相应的新对象进行编码时，您可以在每个字节处使用后缀数组来查找旧对象的最长匹配段。如果它足够长以节省成本，那么您可以用引用替换相应的字节。
于 2018-02-19T18:59:41.197 回答