压缩大约2百万个数字序列的最佳方法是什么(值范围是1 - > 28)

Question

我想压缩一个整数列表,其中:

• 没有负数.
• 项目的价值范围是[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

所以请告诉我压缩这类数据的最佳方法(估计压缩比 - 如果可能的话 - 非常感谢).

Answer 1

有了这种分布^(a),你可能想要研究一个可变长度的编码方案,比如Huffman.这将为您提供比固定的5位大小更好的压缩.它们通过使用较少的位来指示更常见的值(以及表示不常见值的更多位)来降低平均位宽.

举一个简单的例子,让我们说0一点代表第一,所有其他数字用一个1位代表当前的5位方案.

这意味着您为每个值保存4位(1,242,149 x 4 = 4,968,596位),并为所有其他值(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)根据它的外观进行非常人为的分配.每个数量大约是先前数量的一半,使得可变长度编码成为理想的解决方案.