最有效的方法是编码0到64之间的2个位置？

Question

我想通过利用中间某处只有一部分包含数据以及之前和之后为零的事实来压缩64位值。

假设实际数据是l位长并填充前面的n 0和末尾的m 0s，使得n + l + m = 64.我可以发送l位加上任何I而不是发送/存储64位需要以64位的间隔编码数据的位置。

例如，假设我存储了l，m和数据位，那么我将通过读取l，读取l位数据，读取m并将数据m位向左移位来恢复原始的64位模式。

我能想到的最小开销是两次6位，用于存储l，n和m中的两个（每个可以在0到64之间）。是否可以减少这个数字？

Answer 1

l可以是0到64，所以不要发送l，发送n和m，因为它们都可以为零，并且不需要达到64（它们只需要能够添加到64）。

l位必须以1开始和结束，因此不需要传输它们。

为n
发送6位 为m发送最多6位（见下文）
计算l = 64 - （n + m）
如果l = 0，则数字为0，不发送任何其他内容 如果l = 1，数字是1 * 2 ^ m，请不要发送任何其他内容 如果l = 2，数字是3 * 2 ^ m，请不要发送任何其他内容 发送中间l - 2位。

最大开销= 10位。

m的位数减少是因为
如果n <！> gt; 32然后你知道m <！> lt; 32，所以只需要5位
如果n <！> gt; 48然后你知道m <！> lt; 16，所以只需要4位
如果n <！> gt; 56然后你知道m <！> lt; 8，所以只需要3位
如果n <！> gt; 60然后你知道m <！> lt; 4，所以只需要2位
如果n = 63那么你知道m <！> lt; 2，所以只需要1位

Answer 2

您的分析听起来适合单一的声音。但是如果你将许多这样的值一起传输，像gzip这样的通用熵编码算法可能会做得更好，因为它可以很好地消除零字符串，并且还可以利用数据中的冗余。

Answer 3

正如你已经说明了这个问题，不管你提出的解决方案是否能做得更好。

但是，如果数字中零的分布有偏差，则通过使用霍夫曼代码或类似技术来表示计数，您可以平均获得更好的压缩效果。如果零分布从一个64位值与下一个64位值强相关，则另一种可能性是使用增量编码。

在任何一种情况下，您都需要使用可变数量的位来表示零的数量。如果你对偏斜或相关性的假设结果是假的，你可能最终会使用平均比使用简单方法更多的位。

Answer 4

你的解决方案看起来很不错。
霍夫曼编码是另一种压缩价值的方法，尤其是在频率很高的情况下。

实现它并不是很困难，但如果您没有太多数据要传输，可能会非常困难。

Answer 5

64 <1>序列的n可能的起始位置l，序列的长度64 - n不能再log2(2081) = 11.023。有一个

r = sum(n = 0..63, 64 - n) + 1

总计序列。添加的是一个全零序列。做一些数学会产生以下结果。

r = 64 * 64 - (63 * 64) / 2 + 1
  = 2081

表示2081个可能的值需要6位。因此，您建议使用两个总共需要12位的<=>位编码对信息进行编码是最佳的（假设所有可能值的分布均等）。