python - 具有静态噪声的类似 1000 字节 block 的最小二进制差异？

Question

对于类似的 1000 字节 block ，我需要一个最小差异。这些 block 将最多有 20% 的位不同。翻转的比特将像 radio 静态一样——随机翻转的比特在整个 block 上均匀分布。这是我使用 XOR 和 lzo 压缩的伪代码:

minimal_diff=lzo(XOR(block1,block2))

由于 block 很小，我正在使用 lzo 的压缩，希望这种压缩格式具有最少的样板文件。

我已经审查了 xdelta 和 bsdiff 等算法，但这些算法不适用于像这样的随机静态噪声。这些更侧重于查找移位的字节序列。

这里可以使用纠错代码来创建最小差异吗？具体如何？

精确的算法会很好。如果它只是一篇研究论文理论而没有实现，那么我不感兴趣。

注意:每个 block 中的相似位排列。没有转移。只有一些随机噪声位翻转可以区分块。

Answer 1

如果它是真正的随机噪声，那么它就不会真正压缩。这意味着如果您有 8,000 位(1,000 字节 x 8 位/字节)并且每个单独的位都有 1/5 (20%) 的翻转概率，那么您不能将更改的位编码为小于 8,000 x (-4/5 x ln2 4/5 + -1/5 x ln2 1/5) = 8,000 x (-4/5 x -0.322 + -1/5 x -2.322) = 8,000 x (0.2576 + 0.4644) = 5,776 位，即722 字节。这是基于香农的信息论。

因为表示更改位的简单方法需要 1000 个字节(仅对两个 block 的异或进行编码)，所以通过压缩最多可以节省 30% 的空间。如果您始终如一地获得更多，则位不会随机分布或位翻转概率小于 20%。

Lempel-Ziv 等标准算法专为结构化数据(即非随机噪声的数据)而设计。像这样的随机噪声最好用简单的霍夫曼编码之类的东西编码。但是您最多可以节省 30%，所以这是否真的值得付出努力是个问题。