使用压缩方案压缩2位数字并节省1位

Question

我想为2位数字创建一个压缩方案，使任何序列的大小至少减少一位。我怎样才能证明这是不可能的？

Answer 1

有4个可能的双比特数和3个可能的较短比特序列（空比特序列以及序列0和1）。根据鸽子洞原理，这意味着从两个比特序列到较短序列的任何映射都必须至少有两个序列被压缩到同一较短序列。因此，当你想解压缩这个较短的序列时，你将无法做到这一点，因为你不知道它来自原始的两位序列中的哪一个。

这可以概括为表明n比特序列不能无损压缩为长度小于n的比特序列。这个早期的答案详细说明了为什么会这样。

希望这能有所帮助！