存储大量大整数的最节省空间的方式

Question

我有大量非常大的整数（一般来说，大于

unsigned long long

），例如

976790216313803691633662
213166167
12361374472474414331778521
74143614714316467475274141141343747437542416477224365045416
...
46247285274316436417475827426432634528582016257012061846140147206
7287516801860168175715895175371357381735188912758511

我想将其存储在文件中。最节省空间的存储方法是什么？我尝试了几种方法，包括转换为字节并存储在

h5

文件中，使用

.npz

存储为

numpy

，但我得到的最大压缩是将它们存储在纯文本中，然后制作

.tar.gz

文件。

是否有更好的方法（即可以提供更好的压缩）？每个文件可能包含 10^4 到 10^12 行。

Answer 1

如果我们不考虑数字的实际值并假设完美熵，则根据提供的样本，我们会得到以下观察结果：

• 所有数字均为无符号整数。
• 最大数字可以用215位表示。

我们可以设想一种编码方案，使用 8 位来表示每个数字的长度（以位为单位），然后是该数字的实际位。

对于提供的样品：

976790216313803691633662
213166167
12361374472474414331778521
74143614714316467475274141141343747437542416477224365045416
46247285274316436417475827426432634528582016257012061846140147206
7287516801860168175715895175371357381735188912758511

我们得到以下位长度：

80
28
84
196
215
173

这总计为

776

位。添加

48

位来编码每个数字的长度（即

6 * 8

位），以获得总共

824

位或

103

字节。

比较：

• 上述方法：

  103

  字节
• 常规 gzip 压缩：

  144

  字节
• Tar/gzip 压缩为文件，文件名为

  n

  ：

  249

  字节