具有静态噪声的类似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位的间隙，等等。如果翻转位之间的间隔有任何规律性，您可以在这种编码上使用常规压缩器以进一步节省成本。在