3

所以我正在实现一个连分数库来处理二次整数和有理数的子集。连分数项由无符号整数表示。在处理连分数时，我注意到以下一般模式：

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

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

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

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

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

更新

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

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

4

5 回答 5

2

一种可能性是简单的前缀代码，其中二进制数 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) （稍微挥手，因为字母表是无限的）。

于 2015-08-21T21:37:10.797 回答
2

您的发行版似乎适合Rice Coding。您可以根据您的数据调整编码参数，我们称之为k。编码采用数字的低k位以上的位，并传输那么多 1 位，然后是 0。然后直接传输低k位。

于 2015-08-22T02:30:14.783 回答
1

您可以使用算术编码，将每个正整数视为源字母表中的一个符号。无限多并不重要，因为越来越大的整数的相对概率下降到零。

实际上，考虑到[0,1)上的均匀分布，可以将连分数展开式中每个新整数a_n（即熵源中的每个新符号）的条件概率设置为P(a_n = k) = 1 /k - 1/(k+1)。您可能需要考虑第一个整数来理解为什么这个条件概率是有意义的（区间 [0,1）中的一半数字将具有 a_1 = 1，其中六分之一是 a_1 = 2，等等）。

此外，您可能需要使用每个新符号翻转算术编码的方向，以便解码是明确的。不幸的是，算术编码/解码速度不是很快。

于 2016-09-29T17:24:27.263 回答
1

您可能会考虑删除连分数，而是实现它们的突变表亲：continuous logarithms。有关基本算术的讨论和实现，请参见该论文的最底部。

甚至还有一个硬件实现，用于在连续对数上进行大量并行算术，具有与 FFT 相同的渐近复杂度，但要简单得多，因此常数要低得多。

如果您正在寻找比仅由可逆 {+,-,*,/} 运算符构建的更奇特的东西，请参阅我关于 floor 运算符的新问题。

正如您所看到的，对于非常大的整数或非常小的分数，连分数往往会在术语位大小上爆炸。这种大项与小项的振荡是您在任何压缩方案中都需要利用的。

另一方面，正如比尔·戈斯珀（Bill Gosper）在那篇论文中所说，连续对数以一种“递归科学记数法”将大项分开。每个术语协同例程仅发出或消耗非常小的消息，这些消息可以以自然的游程编码序列化形式形成，描述“剩余待描述数字的以 2 为基数的对数”。

使用这种连续对数的不幸副作用是 Hurwitz 数是无模式的，而在连续分数中却非常有规律。然而，大多数（但不是全部）二次曲线仍然是周期性的，这也可以被认为是一种压缩方案。

一旦采用紧凑的游程编码格式，您就可以使用传统的压缩技术来运行小数字，例如 Mark Ransom 在问题评论中描述的 LZW。

于 2017-11-11T23:35:12.040 回答
0

另一种可能性是使用某种“通用编码”方案。由于随机选择的连分数很少有很大的部分商，通用编码应该很有用。

于 2018-11-16T15:18:44.853 回答