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

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

该鸽巢原理告诉我们,对于任何给定的压缩功能^*,必须始终有至少一个输入字符串,将扩大.

_{*即真正压缩至少一个输入字符串的函数.}