list - 存储多集/无序列表的节省空间的方法

Question

我需要在文件中存储大量整数。整数的顺序无关紧要，因此总信息量应低于有序列表的信息量。有没有比任意排序的数组更节省空间的方法来存储数字？

编辑:我假设整数是完全随机的。我真的在寻找一种通用的方法来挤出通过修复排列引入的冗余信息。

Answer 1

要压缩，您实际上需要更高的信息量。您通常无法压缩随机性。幸运的是，您的问题说明允许您重新排序数据。因此，您可以对数据进行排序，从而增加其信息内容。然后，您只需要存储最小的和一阶差分的序列，而不是存储整数列表。第一个差异将小于数字本身，因此应该适合更少的位。

排序后的随机生成序列

sorted seq     (173 218 257 490 618 638 715 815 856 929 932 996)
number of bits (  6   6   6   7   7   7   7   7   7   7   7   7)

可以存储为

first diff     (173 45 39 233 128 20 77 100 41 73 3 64)
number of bits (  6  4  4   6   5  3  5   5  4  5 2  5)

哪里例如45 是 173 和 218 之间的差异，即第一和第二元素。这些数字需要 54 位，而上面需要 81 位。如果数字在绘制它们的范围内相当密集，您可能会看到第一个差异的最大位低于数据，使您能够使用较小的固定位长度。如果您不使用固定大小，您还必须存储分隔符或使用其他一些自适应方案，以便您可以确定一个数字从哪里停止，下一个数字从哪里开始。如果您的数据有大量重复，就像您的数字是从相对较小的范围内随机抽取一样，您也可以查看 run length encoding第一个差异中的零点。