32位/64位正简单分数的最优编码方案咨询

针对正既约分数的唯一编码需求，以下是几种可行且高效的编码/解码方案，均能解决重复存储问题，且逆向还原算法的时间复杂度在合理范围内：

1. Calkin-Wilf树编码法 #

Calkin-Wilf树是一棵包含所有正既约分数的二叉树，每个分数唯一对应一个节点，节点编号可作为编码值，具备O(log n)的编码/解码效率。

编码过程（分数→编号） #

从目标分数a/b出发，重复执行以下步骤直到分数变为1/1：

• 若a > b，则编号累加b，同时更新a = a - b
• 若a < b，则编号累加a，同时更新b = b - a
  最终得到的累加值即为该分数的唯一编码（可自定义起始编号，比如1/1对应0）。

解码过程（编号→分数） #

从初始分数1/1和给定编号n出发，重复执行以下步骤直到n变为0：

• 若当前分数为a/b，且n >= b，则n -= b，同时更新a += b
• 否则，n -= a，同时更新b += a
  最终得到的a/b就是解码后的既约分数。

2. Stern-Brocot树编码法 #

Stern-Brocot树同样覆盖所有正既约分数，且分数按大小顺序排列，编码基于连分数展开，将系数转换为压缩格式存储，解码时通过连分数还原分子分母。

编码过程 #

将既约分数a/b展开为连分数形式：a/b = q0 + 1/(q1 + 1/(q2 + ... + 1/qk))，其中q0,q1,...,qk为正整数。把这些系数按顺序用变长编码或固定位段存入32/64位空间（比如用高位标记系数位数）。

解码过程 #

从连分数系数反向计算分子分母：

• 初始分子num = qk，分母den = 1
• 从倒数第二个系数往前遍历：num = qi * num + den，den = 原num值
• 最后处理q0：num = q0 * num + den，得到的num/den即为既约分数。

该方案优势是编码与分数大小顺序相关，适合需要有序遍历的场景。

3. 质因数分解编码法 #

利用既约分数分子、分母互质的特性，将两者分别分解为质因数乘积，用位段存储各质因数的指数，实现无重复编码。

编码结构（以32位为例） #

• 分配固定位段给常见小质数（如2、3、5、7等），每个质数分配2-4位存储指数（足够覆盖大部分简单分数）
• 剩余位段用于存储大质数的指数（变长编码），或标记是否存在更大质数（扩展位）

编码过程 #

1. 对分子a分解质因数：a = 2^e2 * 3^e3 * 5^e5 * ...
2. 对分母b分解质因数：b = 2^f2 * 3^f3 * 5^f5 * ...（同一质数的指数不会同时出现在分子分母）
3. 将各质数的指数按位段存入存储空间，分子、分母的指数通过位位置区分（比如奇数位存分子指数，偶数位存分母）

解码过程 #

1. 从位段中提取各质数的指数
2. 分别计算分子、分母的质因数乘积，得到既约分数a/b

该方案解码直观，适合需要直接操作质因数的场景，对小质因数组成的简单分数编码非常紧凑。

方案对比 #

• Calkin-Wilf树：编码/解码速度最快，无需额外存储，适合通用场景
• Stern-Brocot树：支持有序遍历，适合需按分数大小排序的场景
• 质因数分解：解码直观，适合需操作质因数的业务场景

内容的提问来源于stack exchange，提问作者Amae Saeki