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

Question

表示无限长度整数的最佳(节省空间)方式是什么？

(数字范围从零到正无穷)

可以找到一些样本编号输入 here (每个数字都显示在它自己的行上)。

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

Answer 1

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

1. 使用每个 k 的 1 位作为结束符。例如，Google protobuf 就是这样做的(在他们的例子中，每个字节一位，因此每个字节中有 7 个有用位)。

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

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

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

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

请注意，这些都不是“压缩”的(除了相对于臃肿的 ascii-decimal 格式)。 log n/n 的渐近线为 0，因此随着数字变大，数字的大小趋向于不占据(相对)空间。但它仍然需要以某种方式表示，因此总表示总是比数字的 log₂ 大一点。