寻找更好的压缩技术

Question

我正在压缩由数据包组成的二进制流

数据包由256个32位整数(样本)组成.问题是大多数整数只改变前一整数的几位(通常0到4位最多来自流中的前一个样本).

这是一个例子:

3322 2222 2222 1111 1111 1110 0000 0000    BIT POSITIONS
1098 7654 3210 9817 6543 2109 8765 4321
--------------------------------------------------------
1100 1001 1110 0010 0001 0101 0110 1101    Sample 1  
               *                   * 
1100 1001 1110 1010 0001 0101 0110 0101    Sample 2     changes: bit 19, 4

1100 1001 1110 1010 0001 0101 0110 0101    Sample 3     changes: none
     *            *            *   
1100 0001 1110 1011 0001 0101 0010 0101    Sample 4     changes: bit 27, 17, 7
...

我目前的损耗压缩方案基于半字节.基本上我正在使用一个控制字节,我正在编码 - 使用单个位 - 从前一个样本改变了半字节; 如果有变化,我将在压缩流中包含修改的半字节,否则它们将在解压缩时从前一个样本重建.

以下是我提供的示例流将如何压缩:

Control Byte: 11111111     // all nibbles change, since this is first sample
Data:         1100 1001 1110 0010 0001 0101 0110 1101 // data for all nibbles
Control Byte: 00010001     // only nibbles 3 and 7 have changes
Data:         1010 0101    // data for nibbles 3 and 7
Control Byte: 00000000     // no nibbles are changing
Data:                      // no data is required
Control Byte: 01010010     // nibbles 1, 3 and 6 have changes
Data:         0001 1011 0010   // nibbles 1, 3 and 6
...

使用这种方案,我们有256字节的固定开销(控制字节),平均可变压缩数据长度为260字节(从样本到样本的半字节变化).考虑到未压缩的数据包长度为1024字节,这实际上给了我们50%的平均压缩率.

这不错,但我的直觉是,更好的方法是可行的.是否有人意识到一种更好的压缩策略,它利用了从样本到样本的极少数位变化的事实？只要解压缩后的误码率很小(小于3%),有损压缩就是另一种选择 - 对于这个特定的数据流,位位置的数字权重是无关紧要的,因此高位中的错误是完全没关系.

提前谢谢大家!

Answer 1

如果发送第一个未压缩的整数,而对于其他255个整数,则在此整数和前一个整数之间计算XOR,您将获得非零位非常罕见的位流.该比特流可以用算术编码来编码.

如果在计算邻居值之间的XOR之后,我们有一个比特流,其中比特彼此独立(每个"0"或"1"比特具有相同的概率,独立于整数中的比特位置并且独立于分组中的整数位置) ,算术编码保证最佳的无损压缩率.

Answer 2

您最好的选择是使用现有技术(例如,Lempel-Ziv-Welch; flate)或在这种方法之前使用差异编码(可能更好).使用差分编码,您将使用该字节与之前的字节之间的差异替换每个字节(第一个除外).现在你应该得到很多零点,并且散布一些小值.霍夫曼编码或像LZW这样的东西会彻底压缩大部分为零的字符串.

Answer 3

您可以对输入数据执行XOR.因为只有少数位会发生变化,所以这会给你带来的结果,其中大部分是0由几位1之间的.

1100 1001 1110 0010 0001 0101 0110 1101    Sample 1  
1100 1001 1110 1010 0001 0101 0110 0101    Sample 2     
1100 1001 1110 1010 0001 0101 0110 0101    Sample 3     
1100 0001 1110 1011 0001 0101 0010 0101    Sample 4     

在起始值之后,这将产生序列

0b0000 0000 0000 1000 0000 0000 0001 0000, 
0b0000 0000 0000 0000 0000 0000 0000 0000, 
0b0000 1000 0000 0010 0000 0000 1000 0000

您现在可以使用各种标准压缩算法.霍夫曼编码的8字节序列,LZW或熵编码,但一个很好的尝试可能是一个简单的位运行长度编码,计算从位位置0的每一位之间的零位:

4, 14, 51, 9, 9

如果将运行长度限制为30并选择转义符号31,意味着"将31添加到下一个运行长度",则得到

4, 14, 31, 20, 9, 9

对于整个序列,这将是6*5位.您现在可以做哈夫曼编码上说 ...