language-agnostic - 是否存在不可压缩的字符串？

Question

关闭。这个问题是off-topic .它目前不接受答案。












想改善这个问题吗？ Update the question所以它是 on-topic对于堆栈溢出。

8年前关闭。




Improve this question




我想知道是否有一个或多个字符串不能进行无损压缩。更正式的:

让 String是一个字符串，f(var)一个压缩函数，它返回 var 的压缩版本, g(var)一个解压函数，使得 g(f(var)) = var和 strlen(var)返回 var 长度的函数,String 是否有有效值？使得 strlen(String) < strlen(f(String))或 strlen(String) = strlen(f(String)) ?

欢迎提供理论答案，以及不同语言和不同压缩算法的示例。

Answer 1

pigeonhole principle告诉我们对于任何给定的压缩函数*，必须始终至少有一个将被扩展的输入字符串。

* 即真正压缩至少一个输入字符串的函数。