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

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

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

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

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

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

Ответ 1

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

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

Ответ 2

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

Ответ 3

Максимальная возможная степень сжатия может составлять 1:1.
Количество возможных входов равно количеству выходов.
Он должен быть способен отображать вывод обратно на вход.
Для хранения вывода вам нужен контейнер такого же размера, как и минимальный контейнер для ввода - с коэффициентом сжатия 1:1.

Ответ 4

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