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

Question

我需要一个相似的1000字节块的最小差异。这些块最多有20%的位不同。翻转的位元将像无线电静电一样——随机翻转的位元在整个区块上均匀分布。以下是我使用XOR和lzo压缩的伪代码：

minimal_diff=lzo(XOR(block1,block2))

由于块很小，所以我使用lzo的压缩，希望这种压缩格式的样板文件最少。在

我已经回顾了xdelta和bsdiff等算法，但这些算法不适用于这样的随机静态噪声。它们更倾向于查找移位的字节序列。在

纠错代码能在这里产生最小的差异吗？到底是怎么回事？在

精确的算法会更好。如果这只是一个研究论文理论，没有实施，那么我就不感兴趣了。在

注：每个块中相似的位排成一行。没有变化。只有一些随机的噪声位翻转来区分块。在

Answer 1

你已经试过标准的压缩算法了吗？你看到了什么表演？在新旧块的异或上应该可以获得相当好的压缩比，因为0的偏差很大

除了标准选项之外，一个让人想到的选择是将每个diff编码为一个可变长度整数列表，指定翻转位之间的距离。例如，使用5位可变长度整数，您可以描述5位中最多16位的间隙，10位中17到1024位的间隙，等等。如果翻转位之间的间隔有任何规律性，您可以在这种编码上使用常规压缩器以进一步节省成本。在

Answer 2

如果它真的是随机噪声，那么它就不会真正压缩。这意味着，如果你有8000位（1000字节x 8位/字节），每一位都有1/5（20%）的翻转概率，那么你就不能在8000 x（-4/5 x ln2 4/5+-1/5 x ln2 1/5）=8000 x（-4/5 x-0.322+-1/5 x-2.322）=8000 x（0.2576+0.4644）=5776位，即722字节。这是基于香农的信息论。在

因为表示变化位的简单方法需要1000个字节（只需对两个块的异或进行编码），通过压缩可以节省最多30%的空间。如果你实现的一致性更高，那么比特不是随机分布的，或者比特翻转概率小于20%。在

像Lempel-Ziv这样的标准算法是为结构化数据（即非随机噪声的数据）设计的。像这样的随机噪声最好用简单的哈夫曼编码之类的东西来编码。但你最多可以节省30%，所以这是一个问题，它是否真的值得努力。在