压缩2位数并保存1位使用压缩方案

我想创建一个2位数的压缩方案，以便它将任何序列的大小减少至少一位。我怎样才能证明这是不可能的？压缩2位数并保存1位使用压缩方案

2013-02-16 benji_r

当然可以将尺寸减小一位。什么是不可能的是无损地逆转过程。 – 2013-02-16 04:37:13

有4个可能的2位数和3个可能的较短位序列（空序列位和序列0和1）。通过pigeonhole principle，这意味着从两位序列到较短序列的任何映射必须具有至少两个序列被压缩到相同的较短序列。因此，当你想解压这个较短的序列时，你将无法做到这一点，因为你不知道它来自哪个原始的两位序列。

这可以概括为显示n比特序列不能被无损地压缩成长度小于n的比特序列。 This earlier answer详细说明了这是为什么。

希望这会有所帮助！

2013-02-16 02:52:03 templatetypedef

你的意思是“...必须至少有两个序列被压缩成同一个较短的序列”，我想。（很显然，任何人都已经知道这个论点，但对新读者来说可能并不明显。） – Nemo 2013-02-16 03:18:40

@ Nemo-谢谢！固定。 – templatetypedef 2013-02-16 07:02:05

嘿家伙非常感谢你的答案 – 2013-02-16 19:57:31

回答