编写一个将文本作为input的程序，并生成一个能够再现该文本的程序

最近我遇到了一个很好的问题，这个问题变得简单易懂，很难find解决办法。 问题是：

编写一个程序，从input中读取文本，并在输出上打印其他程序。 如果我们编译并运行打印的程序，它必须输出原文。

input文本应该是相当大的（超过10000个字符）。

唯一的（也是非常强大的）要求是档案的大小（即打印的程序）必须严格小于原始文本的大小。 这使得不可能明显的解决scheme

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

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

Answer 1

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

要知道为什么这样，我们需要做一些math。 首先，让我们计算一下长度为n的二进制string的数量。 每个比特可以是0或1，这给了我们每个比特的两个select之一。 由于每比特和n比特有两个select，所以总共有2 ^n个长度为^n的二进制string。

现在，我们假设我们要构build一个压缩algorithm，该algorithm总是将长度为n的位串压缩成长度小于n的位串。 为了这个工作，我们需要计算有多less不同的长度小于n的string。 那么这是由长度为0的位串的数目加上长度为1的位串的数目加上长度为2的位串的数目等一直到n – 1给出的。这个总数是

2 ⁰ + 2 ¹ + 2 ² + … + 2 ^{n – 1}

使用一些math运算，我们可以得到这个数字等于2 ⁿ – 1。换句话说，长度小于n的比特串的总数比长度为n的比特串的数目less一个。

但这是一个问题。 为了使我们有一个无损压缩algorithm，总是将一个长度为n的string映射到长度至多为n – 1的string，我们必须有一些方法将长度为n的每个位串与一些较短的位串关联起来，长度为n的两个比特串与相同的较短比特stream相关联。 这样，我们可以通过将它映射到关联的较短string来压缩string，并且可以通过反转映射来对其进行解压缩。 限制：没有两个长度为n的string映射到同一个较短的string是什么使得这个没有损失 – 如果两个长度为n的string映射到相同的较短的string，那么当需要解压缩string时，可以知道我们压缩的两个原始位串中的哪一个。

这是我们遇到问题的地方。 由于长度为n的2 ^n个不同的比特串和只有2 ⁿ -1个较短的比特串，所以我们不可能将长度为n的每个比特串与一些较短的比特串配对，而不将至less两个长度为n的比特串分配给同样短的串。 这意味着无论我们多努力，无论我们有多聪明，无论我们使用压缩algorithm有多创造力，都有一个严格的math限制，说我们不能总是缩短文本。

那么这是如何映射到你原来的问题呢？ 那么，如果我们得到一串长度至less为10000的文本，并且需要输出一个打印它的较短的程序，那么我们就必须有一些方法将^{10000个10000个}string中的每一个映射到2 ¹⁰⁰⁰⁰ – 1长度小于10000的string。这个映射还有其他一些属性，也就是说，我们总是需要生成一个有效的程序，但这里没有什么关系 – 只是没有足够的较短的string。 结果，你想解决的问题是不可能的。

也就是说，我们可能会得到一个程序，可以压缩除了一个长度为10000的string之外的一个string。 事实上，我们可能会发现一个压缩algorithm，这意味着以概率1 – 2 ¹⁰⁰⁰⁰可以压缩任何长度为10000的string。 这个概率很高，如果我们在宇宙的一生中继续选弦，那么我们几乎肯定不会猜一个坏弦。

---

为了进一步阅读，有一个来自信息理论的概念叫做Kolmogorov复杂性 ，它是产生给定string所需的最小程序的长度。 一些string很容易被压缩（例如，abababababababab），而另一些则不是（例如，sdkjhdbvljkhwqe0235089）。 存在被称为不可压缩string的string ，为此string不可能被压缩到任何更小的空间中。 这意味着任何打印该string的程序都必须至less与给定的string一样长。 对于Kolmogorov复杂性的一个很好的介绍，你可能要看Michael Sipser的“Introduction to the Theory of Computation，Second Edition”的第6章，它对一些较酷的结果有很好的概述。 要更加严谨和深入地研究，请考虑阅读“信息理论元素”第14章。

希望这可以帮助！

Answer 2

如果我们正在谈论ASCII文本…

我认为这实际上是可以做到的，而且我认为文本大于10000字的限制是有原因的（给你编码室）。

这里的人们说这个string不能被压缩，但它可以。

为什么？

要求：输出原文

文本不是数据。 当你读取input文本时，你可以读取ASCII字符（字节）。 里面有可打印和不可打印的值。

以此为例：

 ASCII values characters 0x00 .. 0x08 NUL, (other control codes) 0x09 .. 0x0D (white-space control codes: '\t','\f','\v','\n','\r') 0x0E .. 0x1F (other control codes) ... rest of printable characters 

由于必须将文本输出为输出，因此对范围（0x00-0x08,0x0E-0x1F）不感兴趣。 您可以使用不同的存储和检索机制（二进制模式）来压缩input字节，因为您不必原始数据而是原始文本。 您可以重新计算存储的值的含义，并将其重新调整为打印字节。 你将只能有效地释放非文本数据的数据，因此不能打印或input。 如果WinZip会这样做，这将是一个很大的失败，但是对于你所说的要求，这根本就没有关系。

由于要求规定，文本是10000个字符，你可以节省26个255，如果你的包装没有任何损失，你有效地节省了大约10％的空间，这意味着如果你可以编码“解压缩”1000（10％ 10000）字符，你可以实现这一点。 你将不得不把10字节的组作为11个字符，从那里推断te 11，通过一些外推法，你的范围是229.如果可以这样做，那么问题是可以解决的。

然而，它需要聪明的思维和编程技巧，实际上可以做到1千字节。

当然，这只是一个概念性的答案，而不是function性的答案。 我不知道我能否做到这一点。

但是我有这个想法，就是要给我两分钱，因为大家都觉得这是不可能完成的，因为对此确定无疑。

在你的问题真正的问题是理解问题和要求。

Answer 3

你所描述的实质上是一个用于创build自解压zip压缩文件的程序，它与普通的自解压zip压缩文件将原始数据写入文件而不是stdout的区别很小。 如果你想自己制作一个这样的程序，有很多压缩algorithm的实现，或者你可以自己实现例如DEFLATE （gzip使用的algorithm）。 “外部”程序必须压缩input数据并输出解压缩代码，并将压缩数据embedded到该代码中。

伪代码：

 string originalData; cin >> originalData; char * compressedData = compress(originalData); cout << "#include<...> string decompress(char * compressedData) { ... }" << endl; cout << "int main() { char compressedData[] = {"; (output the int values of the elements of the compressedData array) cout << "}; cout << decompress(compressedData) << endl; return 0; }" << endl; 

Answer 4

1. 假设“字符”的意思是“字节”，并假设input文本可能包含至less与编程语言一样多的有效字符，则不可能对所有input执行此操作，因为如templatetypedef所解释的，对于任何给定长度的input文本，较小的“程序本身是可能的，具有较小长度的input，这意味着有比输出更多的可能的input。 （可以通过使用以“如果这是1”开始的编码scheme来安排输出最多比input长一个比特，下面只是未编码的input，因为它不能被进一步压缩“位）

2. 假设它对于大多数input（例如，主要由ASCII字符组成的input而不是全部可能的字节值）有足够的function，那么答案很容易存在：使用gzip。 这就是它擅长的。 没有什么会好多了。 您可以创build自解压文件，也可以将gzip格式视为“语言”输出。 在某些情况下，通过使用完整的编程语言或可执行文件作为输出，您可能会更有效率，但通常通过为此问题devise一种格式来减less开销。 gzip，会更有效率。

Answer 5

它被称为文件归档器，生成自解压文件。