有理数向量的比特编码

Question

我想为具有合理数字的结构实现超紧凑存储。

在Alexander Schrijver的“线性和整数规划理论”一书中，我找到了rational number，vector和matrix的位大小定义（第15页）：

有理数的表示是明确的：符号的单个位和商和分数的对数。

我无法弄清楚如何仅在n位中编码矢量来区分其元素？例如，如果我想写两个元素的向量：524 = 1000001100b，42 = 101010b。我怎样才能使用2个额外的位来指定1000001100何时结束和101010何时开始？

矩阵表示存在同样的问题。

Answer 1

当然，不可能只是将整数表示相互附加，并添加有关合并位置的信息，因为这将比书中的公式所给出的更多位，我无权访问。 我认为这是编码理论中的一个问题，我不是专家。但我找到了一些可能指向正确方向的东西。在this post中，描述了“插值代码”。如果你将它应用到你的例子（524,42），你得到 f（要编码的整数的数量，全部在[1，N] = 2的范围内 N = 524 那么编码的2个整数的最大比特长度就是 f•（2.58 + log（N / f））= 9,99 ......，即10位 因此，可以具有超紧凑编码，尽管必须花费大量时间进行编码和解码。

Answer 2

只有两位才能指定商结束和分数何时开始。至少你需要与商的长度或/和分数大小的长度一样大。另一种方法是使用与IEEE 754类似的商和分数的固定位数。