编写一个程序，它接受文本作为输入，并生成一个能够重现该文本的程序。

Question

编写一个程序，它接受文本作为输入，并生成一个能够重现该文本的程序。

c++algorithmcompressionlossless-compression

35

最近我遇到了一个很好的问题，这个问题看起来很简单，但是找到解决方案却很困难。问题如下：

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

输入文本应该相当大（超过10000个字符）。

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

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

我相信这里需要使用一些存档技术。

- Grigor Gevorgyan

这是奎因概念的一种变体。 - Brian Kelly

1

“text”是什么意思？是指[A-Z][a-z][一些标点符号]*吗？ - Dr. belisarius

5

你可以从国会图书馆开始，多次通过这个程序，并最终得到一个几行代码的程序，可以复制整个图书馆。你感觉到自己的眉毛有一根在动吗？ - Beta

3

如果你将“Text”定义为“键盘上可打印的字符”，那么@Aasmund Eldhuset的解决方案就可以正常工作，但是如果“Text”表示的是值在0到255之间的字节数组，则这是不可能的，因为根据您的要求，“归档的大小（即程序打印的）必须严格小于原始文本的大小。”，因为我可以制作一个10000字节的不可压缩文件。 - Scott Chamberlain

1

这可能是一个很好的代码高尔夫候选项。 - crazy2be

显示剩余8条评论

5个回答

9

如果我们谈论ASCII文本...

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

这里的人们说字符串无法压缩，但它可以。

为什么？

要求：输出原始文本

文本不是数据。当您读取输入文本时，您读取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）不感兴趣。您可以使用不同的存储和检索机制（二进制模式）压缩输入字节，因为您不必返回原始数据而是原始文本。您可以重新计算存储的值的含义并将其调整为要打印的字节。您实际上只会失去非文本数据，因此无法打印或输入。如果WinZip这样做，那将是一个大失败，但对于您所述的要求，这根本不重要。

由于要求规定文本为10000个字符，如果您的打包没有任何损失，您可以节省255个中的26个，因此有效节省约10%的空间，这意味着如果您可以在1000（10000的10%）个字符中编写“解压缩”代码，则可以实现该目标。您必须将10个字节的组视为11个字符，并从中推断出第11个字符，通过某种外推方法来处理您的229个范围。如果可以完成这项工作，则问题是可以解决的。

然而，这需要巧妙的思考和实际能够在1千字节内完成的编码技能。

当然，这只是一个概念性答案，而不是一个功能性答案。我不知道我是否能够实现这一点。

但是，我有冲动在这个问题上发表我的意见，因为每个人都认为它无法完成，而且非常确定。

您问题的真正问题在于理解问题和要求。

- Marino Šimić

8

你所描述的基本上是一个用于创建自解压缩zip存档的程序，与常规的自解压缩zip存档不同的是，它会将原始数据写入到stdout而不是文件中。如果你想自己制作这样的程序，有许多压缩算法的实现可供选择，或者你可以自己实现例如DEFLATE（gzip使用的算法）。"外部"程序必须压缩输入数据并输出用于解压缩的代码，并将压缩后的数据嵌入到该代码中。

伪代码：

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;

- Aasmund Eldhuset

@Tomalak Geret'kal：现在是的 :-) - Aasmund Eldhuset

当然，“使用gzip”是回答这个问题的最佳答案了吧？ :) - Jack V.

0

假设“字符”意味着“字节”，并且假设输入文本可能包含至少与编程语言一样多的有效字符，对于所有输入来说这是不可能的，因为正如templatetypedef所解释的那样，对于任何给定长度的输入文本，所有“严格较小”的程序本身都是可能的具有更小长度的输入，这意味着可能的输入比输出永远多。（通过使用一个以“如果这是1，则以下内容只是未经编码的输入，因为它无法进一步压缩”的编码方案，可以安排输出最多比输入长一个位）

假设只要能够处理大多数输入（例如，主要由ASCII字符组成而不是可能的字节值的全部范围），那么答案就已经存在：使用gzip。这就是它擅长的。没有什么能够更好。您可以创建自解压存档，或将gzip格式视为“语言”输出。在某些情况下，通过拥有完整的编程语言或可执行文件作为输出，您可能会更高效，但通常，通过使用专为此问题设计的格式，即gzip，可以更高效地减少开销。

- Jack V.

0

它被称为文件归档程序，可以生成自解压缩的归档文件。

- Frigo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

很遗憾，这样的程序并不存在。

要了解为什么会这样，我们需要进行一些数学计算。首先，让我们来计算长度为n的二进制字符串的数量。每个位可以是0或1，这给了我们每个位两个选择。由于每个位有两个选择且共有n个位，因此长度为n的二进制字符串的总数为2ⁿ 。

现在，假设我们想构建一个压缩算法，它总是将长度为n的二进制字符串压缩成长度小于n的二进制字符串。为使其工作，我们需要计算出长度小于n的不同字符串的数目。嗯，这就是长度为0、长度为1、长度为2等等，一直到n-1位的二进制字符串的数量之和。这个总数是：

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

通过一些数学运算，我们可以得出这个数字等于2ⁿ - 1。换句话说，长度小于n的二进制字符串的总数比长度为n的二进制字符串的总数少一个。

但这是一个问题。为了有一种无损压缩算法，它总是将长度为n的字符串映射到长度不超过n-1的字符串,我们需要有某种方式将长度为n的每个二进制串关联至一些更短的二进制串, 使得没有两个长度为n的二进制串与同一短二进制串相关联。这样，我们就可以通过将其映射到相关联的较短字符串来压缩字符串，并通过反转映射来解压缩字符串。没有两个长度为n的二进制串映射到相同的较短二进制串的限制是使其无损的原因 - 如果两个长度为n的二进制串映射到相同的较短字符串，则在解压缩字符串时将无法知道我们压缩了哪个原始二进制串。

这就是我们遇到的问题所在。由于长度为n的二进制串有2ⁿ种不同的可能性，而只有2ⁿ-1个长度较短的二进制串，因此我们没有办法将每个长度为n的二进制串与某个较短的二进制串配对，而不将至少两个长度为n的二进制串分配给相同的较短二进制串。这意味着，无论我们多么努力，不管我们有多聪明，也不管我们对压缩算法采取多么创造性的方法，都存在一种严格的数学限制，表明我们不能总是使文本变得更短。

那么这如何与您最初的问题相对应呢？嗯，如果我们获得了一个长度至少为10000的文本字符串，并需要输出一个较短的程序来打印它，则我们必须有某种方式将长度为10000的2¹⁰⁰⁰⁰个二进制串映射到长度小于10000的2¹⁰⁰⁰⁰-1个二进制串。该映射具有其他属性，即我们始终需要生成有效的程序，但这在这里并不重要 - 简单地说，没有足够的较短字符串可用。结果，您想解决的问题是不可能的。

话虽如此，我们可能能够编写一个程序，将长度为10000的字符串中除一个以外的所有字符串都压缩成较短的字符串。实际上，我们可能会发现一种压缩算法可以做到这一点，这意味着长度为10000的任何字符串在概率 1-2¹⁰⁰⁰⁰ 的情况下都可以被压缩。这是一个非常高的概率，如果我们在整个宇宙的寿命里不断地挑选字符串，我们基本上几乎不可能猜出那一个无法被压缩的坏字符串。

更进一步阅读，信息理论有一个叫作科尔莫戈洛夫复杂度的概念，它代表生成某个给定字符串所需的最小程序长度。有些字符串很容易被压缩（例如abababababababab），而其他一些则不行（例如sdkjhdbvljkhwqe0235089）。存在一些被称为无法压缩的字符串，对于这些字符串，它们不可能被压缩到更小的空间。这意味着任何输出该字符串的程序都必须至少与给定字符串一样长。要了解科尔莫戈洛夫复杂度的基本概念，可以参考Michael Sipser的《计算理论导论（第二版）》第6章，其中有一些很棒的综述。如果想要更深入、严谨地研究该主题，可以阅读《信息论基础》的第14章。

希望这能有所帮助！