整数值的二进制编码方案的名称

Question

我曾经在维基百科找到一个很好的编码 $ k \ in（2 ^ {n-1}，2 ^ n）$ 统一分布式整数数字少于 $ \ log_2n $ 平均位/符号，谢谢易于计算可变长度代码。基本上它使用 $ \ log_2n $ 对于某些符号和 $ \ log_2n - 1 $ 对于其他一些符号。

不幸的是，我所有的歌曲都失败了。我记得类似于“可变长度二进制”的东西，但我一直在VLQ结束，这是一个不同的野兽。既然我比我的更好地了解你的记忆，你可以帮助我吗？

Answer 1

技术理念在Yuval Filmus答案中完美描述。即使略有不同，它也被称为截断二进制编码在维基百科。除了在专利之外，我找不到原始来源。，在这个 book ，或者在 google api

Answer 2

假设 $ k= 2 ^ {n-1} + t $ ，其中 $ 0 \ leq t <2 ^ {n-1} $ 。使用以下内容编码 $ z \ in \ {0，\ ldots，k-1 \} $ ：

• 如果 $ z <2 ^ {n-1} -t $ 然后编码 $ z $ 作为自己 $（n-1）$ -bit编码。
否则，写入 $ z= 2 ^ {n-1} -t + 2 \ delta + \ epsilon $ ，其中 $ \ delta \ in \ {0，\ ldots，t-1 \} $ 和 $ \ epsilon \ in \ {0,1 \} $ 。编码 $ z $ $（n-1）$ -bit编码 $ 2 ^ {n-1} -t + \ delta $ ，然后是 $ \ epsilon $ 。

这里是一个例子。让 $ k= 11= 2 ^ 3 + 3 $ 。编码如下：

• $ 0 \ 000 $ 。
• $ 1 \ to 001 $ 。
• $ 2 \到010 $ 。
• $ 3 \到011 $ 。
• $ 4 \到100 $ 。
• $ 5 \到1010 $ 。
• $ 6 \到1011 $ 。
• $ 7 \到1100 $ 。
• $ 8 \到1101 $ 。
• $ 9 \到1110 $ 。
• $ 10 \到1111 $ 。