有理数向量的位编码
Bit encoding for vector of rational numbers
我想为有理数结构实现超紧凑存储。
在Alexander Schrijver的书"Theory of Linear and Integer Programming"中，我找到了rational number、向量和矩阵的位大小（第15页）的定义：
有理数的表示很清楚：符号是一位，商和分数是对数。
我不明白向量如何只用 n 位编码来区分它的元素？
例如，如果我想写两个元素的向量怎么办：
524 = 1000001100b、42 = 101010b。如何仅使用 2 个附加位来指定 1000001100 结束和 101010 开始的时间？
矩阵表示也存在同样的问题。
不可能只用两位来指定商结束和小数开始的时间。至少你需要和商的长度 or/and 一样大的分数大小的长度。另一种方法是对商和分数使用固定位数，类似于 IEEE 754.
当然，不可能仅仅将整数表示相互附加，并添加有关合并位置的信息，因为这将比书中公式给出的位数多得多，我不知道无法访问。
我相信这是我不是专家的编码理论的问题。但我发现了一些可能会为您指明正确方向的东西。在 this post 中描述了一个 "interpolative code"。如果将它应用于您的示例 (524, 42)，您会得到
f（要编码的整数个数，都在[1,N] = 2
范围内
N = 524
编码后的2个整数的最大位长为
f • (2.58 + log (N/f)) = 9,99…，即 10 位
因此，有可能进行超紧凑编码，尽管编码和解码需要花费大量时间。
我想为有理数结构实现超紧凑存储。
在Alexander Schrijver的书"Theory of Linear and Integer Programming"中，我找到了rational number、向量和矩阵的位大小（第15页）的定义：
有理数的表示很清楚：符号是一位，商和分数是对数。
我不明白向量如何只用 n 位编码来区分它的元素？
例如，如果我想写两个元素的向量怎么办：
524 = 1000001100b、42 = 101010b。如何仅使用 2 个附加位来指定 1000001100 结束和 101010 开始的时间？
矩阵表示也存在同样的问题。
不可能只用两位来指定商结束和小数开始的时间。至少你需要和商的长度 or/and 一样大的分数大小的长度。另一种方法是对商和分数使用固定位数，类似于 IEEE 754.
当然，不可能仅仅将整数表示相互附加，并添加有关合并位置的信息，因为这将比书中公式给出的位数多得多，我不知道无法访问。
我相信这是我不是专家的编码理论的问题。但我发现了一些可能会为您指明正确方向的东西。在 this post 中描述了一个 "interpolative code"。如果将它应用于您的示例 (524, 42)，您会得到
f（要编码的整数个数，都在[1,N] = 2
范围内
N = 524
编码后的2个整数的最大位长为
f • (2.58 + log (N/f)) = 9,99…，即 10 位
因此，有可能进行超紧凑编码，尽管编码和解码需要花费大量时间。