Подтвердить что ты не робот

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

Недавно я столкнулся с одной приятной проблемой, которая оказалась так же просто понять, как трудно найти какой-либо способ решения. Проблема заключается в следующем:

Напишите программу, которая считывает текст с ввода и печатает некоторые другие программа на выходе. Если мы скомпилируем и запустим печатную программу, она должна выводить исходный текст.

Входной текст должен быть довольно большим (более 10000 символов).

Единственное (и очень сильное) требование состоит в том, что размер архива (т.е. напечатанная программа) должен быть строго меньше, чем размер исходного текста. Это делает невозможными очевидные решения, такие как

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

Я считаю, что здесь нужно использовать некоторые методы архивирования.

4b9b3361

ОТВЕТЫ

Ответ 1

К сожалению, такой программы не существует.

Чтобы понять, почему это так, нам нужно сделать немного математики. Во-первых, пусть подсчитывает, сколько бинарных строк имеет длину 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 с короткими bitstring без присвоения по меньшей мере двух бит-строк длины-n для одной и той же более короткой строки. Это означает, что независимо от того, насколько сильно мы стараемся, независимо от того, насколько мы умны, и каким бы креативным мы ни сталкивались с нашим алгоритмом сжатия, существует жесткий математический предел, в котором говорится, что мы не можем сделать текст короче.

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

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

Для дальнейшего чтения существует понятие из теории информации, называемой колмогоровская сложность, которая представляет собой длину самой маленькой программы, необходимой для создания заданного строка. Некоторые строки легко сжимаются (например, abababababababab), а другие - нет (например, sdkjhdbvljkhwqe0235089). Существуют строки, которые называются несжимаемыми строками, для которых строка не может быть сжата в любое меньшее пространство. Это означает, что любойпрограмма, которая будет печатать эту строку, должна быть не меньше длины данной строки. Для хорошего ознакомления с сложностью Колмогорова вы можете взглянуть на главу 6 "Введение в теорию вычислений, второе издание" Майкла Сипсера, в которой есть отличный обзор некоторых более холодных результатов. Для более тщательного и углубленного изучения рассмотрите раздел "Элементы теории информации", глава 14.

Надеюсь, это поможет!

Ответ 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 цента, потому что все чувствовали, что это невозможно сделать, будучи уверенным в этом.

Реальная проблема в вашей проблеме заключается в понимании проблемы и требований.

Ответ 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;

Ответ 4

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

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

Ответ 5

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