如何压缩一系列非重复数字大小的N位？

Question

我试图压缩一系列非负数,其中:

• 每个数字的取值范围为0到2 ^ N-1

• 每个号码只出现一次(这意味着总共有2 ^ N个号码)

  N = 4的示例:

  [14,1,8,2,12,6,0,10,4,13,5,7,15,9,3,11]

因此通常每个数字将花费4位,对于16个数字,我们将不得不使用16x4 = 64位来存储它们.

目前我刚想到压缩它们如下:

• 对于前8个数字 - >使用4位来存储它们中的每一个.
• 对于接下来的4个数字--->每个只有3位
• 对于接下来的2个数字--->每个只有2位
• 对于接下来的1个数字--->只有1位.
• 对于最后一个,实际上并不需要存储(显然,如果我们知道所有其他15个数字,我们应该知道最后一个数字是什么)

所以压缩的数据大小将是:

Z = 8 * 4 + 4 * 3 + 2 * 2 + 1 * 1 + 1 * 0 = 49 bits 

压缩率约为76%,这是相当不错的(我认为).

但是对于较大的N值,该比率似乎会降低(对于N = 2048,该比率仅为91%)

所以我想听听你有关更好压缩的建议.

谢谢.

Answer 1

正如评论中指出的那样，最佳编码（如果所有排列的可能性相同）是将整个排列替换为其在排列枚举中的索引。因为有n 个！可能的排列，索引需要 log ₂ n ! 位，因此对每个元素使用 log ₂ n位的朴素编码的压缩比是 (log n !)/( n log n )。

使用斯特林近似，我们可以将其重写为 ( n log n - n + O(log n ))/( n log n )，即 1 - 1/(log n ) + O(1/ n ) ，显然渐近逼近1 随着n 的增长。因此， n越大，压缩比下降是不可避免的。

除非并非所有排列都具有相同的概率（并且您有一些有关概率分布的信息），否则不可能实现更好的压缩。