algorithm - 表示无限长度数字的最佳方法？

Question

表示无限长度整数的最佳（空间效率）方法是什么？

（数字范围从零到正无穷）

可以在此处找到一些示例编号输入（每个编号都显示在其自己的行上）。

是否有专门用于压缩数字的压缩算法？

Answer 1

对于可变长度整数，您基本上有两种选择：

1. 使用每个的 1 位k作为结束终止符。例如，Google protobuf 就是这样做的（在他们的例子中，每个字节有一个位，所以每个字节中有 7 个有用的位）。

2. 先输出位长，再输出位。这就是 ASN.1 的工作原理，除了以表格 1 表示的 OID。

如果数字真的很大，选项 2 会更好，虽然它更复杂，你必须递归地应用它，因为你可能必须输出长度的长度，然后是长度，然后是数字。一种常见的技术是对长度字段使用选项 1（位标记）。

对于较小的数字，选项 1 更好。考虑大多数数字适合 64 位的情况。每个字节存储 7 位的开销是 1/7；用 8 个字节表示 56 位。即使使用 7/8 表示长度也将表示 8 个字节中的 56 位：一个长度字节和七个数据字节。任何小于 48 位的数字都将受益于自终止代码。

平均而言，无限长度的“真正随机数”是无限长的，所以这可能不是你所拥有的。更有可能的是，您对数字大小的概率分布有所了解，并且可以在上述选项之间进行选择。

请注意，这些“压缩”都不是（相对于臃肿的 ascii 十进制格式除外）。的渐近线log n/n为 0，因此随着数字变大，数字大小的大小往往不占用（相对）空间。但它仍然需要以某种方式表示，所以总表示总是比数字的 log ₂大一点。

Answer 2

您本身无法压缩，但您可以编码，这可能是您正在寻找的。您的文件包含由换行符分隔的 ASCII 十进制数字序列。您应该简单地对字符进行 Huffman 编码。你不会比每个字符大约 3.5 位做得更好。