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章“信息论的要素”。

希望这可以帮助!