-4

我正在尝试压缩整数列表，其中：

  • 没有负数。
  • items的取值范围是从[1....28]
  • 列表中共有2482113项。
  • 目前我使用5 位来存储每个数字。

  • “出现”的统计数据如下

    • 1：1242149
    • 2：620038
    • 3：309399
    • 4：154983
    • 5 : 77816
    • 6：38601
    • 7 : 19651
    • 8 : 9790
    • 9 : 4830
    • 10 : 2447
    • 11 : 1253
    • 12 : 597
    • 13 : 303
    • 14 : 130
    • 15 : 73
    • 16 : 23
    • 17 : 17
    • 18 : 4
    • 19 : 4
    • 20 : 2
    • 21:1
    • 23:1
    • 28 : 1

所以请告诉我压缩这种数据的最佳方法（估计压缩率 - 如果可能的话 - 非常感谢）。

4

3 回答 3

6

使用这种分布(a)，您可能想要研究可变长度编码方案，例如 Huffman。与固定的 5 位大小相比，这将为您提供更好的压缩。它们通过使用更少的位来表示更常见的值（并使用更多的位来表示不常见的值）来降低平均位宽度。

举一个简单的例子，假设一个0位代表数字一，所有其他数字由一个1位表示，后跟您当前的 5 位方案。

这意味着您为 1 的每个值（1,242,149 x 4 = 4,968,596 位）节省了 4 位，而为所有其他值（1,239,964 位）“浪费”了一位，净节省了 370 万位。

这是针对您的特定数据集的“硬编码”霍夫曼方案，旨在说明其工作原理，您可能希望对任意数据集更具适应性。

并且扩展它以包含更多更大的数量会带来额外的改进。我们已经知道最高价值的节省：

Bit pattern  Value   Quantity  Saved bits
0                1  1,242,149   4,968,596  (4 per)
1xxxxx          >1  1,239,964   1,239,964- (1 per)
                                ---------
Net saving                      3,728,632  (extra return 3,728,632)

对于前两个值：

Bit pattern  Value   Quantity  Saved bits
0                1  1,242,149   4,968,596  (4 per)
10               2    620,038   1,860,114  (3 per)
11xxxxx         >2    619,926   1,239,852- (2 per)
                                ---------
Net saving                      5,588,858  (extra return 1,860,226)

对于前三名：

Bit pattern  Value   Quantity  Saved bits
0                1  1,242,149   4,968,596  (4 per)
10               2    620,038   1,860,114  (3 per)
110              3    309,399     618,798  (2 per)
111xxxxx        >3    310,527     931,581- (3 per)
                                ---------
Net saving                      6,515,927  (extra return 927,069)

对于前四名：

Bit pattern  Value   Quantity  Saved bits
0                1  1,242,149   4,968,596  (4 per)
10               2    620,038   1,860,114  (3 per)
110              3    309,399     618,798  (2 per)
1110             4    154,983     154,983  (1 per)
1111xxxxx       >4    155,544     622,176- (4 per)
                                ---------
Net saving                      6,980,315  (extra return 464,388)

在此级别，您的每个数字固定 5 位的方案会产生 12,410,565 位。净节省 6,980,315 位，现在总压缩大小为 5,430,250 位，比固定位大小方法节省约 56 位。

随着更多价值的增加，您可以看到额外的投资回报迅速减少。除了前四个值之外，您不会使用此硬编码方案保存任何内容，因为每个项目的位节省为零（之后为负数）。真正的自适应编码会给你更多的节省（因为它也在优化xxxxx比特），但可能不会太多。

(a)从外观上看，这是一个非常人为的分布。每个数量大约是前一个数量的一半，使可变长度编码成为理想的解决方案。

于 2014-01-21T23:32:09.040 回答
3

看看霍夫曼编码。我不知道确切的细节，但基本原则是根据需要将更少的位分配给更常见的数字，将更多的位分配给不太常见的数字，以便总体而言，每个数字的平均位数更少比您期望的均匀分布（每个字符约 5 位）

于 2014-01-21T23:33:42.330 回答
2

有关压缩信息的信息，请参阅http://en.wikipedia.org/wiki/Huffman_coding 。

因为列表中的大多数项目的频率大于列表中所有频率较低的项目的频率之和，所以实际上每个项目的效率约为 2 位。

精确压缩提供平均每个符号 2.00915 位。下面的计算揭示了我对编码的选择。

(1242149 + 2 * 620038 + 3 * 309399 + 4 * 154983 + 5 * 77816 + 6 * 38601 + 7 * 19651 + 8 * 9790 + 9 * 4830 + 10 * 2447 + 11 * 1253 + 12 * 597 + 13 * 30 + 14 * 130 + 15 * 73 + 16 * 23 + 17 * 17 * 18 * 4 + 19 * 4 * 20 * 2 + 21 * 1 + 22 * (1+1)) / 2482113.0

请注意，由于您的频率并不总是接近 2 http://en.wikipedia.org/wiki/Arithmetic_coding的逆幂，因此压缩可能会稍微好一些。

于 2014-01-21T23:33:20.790 回答