8

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

一个数据包由 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%），有损压缩就是一种替代方案——对于这个特定的数据流，位位置的数值权重是无关紧要的，因此在较高位中发生的错误是完全不用担心。

提前谢谢大家！

4

5 回答 5

6

如果您发送未压缩的第一个整数，并为其他 255 个整数计算此整数与前一个整数之间的异或，您将获得一个位流，其中非零位非常罕见。这个比特流可以用算术编码进行编码。

如果在计算相邻值之间的异或之后，我们有一个比特流，其中比特相互独立（每个“0”或“1”比特具有相同的概率，独立于整数中的比特位置，独立于数据包中的整数位置） ，算术编码保证最佳的无损压缩率。

于 2012-11-12T18:44:07.257 回答
5

您最好的选择是使用现有技术（例如，Lempel-Ziv-Welch；flate）或在这种方法之前使用差异编码（可能更好）。使用差异编码，您将用该字节与之前字节之间的差异替换每个字节（第一个字节除外）。现在你应该得到很多零，并穿插一些小值。霍夫曼编码或类似 LZW 的东西将非常彻底地压缩大部分为零的字符串。

于 2012-11-12T18:38:32.690 回答
5

您可以对输入数据进行 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 字节序列的 Huffman 编码、LZW 或熵编码，但一个好的尝试可能是简单的位运行长度编码，从位位置 0 开始计算每个位之间的零位：

4, 14, 51, 9, 9

如果您将运行长度限制为 30 并选择转义符号 31，意思是“将 31 添加到下一个运行长度”，您会得到

4, 14, 31, 20, 9, 9

这将是整个序列的 6*5 位。您现在可以对其进行霍夫曼编码...

于 2012-11-12T19:04:59.980 回答
1

从您的示例看来，更改的少数位并不总是相同的（例如，始终是最低的 4 位）。所以我建议对转置数组上的位进行简单的运行长度编码。如果没有您的数字/数据的分布，我建议从 4 位开始，但您可以尝试一些示例输入。

伪代码（用于压缩）如下所示：

 for bitpos = 0 to 31
     for datapos = 0 to 255 
         BitString.append(getbit(data[datapos], bitpos);
     endfor
 endfor

 result="";
 pos = 0;
 while (notEndOfString)
     # count 1s
     count = 0;
     while (pos < 32*256 AND count < 16 AND BitString[pos]==1)
         count++;
         pos++;
         endwhile
     result.append4BitNumber(count);
     # count 0s
     count = 0;
     while (pos < 32*256 AND count < 16 AND BitString[pos]==0)
         count++;
         pos++;
         endwhile
     result.append4BitNumber(count);
 endwhile

也许可以通过事后应用 Lempel-Ziv 或 Huffman 编码来增加压缩率——但如果没有关于输入数据分布的更多信息，就不能说更多（这通常适用于这个问题——输入数据的更好信息，可以对其进行某种压缩）。

编辑：另一种简单的方法是对变化的位位置进行编码：从初始的 32 位字开始，然后为每个数据字存储 3 位，定义位的变化量（即 0..7），然后您存储 0..7 乘以 4 位，其中 4 位编码 chaning 位的位置。这意味着当平均 2 位更改时，您的 32*256 位数据包需要 32+255*(3+8)=2837 => 大约其原始大小的 35%。

如果您经常有相同数量的位变化，那么这 4 位模式中的一些会经常出现，而另一些则根本不会出现 => 在这 4 个位组上的霍夫曼编码会将其压缩到最佳状态（如果您知道这些模式概率永远不会改变，你甚至可以制作一个静态的霍夫曼树，所以你不必存储它）。

于 2012-11-12T19:02:16.367 回答
1

我的想法与 Evgeny Kluev 的想法相似。第一个整数未压缩发送，其余的变为自身和前一个整数的 XOR。

1100 1001 1110 0010 0001 0101 0110 1101    Sample 1  
               *                   * 
0000 0000 0000 1000 0000 0000 0000 1000    Sample 2

0000 0000 0000 0000 0000 0000 0000 0000    Sample 3
     *            *            *   
0000 1000 0000 0001 0000 0000 0100 0000    Sample 4

现在，我没有将稀疏数据分成块并在这里进行算术编码，而是进一步转换数据。因为实际上，算术编码是基于数据频率不相等的。看着这个，你觉得

0000 0000 0000 1000 0000 0000 0000 1000

会出现比

0000 1000 0000 0001 0000 0000 0100 0000

或相反亦然？

好的，这就是我将如何进一步转换数据。让其余数据成为描述连续零个数的数字序列。例如，数据变为：

1100 1001 1110 0010 0001 0101 0110 1101    Sample 1  followed by decimals
12, 15, 39, 10, 9, 6

现在您可以对这些尾随小数执行算术编码。这次频率会有意义！因为您在问题中说变化很小，这意味着更多的连续零会出现更多。

编辑：这个答案与 hirschhornsalz 的答案完全相同。除了他还提到你可以限制零的最大数量并将它们分开......

于 2012-11-12T19:10:58.633 回答