连续分数项的良好压缩方案？
Good compression scheme for continued fraction terms?
所以我正在实施 continued fraction library for handling a subset of quadratic integers and rational numbers。连分数项由无符号整数表示。在处理连分数时，我注意到以下一般模式：
- 大多数术语都是小的个位数，最常见的是 1。
- 有些术语可能很大，我的应用程序最大可能是 366 位，但这种情况极为罕见。
- 大项表示特别好的数字近似值，这意味着对于大的分数，总体上通常较少的项。
- 最差的连分数可能是黄金比例，其 366 位精度的有理近似值大约对应于连续 525 个 1。
- 随机有理数通常不会有大量相同的数，但可能有两到四个连续的数，其中 1 也是最常见的。
所以我对术语的数量和术语的大小都有限制，术语的数量与它们的大小大致成反比。所以用机器字甚至字节来存储这些术语通常是非常浪费space，而且在最坏的情况下我仍然需要处理多字运算。鉴于项的大小和项的数量之间的大致反比关系（两者也取决于分数的分子和分母的大小），我一直在努力寻找或想出一个好的压缩方案，这样我就不会浪费这么多 space 存储整数项。
我考虑过 Huffman encoding, as the speed of encoding and decoding is nice, but I'm not sure how to come up with the probabilities for the code values. I have a vague intuition that Stern-Brocot Trees might offer a hint, as they are binary trees 与连分数有直接关系。
有谁知道处理大量小数字和偶尔出现大数字的好压缩方法，其中相同数字的运行通常很短（但在极少数情况下可能很长）？特别是我需要能够相当快地编码和解码（比如 O(n*lg(n)) 是我可以容忍的绝对最差速度，O(n) 或更好），并且能够获得各个术语的位置，以便我知道我正在操作的术语编号（第四个术语、第五个术语等）。
此外，我对使用任何第三方实数或连分数库不感兴趣。我看过几个，但它们要么不足以满足我的需求，要么有点矫枉过正，我想要自己编写代码以供自己启迪的经验。
更新
我还了解到 Gauss–Kuzmin distribution 它给出了 k 的特定连分数项的概率分布，该随机数在 0 和 1 之间均匀分布。它是
P(k) = -lg(1.0 - 1.0/((k + 1.0)**2) in Python 伪代码，其中 lg 是以 2 为底的对数。这是 k 接近无穷大的极限，所以我的情况有点受限（尽管 2**366 仍然很大）。 Linas Vepstas 的“The Entropy of Continued Fractions”给出了 Gauss-Kuzmin 分布的（信息）熵大约为 3.43 位。我的最大分母足够大，以至于我的连分数的信息熵可能接近该限制，尽管链接文章中的图表显示接近该限制的速度非常缓慢，因此对于相对较小的分母来说是不同的。
一种可能性是简单的前缀代码，其中二进制数 1x 的位 x 编码为 0 -> 10 和 1 -> 11，后跟终止符 0。
Table:
1 -> 0
2 -> 100
3 -> 110
4 -> 10100
5 -> 10110
6 -> 11100
7 -> 11110
8 -> 1010100
此处 n 对应的霍夫曼编码概率类似于 Theta(1/n^2)（挥动我的手，因为字母表是无限的）。
您的发行版似乎适合 Rice Coding。您可以根据您的数据调整编码参数，我们称它为 k。编码采用低 k 位以上的数字位，并传输那么多 1 位，后跟 0。然后传输低 k直接位。
您可以使用 arithmetic encoding 将每个正整数视为源字母表中的一个符号。无限多并不重要，因为越来越大的整数的相对概率降为零。
实际上，考虑[0,1)上的均匀分布，可以在连分数展开中设置每个新整数a_n的条件概率a_n(即来自熵源的每个新符号）为 P(a_n = k ) = 1/k - 1/(k+1)。您可能需要考虑第一个整数来理解为什么这个条件概率有意义（区间 [0,1] 中的一半数字将 a_1 = 1，其中六分之一 a_1 = 2 等）。
此外，您可能需要用每个新符号翻转算术编码的方向，以便解码是明确的。不幸的是，算术 en/decoding 不是很快。
您可以考虑放弃连分数，而是实现它们的变异表亲：continued logarithms。有关基本算术的讨论和实现，请参阅该论文的最底部。
甚至还有一个 hardware implementation 用于连续对数的大规模并行运算，具有与 FFT 相同的渐近复杂性，但更简单，因此常数要低得多。
如果您正在寻找比可逆 {+,-,*,/} 运算符更奇特的东西，请参阅我的 new question on the floor operator。
如您所见，对于非常大的整数或非常小的分数，连分数在项位大小方面往往会爆炸。这种大项与小项的振荡是您在任何压缩方案中都需要利用的。
另一方面，正如 Bill Gosper 在该论文中提出的那样，连续对数以 'recursive scientific notation,' 的形式拆分大项。每个术语协同例程仅发出或消耗非常小的消息，这些消息可以以自然的 运行 长度编码序列化形式形成，描述 'log base 2 of the number remaining to be described.'
不幸的是，使用这种连续对数的副作用是 Hurwitz 数没有规律，而连续分数非常规则。然而，大多数（但不是全部）二次函数仍然是周期性的，这也可以被认为是一种压缩方案。
一旦采用紧凑的 运行 长度编码格式，您就可以对 运行 的小数字使用传统的压缩技术，例如 Mark Ransom 在问题评论中描述的 LZW。
另一种可能性是使用某种"Universal Encoding" 方案。由于随机选择的连分数很少有很大的偏商，通用编码应该很有用。
所以我正在实施 continued fraction library for handling a subset of quadratic integers and rational numbers。连分数项由无符号整数表示。在处理连分数时，我注意到以下一般模式：
- 大多数术语都是小的个位数，最常见的是 1。
- 有些术语可能很大，我的应用程序最大可能是 366 位，但这种情况极为罕见。
- 大项表示特别好的数字近似值，这意味着对于大的分数，总体上通常较少的项。
- 最差的连分数可能是黄金比例，其 366 位精度的有理近似值大约对应于连续 525 个 1。
- 随机有理数通常不会有大量相同的数，但可能有两到四个连续的数，其中 1 也是最常见的。
所以我对术语的数量和术语的大小都有限制，术语的数量与它们的大小大致成反比。所以用机器字甚至字节来存储这些术语通常是非常浪费space，而且在最坏的情况下我仍然需要处理多字运算。鉴于项的大小和项的数量之间的大致反比关系（两者也取决于分数的分子和分母的大小），我一直在努力寻找或想出一个好的压缩方案，这样我就不会浪费这么多 space 存储整数项。
我考虑过 Huffman encoding, as the speed of encoding and decoding is nice, but I'm not sure how to come up with the probabilities for the code values. I have a vague intuition that Stern-Brocot Trees might offer a hint, as they are binary trees 与连分数有直接关系。
有谁知道处理大量小数字和偶尔出现大数字的好压缩方法，其中相同数字的运行通常很短（但在极少数情况下可能很长）？特别是我需要能够相当快地编码和解码（比如 O(n*lg(n)) 是我可以容忍的绝对最差速度，O(n) 或更好），并且能够获得各个术语的位置，以便我知道我正在操作的术语编号（第四个术语、第五个术语等）。
此外，我对使用任何第三方实数或连分数库不感兴趣。我看过几个，但它们要么不足以满足我的需求，要么有点矫枉过正，我想要自己编写代码以供自己启迪的经验。
更新
我还了解到 Gauss–Kuzmin distribution 它给出了 k 的特定连分数项的概率分布，该随机数在 0 和 1 之间均匀分布。它是
P(k) = -lg(1.0 - 1.0/((k + 1.0)**2) in Python 伪代码，其中 lg 是以 2 为底的对数。这是 k 接近无穷大的极限，所以我的情况有点受限（尽管 2**366 仍然很大）。 Linas Vepstas 的“The Entropy of Continued Fractions”给出了 Gauss-Kuzmin 分布的（信息）熵大约为 3.43 位。我的最大分母足够大，以至于我的连分数的信息熵可能接近该限制，尽管链接文章中的图表显示接近该限制的速度非常缓慢，因此对于相对较小的分母来说是不同的。
一种可能性是简单的前缀代码，其中二进制数 1x 的位 x 编码为 0 -> 10 和 1 -> 11，后跟终止符 0。
Table:
1 -> 0
2 -> 100
3 -> 110
4 -> 10100
5 -> 10110
6 -> 11100
7 -> 11110
8 -> 1010100
此处 n 对应的霍夫曼编码概率类似于 Theta(1/n^2)（挥动我的手，因为字母表是无限的）。
您的发行版似乎适合 Rice Coding。您可以根据您的数据调整编码参数，我们称它为 k。编码采用低 k 位以上的数字位，并传输那么多 1 位，后跟 0。然后传输低 k直接位。
您可以使用 arithmetic encoding 将每个正整数视为源字母表中的一个符号。无限多并不重要，因为越来越大的整数的相对概率降为零。
实际上，考虑[0,1)上的均匀分布，可以在连分数展开中设置每个新整数a_n的条件概率a_n(即来自熵源的每个新符号）为 P(a_n = k ) = 1/k - 1/(k+1)。您可能需要考虑第一个整数来理解为什么这个条件概率有意义（区间 [0,1] 中的一半数字将 a_1 = 1，其中六分之一 a_1 = 2 等）。
此外，您可能需要用每个新符号翻转算术编码的方向，以便解码是明确的。不幸的是，算术 en/decoding 不是很快。
您可以考虑放弃连分数，而是实现它们的变异表亲：continued logarithms。有关基本算术的讨论和实现，请参阅该论文的最底部。
甚至还有一个 hardware implementation 用于连续对数的大规模并行运算，具有与 FFT 相同的渐近复杂性，但更简单，因此常数要低得多。
如果您正在寻找比可逆 {+,-,*,/} 运算符更奇特的东西，请参阅我的 new question on the floor operator。
如您所见，对于非常大的整数或非常小的分数，连分数在项位大小方面往往会爆炸。这种大项与小项的振荡是您在任何压缩方案中都需要利用的。
另一方面，正如 Bill Gosper 在该论文中提出的那样，连续对数以 'recursive scientific notation,' 的形式拆分大项。每个术语协同例程仅发出或消耗非常小的消息，这些消息可以以自然的 运行 长度编码序列化形式形成，描述 'log base 2 of the number remaining to be described.'
不幸的是，使用这种连续对数的副作用是 Hurwitz 数没有规律，而连续分数非常规则。然而，大多数（但不是全部）二次函数仍然是周期性的，这也可以被认为是一种压缩方案。
一旦采用紧凑的 运行 长度编码格式，您就可以对 运行 的小数字使用传统的压缩技术，例如 Mark Ransom 在问题评论中描述的 LZW。
另一种可能性是使用某种"Universal Encoding" 方案。由于随机选择的连分数很少有很大的偏商，通用编码应该很有用。