使用较少位的无符号 qword(64 位)的值范围?

Value range of unsigned qword (64-Bits) using less bits?

我正在寻找一种表示以下值范围的方法: 0 - 18446744073709551615 使用少于 8 个字节。

我试过想一些方法可以做到,但没有任何效果。 理论上,例如: 用一个字节来表示至少2个字节的位序列。 然而,2个字节有65536个不同的位组合,而一个字节只给我们0-255的取值范围(256种组合)。

最好的方法可能是更改位的含义。那会很好,但不能有任何精度损失。

我开始认为这根本不可能,尽管我想听听其他人对这个问题的看法和理论。

有两条规则: #1 不能有任何精度损失(即所有数字 0 - 18446744073709551615 必须是可表示的)。 #2 标准 64 位格式的转换永远不会导致需要超过 7 个字节(56 位)。

这些规则使这变得特别困难。

these rules make this particularly hard.

是的,很难证明是不可能的。

如果您可以将 每个 可能的 64b 值的 8 个字节无损压缩到少于 8 个字节,您可以继续重复该过程,直到您的 1TB 文件大约为 7 个字节。

还有许多其他信息论论据可以解释为什么这是不可能的。例如鸽巢原则:n 位只有 2^n 个独特的位模式,因此任何小于 64 位的东西都不能对每个可能的 64 位值都有唯一的表示。


您可以使用 Huffman coding 或类似的东西:如果某些 64b 值比其他值更常见,则不太复杂的可变长度编码方案可以节省总字节数。 但对于所有 64b 值都可以用可变长度编码方案表示,某些值的编码将占用超过 8 个字节。

存在更高级的熵编码方法,并用于现代视频编解码器。 (例如 x264 的 CABAC)。


关于更多理论,维基百科的无损压缩文章有 Limitations section

另请参阅: