Какая максимальная теоретически возможная степень сжатия?

Это теоретический вопрос, поэтому ожидайте, что многие детали здесь невозможно вычислить ни на практике, ни даже в теории.

Допустим, у меня есть строка s, которую я хочу сжать. Результатом должен быть самораспаковывающийся двоичный файл (может быть ассемблер x86, но также может быть какой-то другой гипотетический полный по Тьюрингу язык низкого уровня), который выводит s.

Теперь мы можем легко перебрать все возможные такие двоичные файлы и программы, отсортированные по размеру. Пусть B_s будет подсписком этих двоичных файлов, которые выводят s (конечно, B_s невычислимо).

Поскольку каждый набор положительных целых чисел должен иметь минимум, должна быть самая маленькая программа b_min_s в B_s.

Для каких языков (то есть набора строк) мы знаем что-то о размере b_min_s? Может быть, только оценка. (Я могу построить несколько тривиальных примеров, где я всегда могу даже вычислить B_s, а также b_min_s, но меня интересуют более интересные языки.)


compression
person Albert    schedule 16.07.2010    source источник
comment
Я вспоминаю некоторые очень умные программы из старины, такие как загрузчики начальной загрузки, которые перезаписывали себя несколько раз. Вероятно, чтобы достичь минимального общего размера самораспаковывающейся программы, программа могла бы каким-то образом использовать свой собственный текст - например, в качестве источника констант.   -  person Hot Licks    schedule 10.09.2011

Ответы (4)


arrow_upward
19
arrow_downward

Это колмогоровская сложность, и вы правы, что это не вычислимо. Если бы это было так, вы могли бы создать парадоксальную программу длины n, которая печатала бы строку с колмогоровской сложностью m> n.

Ясно, что вы можете привязать b_min_s для заданных входов. Однако, насколько мне известно, большинство попыток сделать это были доказательствами существования. Например, продолжается соревнование по сжатию английской Википедии.

person Matthew Flaschen    schedule 16.07.2010
comment
Да, именно этот приз подтолкнул меня к этому вопросу. :) Однако такие соревнования / попытки дают только указания, потому что они показывают более низкие пределы для конкретной строки примера. Они не дают никакого ответа о среднем / реальном жестком ограничении какого-либо данного языка (например, XML с грамматически правильным английским в качестве содержания). - person Albert; 16.07.2010
comment
Вот хорошее объяснение сжатия, которое я бы порекомендовал для дальнейшего чтения: mattmahoney.net/dc/dce. html - а на странице Hutter есть ссылка на cs.fit .edu / ~ mmahoney / compress / textdata.html, который тоже приятно читать. - person schnaader; 16.07.2010

arrow_upward
7
arrow_downward

По оценке Клода Шеннона, плотность информации английского языка составляет от 0,6 до 1,3 бит на символ в его статья 1951 года Прогнозирование и энтропия печатного английского языка (PDF, 1,6 МБ. Bell Sys. Tech. J (3) p. 50-64).

person phreeza    schedule 16.07.2010
comment
Хм, мне интересно, совместима ли колмогоровская сложность с плотностью информации Шеннона. По моей интуиции, информация Шеннона - это просто поток битов. Например. Пиксельный поток фрактального изображения по определению Шеннона все еще имеет некоторую высокую плотность информации. Поэтому мне интересно, действительно ли 0,6 является хорошей оценкой. Возможно, для английского текста, который не содержит лишней информации. - person Albert; 19.07.2010
comment
Shannon Information делает утверждение об общем статистическом случае, в то время как колмогоровская сложность - это информационное содержание одного объекта. Итак, в этом примере информация Шеннона говорит что-то о среднем символе в английском тексте, в то время как сложность Колмогорова - это информационное содержание определенного тела текста, например, вашей строки s. - person phreeza; 19.07.2010
comment
Но Шеннон был важной фигурой, формирующей теорию информации и энтропию, и, в конечном счете, проблема заключается в энтропии. Энтропия Шеннона представляет собой абсолютный предел наилучшего возможного сжатия любого сообщения без потерь - person Hot Licks; 10.09.2011

arrow_upward
0
arrow_downward

Максимально возможная (средняя) степень сжатия составляет 1: 1.
Количество возможных входов равно количеству выходов.
Это должно быть, чтобы иметь возможность отображать выходные данные обратно на вход.
Чтобы иметь возможность хранить вывод, вам нужен контейнер того же размера, что и минимальный контейнер для ввода, что дает степень сжатия 1: 1.

person Dani    schedule 16.07.2010
comment
Максимально возможная (средняя) степень сжатия - 1: 1. Что это на самом деле означает? - person Matthew Flaschen; 16.07.2010
comment
Это означает, что вы берете все возможные 100-байтовые строки и сжимаете каждую из них. Средняя длина вашего сжатого вывода составляет не менее 100 байт, поэтому среднее сжатие составляет 1: 1 или хуже. Конечно, реальные данные не случайны, поэтому было бы лучше сказать, что он говорит об оптимальной степени сжатия в худшем случае. Но он пытается ответить на вопрос в заголовке: максимально возможная степень сжатия зависит, прежде всего, от данных. На самом деле это не отвечает на основной вопрос ... - person jjrv; 17.06.2012

arrow_upward
0
arrow_downward

По сути, вам нужно достаточно информации, чтобы восстановить исходную информацию. Я думаю, что другие ответы более полезны для вашего теоретического обсуждения, но просто имейте это в виду.

person Chad    schedule 16.07.2010