0

我想为 2 位数字创建一个压缩方案，以便它将任何序列的大小减少至少一位。我如何证明这是不可能的？

4

1 回答 1

3

有 4 个可能的两位数和 3 个可能的较短位序列（空位序列以及序列 0 和 1）。根据鸽巢原理，这意味着从两位序列到较短序列的任何映射都必须至少将两个序列压缩为相同的较短序列。结果，当您想解压缩这个较短的序列时，您将无法这样做，因为您不知道它来自哪个原始两位序列。

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

希望这可以帮助！

于 2013-02-16T02:52:03.297 回答