改进数字压缩算法？

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编码。

使用Huffman编码比您的步骤更重要；我将向您说明原因：

考虑以下数据：

1 2 3 4 5 6 7 4294967295

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

1 1 1 1 1 1 1 4294967288

所需双边投资总额仍为32*8

使用Huffman编码，频率如下：

1 => 7
4294967288 => 1

Huffman码是1 => 0和4294967288 => 1

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

Huffman编码将大小减少32*8/8 = 32倍

Answer 2

这个问题在数据库社区中是众所周知的“倒排索引压缩”。你可以在谷歌上搜索一些文件。

以下是一些最常见的技术：

• 可变字节编码(VByte)
• Simple9，Simple16
• “参考框架”系列技术
  • PForDelta
  • 自适应参照系

​

• 水稻-Golomb编码 (通常用作其他技术的一部分)

VByte和Simple9/16易于实现，速度快，在实际应用中具有良好的压缩比。

Huffman编码对于索引压缩不是很好，因为它速度慢，而且在实践中差异很大。(但就你的情况而言，这可能是个不错的选择。)

Answer 3

你有几个号码？如果您的集合足够密集地覆盖范围[0..(2^32)-1] (您正在计算)，那么一个4 4GiB位字段，其中n-th位表示自然数n的存在或缺失可能是有用的。