编写一个程序,将文本作为输入,并生成一个再现该文本的程序

Question

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

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

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

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

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

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

Answer 1

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

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

现在,让我们假设我们要构建一个压缩算法,该算法总是将长度为n的位串压缩为长度小于n的位串.为了使其工作,我们需要计算有多少不同的字符串长度小于n.好吧,这是由长度为0的位串数加上长度为1的位串数加上长度为2的位串数等等,一直到n-1.这个总数是

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

使用一些数学运算,我们可以得到该数字等于2 ⁿ -1.换句话说,长度小于n的位串总数比长度为n的位串数小1.

但这是一个问题.为了让我们有一个无损压缩算法,总是将长度为n的字符串映射到长度最多为n-1的字符串,我们必须有一些方法将长度为n的每个位串与一些较短的位串相关联,这样就不会长度为n的两个比特串与相同的较短比特流相关联.这样,我们可以通过将字符串映射到关联的较短字符串来压缩字符串,我们可以通过反转映射来解压缩字符串.没有长度为n的两个位串映射到相同的较短字符串的限制使得这种无损 - 如果两个长度为n的位串都映射到相同的较短位串,那么当需要解压缩字符串时,就不会是一种了解我们压缩的两个原始位串中的哪一个的方法.

这是我们遇到问题的地方.由于有2个^Ñ不同长度为n的位串和仅2 ^Ñ -1短位串,有我们可以用更短的一些位串配对长度为n的位串的每个不分配至少两个长度为N的位串的相同短没有可能的方式串.这意味着无论我们如何努力,无论我们多么聪明,无论我们使用压缩算法多么有创意,都有一个严格的数学限制,即我们不能总是缩短文本.

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

也就是说,我们可能能够获得一个程序,可以将除了一个长度为10000的字符串之外的所有字符串压缩为更短的字符串.事实上,我们可能会找到一种压缩算法,这意味着在概率为1 - 2 ^10000时,任何长度为10000的字符串都可以被压缩.这是一个很高的概率,如果我们在宇宙的整个生命周期中不断挑选字符串,我们几乎肯定不会猜到一个坏字符串.

为了进一步阅读,有一个名为Kolmogorov复杂度的信息理论概念,它是生成给定字符串所需的最小程序的长度.一些字符串很容易压缩(例如,abababababababab),而其他字符串则不容易(例如,sdkjhdbvljkhwqe0235089).存在称为不可压缩字符串的字符串,对于该字符串,字符串不可能被压缩到任何较小的空间中.这意味着任何打印该字符串的程序必须至少与给定字符串一样长.为了更好地介绍Kolmogorov Complexity,您可能需要查看Michael Sipser的"计算理论导论"第6章,该文章对一些较冷的结果有很好的概述.要想更加严谨和深入,请阅读"信息理论要素"第14章.

希望这可以帮助!

Answer 2

如果我们谈论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个字符,你可以节省26个中的26个,如果你的包装没有任何损失,你实际上可以节省大约10%的空间,这意味着如果你可以在1000中编码'减压'(10%) 10000)你可以实现的角色.您将不得不将10个字节的组视为11个字符,并从那里推断te 11th,通过229的范围的一些外推方法.如果可以做到那么问题是可解决的.

然而,它需要聪明的思维和编码技能,实际上可以在1千字节内完成.

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

但是我有冲动给我2美分,因为每个人都觉得无法做到这一点,因为我非常肯定.

问题中的真正问题是理解问题和要求.

Answer 3

你所描述的本质上是一个用于创建自解压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;