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

Question

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

假设String是一个字符串，f(var)一个返回压缩版本的压缩函数var，g(var)一个解压缩函数，g(f(var)) = var以及strlen(var)一个返回长度的函数var，是否存在
有效值？Stringstrlen(String) < strlen(f(String))strlen(String) = strlen(f(String))

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

Answer 1

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

---

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

Answer 2

我希望这个字符串符合要求：“”

Answer 3

是的，原因很简单：例如，一个保证返回无损压缩字符串的函数，对于任何输入字符串，该字符串至少会少一点。是否存在这样的函数，然后通过一次又一次地将相同的函数重新应用于其先前的结果，我们保证每次通过时至少进一步连续压缩任何字符串，因此，我们保证能够无损压缩任何任何长度的字符串，每次只有一位。

显然，这是错误的（一些初始字符串可能会给出这样的最终结果，并且很容易发现它们正在将解压缩算法应用于长度为一位的压缩字符串，但该结果不能扩展到所有未压缩的字符串），因此，这样的功能不可能存在；这意味着对于任何压缩算法，至少存在一个不可压缩的字符串。