我有大量非常大的整数(一般大于unsigned long long
),例如
976790216313803691633662
213166167
12361374472474414331778521
74143614714316467475274141141343747437542416477224365045416
...
46247285274316436417475827426432634528582016257012061846140147206
7287516801860168175715895175371357381735188912758511
我想将其存储在文件中。存储它们最节省空间的方法是什么?我尝试了几种方法,包括转换为字节并存储在文件中,使用h5
存储,但我获得的最大压缩是将它们存储在纯文本中,然后制作文件的 。.npz
numpy
.tar.gz
有没有更好的方法(即哪种方法可以提供更好的压缩效果)?每个文件可能有 10^4 到 10^12 行。
编辑:您可以通过在 python 中运行以下命令来生成一个最小的可重现示例(这是首先获取数字列表的方式):
import numpy as np
def generate_int(n):
return int(str(np.random.randint(1, 10)) + ''.join([str(np.random.randint(0, 10)) for _ in range(n-1)]))
output = [generate_int(np.random.randint(4, 1001)) for _ in range(1000000)]
12
最佳答案
2
如果我们不考虑数字的实际值并假设完全熵,我们将根据提供的样本得出以下观察结果:
- 所有数字都是无符号整数。
- 最大的数字可以用 215 位来表示。
然后我们可以设想一种编码方案,使用 8 位来表示每个数字的长度,后面跟着数字的实际位。
对于提供的示例:
976790216313803691633662
213166167
12361374472474414331778521
74143614714316467475274141141343747437542416477224365045416
46247285274316436417475827426432634528582016257012061846140147206
7287516801860168175715895175371357381735188912758511
我们得到以下位长度:
80
28
84
196
215
173
这加起来就是总位数776
。加上这些48
位数,对每个数字的长度(6 * 8
即位)进行编码,得到总824
位数,即103
字节数。
为了比较:
- 上述原始位方法:
103
字节 - 基于文本的方法,使用常规
gzip
压缩文件内容:144
字节
(cat n | gzip > n.gz
) - 基于文本的方法使用
tar
/gzip
压缩文件:249
字节
(tar -czvf n.tar.gz n
)
12
-
1那是忽略的。这些数字比
...
生成的数字小得多。话虽如此,即使大小为 2 个字节(这是 mre 代码的绝对最大值:最多 1000 个十进制数字,因此最多 3322 位),甚至通过将整数位四舍五入到高 8 位以简化实现,对于此示例,这仍然只有 111 个字节。
– -
1@chrslg 是的,我忽略了,
...
因为我认为它被用作“更多数据”的指标。当我写答案时,最小可重现示例并不存在。再说一遍:我根据当时可用的数据回答了“最节省空间的存储方式…”的问题。不是最实用的方式,不是最容易实现的方式,也不是可以推断出所有在写作时未知的数据的方式。
–
-
1话虽如此,只需添加所需的位数即可表达最大位长度,这可能仍然是最有效的答案。存储字节将导致平均每个数字损失 4 位,而您只需要 3 个额外的位 (2^3=8) 来表达位长度而不是字节长度。
–
-
2@chrslg 不,当然可以做得更好。例如,从每个数字中去掉前 1 位。那里有 100 万位。您可以将长度表示为前缀代码而不是 16 位,从而节省 400 多万位。
– -
1@chrslg 12. 4096 是 12 位。如果你想要准确的话。
–
|
可能的值范围从 1000 到 10 1000 -1。这些值可以用 10 到 3326 位表示,始终以 1 为前导位。我们将省略前导 1,因此每个数字将由 9..3325 位表示。
每组比特前面都会有一个表示比特数的前缀码。可能的比特数有 3317 种,其中前 779 个比特将被编码为 11 个比特,其余 2538 个比特将被编码为 12 个比特。平均每个比特为 11.765 个比特。每个比特后面都会跟着 9..3325 个比特,平均为 1667 个比特。
那么,一百万个这样的数字的完整序列将平均编码为 1678765150 位,即 209845644 字节。(如果以字节为单位编码,最后几位将被检测为不完整的 11..12 位计数代码,并被丢弃。)总长度将在这些平均值附近变化约 ±0.06% 1σ。
|
–
–
random
比 numpy 更快。numpy random 更适合生成整个 numpy dtype 值数组。如果你真的想要大整数,那就远离 numpy。–
–
–
|