Напишите программу, которая принимает текст в качестве входных данных и создает программу, которая воспроизводит этот текст

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. Ну, это дается числом битовых строк длины 0, плюс количество битовых строк длины 1, плюс количество битовых строк длины 2 и т. Д., Вплоть до n - 1. Это общее значение равно

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

Используя немного математики, мы можем получить, что это число равно 2 ⁿ - 1. Другими словами, общее число цепочек битов длиной меньше n на единицу меньше числа цепочки битов длиной n.

Но это проблема. Чтобы у нас был алгоритм сжатия без потерь, который всегда отображает строку длины n в строку длиной не более n - 1, нам нужно было бы каким-то образом связать каждую цепочку битов длины n с какой-то более короткой цепочкой битов, так что нет две строки битов длины n связаны с одним и тем же более коротким потоком битов. Таким образом, мы можем сжать строку, просто сопоставив ее с соответствующей более короткой строкой, и мы можем распаковать ее путем обращения отображения. Ограничение, заключающееся в том, что никакие две цепочки битов длины n не отображаются в одну и ту же более короткую строку, делает эту потерю без потерь - если две цепочки бит длины-n должны отображаться в одну и ту же более короткую цепочку битов, то когда придет время распаковывать строку, не будет быть способом узнать, какие из двух исходных цепочек битов мы сжимали.

Здесь мы достигаем проблемы. Поскольку существует 2 ⁿ различных цепочек битов длины n и только 2 ⁿ -1 более коротких цепочек битов, нет никакого способа, которым мы можем связать каждую цепочку битов длины n с какой-то более короткой цепочкой бит без присвоение как минимум двух строк длины-n одной и той же более короткой строке. Это означает, что независимо от того, как сильно мы стараемся, какими бы умными мы ни были, и независимо от того, насколько мы креативны с нашим алгоритмом сжатия, существует жесткое математическое ограничение, которое говорит о том, что мы не всегда можем сделать текст короче.

Так как эта карта связана с вашей первоначальной проблемой? Что ж, если мы получим строку текста длиной не менее 10000 и нам понадобится вывести более короткую программу, которая ее печатает, то нам нужно будет каким-то образом отобразить каждую из 2 ¹⁰⁰⁰⁰ строк длиной 10000. на строки 2 ¹⁰⁰⁰⁰ - 1 длиной менее 10000. Это отображение имеет некоторые другие свойства, а именно то, что мы всегда должны создавать допустимую программу, но это не имеет значения - здесь просто не хватает более коротких строк обойти В результате проблема, которую вы хотите решить, невозможна.

Тем не менее, мы могли бы получить программу, которая может сжимать все строки, кроме одной, длиной 10000 в более короткую строку. Фактически, мы могли бы найти алгоритм сжатия, который делает это, что означает, что с вероятностью 1 - 2 ¹⁰⁰⁰⁰ любая строка длиной 10000 может быть сжата. Это настолько высокая вероятность того, что если бы мы продолжали выбирать строки на протяжении всей жизни вселенной, мы почти наверняка никогда бы не догадались об одной плохой строке.

---

Для дальнейшего чтения есть понятие из теории информации под названием Колмогоровская сложность , которая является длиной самой маленькой программы, необходимой для создания данной строки. Некоторые строки легко сжимаются (например, abababababababab), а другие - нет (например, sdkjhdbvljkhwqe0235089). Существуют строки, которые называются несжимаемыми строками , для которых строка не может быть сжата в каком-либо меньшем пространстве. Это означает, что любая программа, которая будет печатать эту строку, должна иметь длину не менее указанной строки. Для хорошего знакомства с колмогоровской сложностью вы можете обратиться к главе 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 из 255, если ваша упаковкабез потерь вы эффективно экономите около 10% пространства, а это означает, что если вы можете закодировать «декомпрессию» в 1000 (10% из 10000) символов, вы сможете добиться этого.Вы должны будете обрабатывать группы из 10 байтов как 11 символов, и оттуда экстраполировать 11-е число некоторым методом экстраполяции для вашего диапазона 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;

Answer 4

Он называется файловым архиватором, производящим самораспаковывающиеся архивы.

Answer 5

1. Предполагая, что "символ" означает "байт", и предполагая, что входной текст может содержать как минимум столько же допустимых символов, сколько язык программирования, это невозможно сделать для всех входов,поскольку, как объяснил templatetypedef, для любой заданной длины входного текста все «строго меньшие» программы сами по себе являются возможными входными данными с меньшей длиной, что означает, что существует больше возможных входных данных, чем когда-либо может быть выходных данных.(Можно сделать так, чтобы выходные данные были не более чем на один бит длиннее, чем входные данные, используя схему кодирования, начинающуюся со слова «если это 1, то это просто некодированный вход, поскольку он не может быть сжат дальше»))

2. Если предположить, что этого достаточно для большинства входных данных (например, входных данных, которые состоят в основном из символов ASCII, а не из полного диапазона возможных значений байтов), то ответ легко существует:используйте gzip.Это то, что хорошо.Ничто не будет намного лучше.Вы можете создавать самораспаковывающиеся архивы или рассматривать формат gzip как «языковой» вывод.В некоторых случаях вы можете быть более эффективными, имея в качестве выходных данных полный язык программирования или исполняемый файл, но часто уменьшая накладные расходы, имея формат, разработанный для этой проблемы, т.е.gzip, будет более эффективным.