有理数向量的位编码

Question

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

在Alexander Schrijver的《线性和整数规划理论》一书中，我找到了有理数、向量和矩阵的位大小的定义（第15页） ：

有理数的表示很清楚：符号用一位表示，商和分数用对数表示。

我不明白如何仅以n位对向量进行编码以区分其元素？例如，如果我想写两个元素的向量： 524 = 1000001100b, 42 = 101010b. 如何仅使用 2 个附加位来指定何时1000001100结束和101010开始？

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

Answer 1

当然，不可能仅仅将整数表示形式相互附加，并添加有关合并位置的信息，因为这将比书中公式给出的位数多得多，而我无权访问该公式到。
\n我相信这是编码理论中的一个问题，我不是专家。但我发现一些东西可能会为你指明正确的方向。在这篇文章中，描述了“插值代码”等。如果将其应用到您的示例 (524, 42)，您将得到
\nf （要编码的整数的数量，全部在 [1,N] = 2 范围内
\nN = 524
\n编码 2 的最大位长度整数则为
\nf \xe2\x80\xa2 (2.58 + log (N/f)) = 9,99\xe2\x80\xa6，即 10 位
\n因此，可以进行超紧凑编码，尽管有花费大量时间进行编码和解码。

\n