使用压缩方案压缩2位数字并节省1位
使用压缩方案压缩2位数字并节省1位
提问于 2013-02-16 10:46:31
我想为2位数字创建一个压缩方案，这样就可以将任何序列的大小减少至少一位。我如何证明这是不可能的？
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-02-16 10:52:03
有4个可能的2比特数和3个可能的更短的比特序列(空的比特序列以及序列0和1)。通过pigeonhole principle，这意味着从两位序列到短序列的任何映射都必须将至少两个序列压缩成相同的短序列。因此，当您想要解压缩这个较短的序列时，您将无法这样做，因为您将不知道它来自原始的两位序列中的哪一个。
这可以推广到表明n比特序列不能无损地压缩成长度小于n的比特序列。This earlier answer详细说明了为什么会这样。
希望这能有所帮助！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14906396
复制相关文章
相似问题
腾讯云开发者
