我需要在一个文件中存储大量整数。整数的顺序无关紧要，所以总信息量应该低于有序列表。有没有比任意排序的数组更节省空间的方法来存储数字？
编辑：我假设整数是完全随机的。我真的在寻找一种通用的方法来挤出通过修复排列引入的冗余信息。
问问题
316 次
3 回答
3
要进行压缩，您实际上需要更高的信息内容。您通常不能压缩随机性。幸运的是，您的问题规范允许您重新排序数据。因此，您可以对数据进行排序，从而增加其信息量。然后，您不需要存储整数列表，只需存储最小的和一阶差分的序列。第一个差异将小于数字本身，因此应该适合更少的位。
排序后的随机生成序列
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 位。如果数字在绘制它们的范围内相当密集，您可能会看到第一个差异的最大位数低于使您能够使用更小的固定位长度的数据。如果您不使用固定大小，您还必须存储分隔符或使用其他一些自适应方案，以便您可以确定一个数字在哪里结束，下一个数字从哪里开始。如果您的数据有大量重复项（如果您的数字是从相对较小的范围内随机抽取的），您可能还需要考虑对第一个差异中的零进行编码的游程长度。
于 2013-01-28T01:23:14.950 回答
1
一般来说，我会说不。如果您的数字有某种模式或以某种单一方式分布，那么您应该提及它。
于 2013-01-27T20:43:42.213 回答
0
本文正是这样做的。
用大字母压缩多重集
论文：https ://arxiv.org/abs/2107.09202
代码：https ://github.com/facebookresearch/multiset-compression
于 2021-10-21T19:37:49.213 回答