c++ - 编写一个程序，将文本作为输入并生成一个复制该文本的程序

Question

最近，我遇到了一个不错的问题，它变得简单易懂，很难找到解决方法。问题是:

Write a program, that reads a text from input and prints some other program on output. If we compile and run the printed program, it must output the original text.

输入的文本应该很大(超过10000个字符)。

唯一(而且非常强烈)的要求是归档文件(即打印的程序)的大小必须比原始文本的大小严格小于。这使得不可能的显而易见的解决方案，例如

std::string s;
/* read the text into s */
std::cout << "#include<iostream> int main () { std::cout<<\"" << s << "\"; }";

我相信这里将使用一些归档技术。

Answer 1

不幸的是，这样的程序不存在。

要了解为什么会这样，我们需要做一些数学运算。首先，让我们计算一下有多少个长度为n的二进制字符串。每个位可以是0或1，这使我们可以为每个位提供两个选择之一。由于每位和n位有两个选择，因此总共有2n个长度为n的二进制字符串。

现在，让我们假设我们要构建一个压缩算法，该算法始终将长度为n的位串压缩为长度小于n的位串。为了使它起作用，我们需要计算长度小于n的不同字符串的数目。好吧，这是由长度为0的位串的数量，加上长度为1的位串的数量，加上长度为2的位串的数量，依此类推，一直到n-1。

2⁰ + 2¹ + 2² + ... + 2^{n - 1}

通过一点数学运算，我们可以得出此数字等于2n-1。换句话说，长度小于n的位串的总数比长度n的位串的总数小一个。

但这是一个问题。为了使我们拥有一种无损压缩算法，该算法始终将长度为n的字符串映射到长度最大为n-1的字符串，我们必须采用某种方式将长度为n的每个位串与一些较短的位串相关联，以使长度为n的两个位串与相同的较短位流相关联。这样，我们可以通过仅将字符串映射到关联的较短字符串来压缩字符串，并且可以通过反转映射来对其进行解压缩。没有两个长度为n的位串映射到相同的较短字符串的限制使得此方法无损-如果两个长度为n的位串映射到相同的较短的字符串，那么当需要解压缩字符串时，就不会知道我们压缩过的两个原始位串中的哪一个。

这是我们遇到的问题。由于存在2n个长度为n的不同位串，而只有2n-1个较短的位串，因此我们不可能将长度n的每个位串与一些较短的位串配对，而不必为同一较短的串分配至少两个length-n位串。这意味着，无论我们多么努力，无论我们多么聪明，以及我们通过压缩算法获得的创意如何，都存在一个严格的数学极限，即我们不能总是使文本变短。

那么这如何映射到您的原始问题？好吧，如果我们得到的字符串长度至少为10000，并且需要输出一个较短的程序来打印该字符串，那么我们将不得不采用某种方式将长度为10000的210000个字符串中的每一个映射到210000-1个字符串中长度小于10000。该映射具有其他一些属性，即我们总是必须生成一个有效的程序，但这与这里无关紧要-根本就没有足够短的字符串来处理。结果，您要解决的问题是不可能的。

就是说，我们也许能够获得一个程序，该程序可以将长度为10000的字符串(除了其中之一)压缩为较短的字符串。实际上，我们可能会找到执行此操作的压缩算法，这意味着以1-210000的概率可以压缩任何长度为10000的字符串。这是一个很高的可能性，如果我们在整个宇宙的生命周期中不断选择弦，我们几乎肯定不会猜到一个坏弦。

为了进一步阅读，信息理论中有一个称为Kolmogorov complexity的概念，它是产生给定字符串所需的最小程序的长度。有些字符串很容易压缩(例如abababababababab)，而有些则不是(例如sdkjhdbvljkhwqe0235089)。存在称为incompressible strings的字符串，对于该字符串，可能无法将其压缩到任何较小的空间中。这意味着任何将打印该字符串的程序都必须至少与给定的字符串一样长。有关Kolmogorov复杂度的一个很好的介绍，您可能需要看Michael Sipser撰写的“计算理论入门，第二版”的第6章，其中对一些较酷的结果进行了很好的概述。有关更严格和深入的研究，请考虑阅读第14章“信息论的要素”。

希望这可以帮助!