algorithm - 改进数字压缩算法？

Question

我有很多唯一的数字，都是正数，顺序无关紧要，0 < num < 2^32 .
示例:23 56 24 26

最大的，56 , 需要 6 bits空间。所以，我需要:4*6 = 24 bits总计。

我执行以下操作以节省空间:
我先对它们进行排序:23 24 26 56 (因为顺序无关紧要)
现在我得到了每个与之前的区别:23 1 2 30

最大的，30 , 需要 5 bits空间。
在此之后，我将所有数字存储在 4*5 bits = 20 bits 中空间。

问题:如何进一步改进这个算法？

更多信息:自请求以来，数字大部分在 2.000-4.000 范围内.小于 300 的数字非常罕见。超过 16.000 的号码也很少见。一般来说，所有的数字都会很接近。例如，它们可能都在 1.000-2.000 中。范围或者它们可能都在 16.000-20.000 中范围。数字总数将在 500-5.000 范围内。 .

Answer 1

您迈出的第一步是好的，因为排序可以将差异降到最低。这是改进算法的一种方法:

1. 像您所做的那样排序和计算差异。
2. 使用Huffman coding在上面。

霍夫曼编码的使用比您的步骤更重要；我会告诉你原因:

考虑以下数据:

1 2 3 4 5 6 7 4294967295

其中 4294967295 = 2^32-1。使用您的算法:

1 1 1 1 1 1 1 4294967288

所需的总比特数仍然是 32*8

使用霍夫曼编码，频率为:

1 => 7
4294967288 => 1

霍夫曼编码为 1 => 0 和 4294967288 => 1

所需的总位数 = 7*1 + 1 = 8 位

霍夫曼编码减少了 32*8/8 = 32 倍的大小