最近，我遇到了一个不错的问题，它变得简单易懂，很难找到解决方法。问题是：
编写一个程序，该程序从输入中读取文本并在输出上打印一些其他程序。如果我们编译并运行打印的程序，它必须输出原始文本。
输入的文本应该很大（超过10000个字符）。
唯一（而且非常强烈）的要求是存档（即打印的程序）的大小必须 严格小于 原始文本的大小。这使不可能的显而易见的解决方案，例如
std::string s; /* read the text into s */ std::cout << "#include<iostream> int main () { std::cout<<\"" << s << "\"; }";
我相信这里将使用一些归档技术。
不幸的是，这样的程序不存在。
要了解为什么会这样，我们需要做一些数学运算。首先，让我们计算一下有多少个长度为n的二进制字符串。每个位可以是0或1，这给我们提供了每个这些位的两个选择之一。由于每位和n位有两个选择，因此总共有2 n个长度为n的二进制字符串。
现在，让我们假设我们要构建一种压缩算法，该算法始终将长度为n的位串压缩为长度小于n的位串。为了使它起作用，我们需要计算长度小于n的不同字符串的数目。好吧，这是由长度为0的位串的数目，加上长度为1的位串的数目，加上长度为2的位串的数目，依此类推，一直到n-1。
2 0 + 2 1 + 2 2 + … + 2 n-1
通过一点数学运算，我们可以得出这个数字等于2 n -1。换句话说，长度小于n的位串的总数比长度n的位串的总数少一个。
但这是一个问题。为了使我们拥有一种无损压缩算法，该算法始终将长度为n的字符串映射到长度为n-1的字符串，我们必须采用某种方式将长度为n的每个位串与一些较短的位串相关联，这样长度为n的两个位串与相同的较短位流相关联。这样，我们可以通过将字符串映射到关联的较短字符串来压缩字符串，并可以通过反转映射来解压缩字符串。没有两个长度为n的位串映射到相同的较短字符串的限制使得此方法无损- 如果两个长度为n的位串映射到相同的较短的字符串，那么当需要解压缩字符串时，就不会知道我们压缩过的两个原始位串中的哪一个。
这是我们遇到的问题。由于存在2 n个长度为n的不同位串，而只有2 n -1个较短的位串，因此我们不可能将长度n的每个位串与一些较短的位串配对，而不必为相同的较短的位串分配至少两个length- n位串串。这意味着，无论我们多么努力，无论我们多么聪明，以及我们通过压缩算法获得的创意如何，都存在一个严格的数学极限，即我们不能总是使文本变短。
那么这如何映射到您的原始问题？那么，如果我们得到至少10000长度的文本和需要输出的字符串更短的程序，打印出来，那么我们就必须有各2个映射的一些方法10000长度10000串到2 10000 - 1长度小于10000的字符串。该映射还具有其他一些属性，即我们总是必须生成一个有效的程序，但这与这里无关紧要- 根本就没有足够的短字符串来处理。结果，您要解决的问题是不可能的。
就是说，我们也许能够获得一个程序，该程序可以将长度为10000的字符串以外的所有字符串压缩为较短的字符串。实际上，我们可能会找到执行此操作的压缩算法，这意味着以1-2 10000的概率可以压缩任何长度为10000的字符串。这是一个很高的可能性，如果我们在整个宇宙的生命周期中不断选择弦，我们几乎肯定不会猜到一个坏弦。
为了进一步阅读，信息理论中有一个称为Kolmogorov复杂度的概念，它是产生给定字符串所需的最小程序的长度。有些字符串很容易压缩（例如abababababababab），而有些则不是（例如sdkjhdbvljkhwqe0235089）。存在称为不可压缩字符串的字符串，对于该字符串，可能无法将其压缩到任何较小的空间中。这意味着 任何 打印该字符串的程序必须至少与给定的字符串一样长。有关Kolmogorov复杂度的一个很好的介绍，您可能需要看Michael Sipser撰写的“计算理论入门，第二版”的第6章，其中对一些较酷的结果进行了很好的概述。有关更严格和深入的研究，请考虑阅读第14章“信息论的要素”。
希望这可以帮助！
