algorithm - 连续分数项的良好压缩方案？

Question

所以我正在实现 continued fraction处理 quadratic integers 子集的库和 rational numbers .连分数项由无符号整数表示。在处理连分数时，我注意到以下一般模式:

1. 大多数术语都是小的个位数，最常见的是 1。
2. 有些术语可能很大，对我的应用程序来说最大可能是 366 位，但这种情况极为罕见。
3. 大项表示特别好的数字近似值，这意味着对于大的分数，总体上通常较少的项。
4. 可能最差的连分数是黄金比例，其 366 位精度的有理近似值大约对应于连续 525 个 1。
5. 随机有理数通常不会有大量相同的数，但可能有两到四个连续的数，其中 1 也是最常见的。

所以我对术语的数量和术语的大小都有限制，术语的数量与它们的大小大致成反比。所以将这些术语存储在机器字甚至字节中通常非常浪费空间，而且在最坏的情况下我仍然需要处理多字运算。鉴于项的大小和项的数量之间的大致反比关系(两者也取决于分数的分子和分母的大小)，我一直在努力寻找或想出一个好的压缩方案，这样我就不会浪费这么多空间存储整数项。

我考虑过 Huffman encoding ，因为编码和解码的速度很好，但我不确定如何得出代码值的概率。我有一个模糊的直觉 Stern-Brocot Trees可能会提供提示，因为它们是 binary trees与连分数有直接关系。

有没有人知道一种很好的压缩方法来处理大量的小数字和偶尔的大数字，其中相同数字的运行通常很短(但在极少数情况下可能很长)？特别是我需要能够相当快地编码和解码(比如 O(n*lg(n)) 是我可以容忍的绝对最差速度，O(n) 或更好)，并且能够获得各个术语的位置，以便我知道我在处理哪个术语(第四个术语、第五个术语等)。

此外，我对使用任何第三方实数库或连分数库不感兴趣。我看过几个，但它们要么不足以满足我的需求，要么有点矫枉过正，我想要自己编写代码以供自己启迪的经验。

更新

我还了解到 Gauss–Kuzmin distribution对于均匀分布在 0 和 1 之间的随机数，它给出了 k 的特定连分数项的概率分布。它是

P(k) = -lg(1.0 - 1.0/((k + 1.0)**2) 在 Python 伪代码中，其中 lg 是以 2 为底的对数。这是极限因为 k 接近无穷大，所以我的情况有点受限(尽管 2**366 仍然很大)。Linas Vepstas 的“The Entropy of Continued Fractions”给出了(信息) Gauss-Kuzmin 分布的熵大约为 3.43 位。我的最大分母足够大，以至于我的连分数的信息熵可能接近该极限，尽管链接文章中的图表显示接近极限的速度非常缓慢，因此有所不同对于相对较小的分母。

Answer 1

一种可能性是一个简单的前缀代码，其中二进制数 1x 的位 x 编码为 0 -> 10 和 1 -> 11，后跟终止符 0。

表格:

1 -> 0
2 -> 100
3 -> 110
4 -> 10100
5 -> 10110
6 -> 11100
7 -> 11110
8 -> 1010100

此处 n 对应的霍夫曼编码概率类似于 Theta(1/n^2)(稍微挥动我的手，因为字母表是无限的)。