35

最近我遇到了一个很好的问题,它看起来很容易理解,但很难找到任何解决方法。问题是:

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

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

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

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

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

4

5 回答 5

54

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

要了解为什么会这样,我们需要做一些数学运算。首先,让我们计算一下有多少个长度为 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 的位串与一些较短的位串配对,而无需将至少两个长度为 n 的位串分配给相同的较短的位串细绳。这意味着无论我们多么努力,无论我们多么聪明,无论我们的压缩算法多么有创意,都有一个严格的数学限制,即我们不能总是让文本变短。

那么这如何映射到您原来的问题呢?好吧,如果我们得到一个长度至少为 10000 的文本字符串并且需要输出一个较短的程序来打印它,那么我们必须有某种方法将 2 10000 个长度为 10000 的字符串中的每一个映射2 10000 - 1长度小于 10000 的字符串。该映射还有一些其他属性,即我们总是必须生成一个有效的程序,但这在这里无关紧要 - 根本没有足够的短字符串可供使用。结果,你想解决的问题是不可能的。

也就是说,我们也许可以得到一个程序,它可以将除一个长度为 10000 的字符串之外的所有字符串压缩为更短的字符串。事实上,我们可能会找到一种压缩算法来执行此操作,这意味着以 1 - 2 10000的概率可以压缩任何长度为 10000 的字符串。这是一个如此高的概率,如果我们在宇宙的整个生命周期中一直挑选弦,我们几乎肯定永远不会猜到一根坏弦。


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

希望这可以帮助!

于 2011-06-29T19:40:25.640 回答
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 (10% 10000) 个字符,您可以实现这一目标。您必须将 10 个字节的组视为 11 个字符,并从那里通过某种外推方法对 229 范围进行外推 te 11th。如果可以做到,那么问题是可以解决的。

然而,它需要聪明的思考,以及实际上可以在 1 KB 内完成的编码技能。

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

但我有冲动为此付出我的 2 美分,因为每个人都认为这是不可能做到的,因为对此非常确定。

你的问题中真正的问题是理解问题和需求。

于 2011-06-30T17:47:05.570 回答
8

您所描述的本质上是一个用于创建自解压 zip 存档的程序,与常规自解压 zip 存档将原始数据写入文件而不是标准输出的细微差别。如果您想自己制作这样的程序,有很多压缩算法的实现,或者您可以自己实现例如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;
于 2011-06-29T19:35:59.857 回答
0
  1. 假设“字符”表示“字节”,并假设输入文本可能包含至少与编程语言一样多的有效字符,则不可能对所有输入执行此操作,因为正如 templatetypedef 所解释的那样,对于任何给定长度的输入文本都“严格较小的”程序本身就是长度较小的可能输入,这意味着可能的输入多于输出。(通过使用以“如果这是 1,以下只是未编码的输入,因为它无法进一步压缩”位开头的编码方案,可以安排输出最多比输入长一位)

  2. 假设它足以对大多数输入进行这项工作(例如,主要由 ASCII 字符组成的输入,而不是可能的字节值的全部范围),那么答案很容易存在:使用 gzip。这就是它擅长的。没有什么会变得更好。您可以创建自解压档案,或将 gzip 格式视为“语言”输出。在某些情况下,通过使用完整的编程语言或可执行文件作为输出可能会更有效,但通常会通过为此问题设计的格式来减少开销,即。gzip,效率会更高。

于 2011-07-05T15:14:42.947 回答
0

它被称为生成自解压档案的文件存档器。

于 2011-08-13T01:11:11.957 回答