Каков максимум теоретически возможный уровень сжатия?
Это - теоретический вопрос, поэтому ожидайте, что много деталей здесь не вычислимы на практике или даже в теории.
Скажем, у меня есть строка s то, что я хочу сжаться. Результатом должен быть самораспаковывающийся двоичный файл (может быть x86 ассемблер, но это может также быть некоторый другой гипотетический полный по Тьюрингу низкоуровневый язык), который выводы s.
Теперь, мы можем легко выполнить итерации через всех возможных такие двоичные файлы и программы, заказанные размером. Позволить B_s будьте подсписком этих двоичных файлов, кто произвел s (конечно, B_s невычислимо).
Поскольку каждый набор положительных целых чисел должен иметь минимум, должна быть наименьшая программа b_min_s в B_s.
Поскольку, что языки (т.е. набор строк), мы знаем что-то о размере b_min_s? Возможно, только оценка. (Я могу создать некоторые тривиальные примеры, где я могу всегда даже вычислять B_s и также b_min_s, но я интересуюсь более интересными языками.)
4 ответа
Это сложность Колмогорова , и вы правы, что она не вычислима . Если бы это было так, вы могли бы создать парадоксальную программу длины n, которая печатала бы строку с колмогоровской сложностью m> n.
Очевидно, вы можете связать b_min_s для заданных входов. Однако, насколько мне известно, большинство попыток сделать это были доказательствами существования. Например, продолжается соревнование по сжатию английской Википедии .
Клод Шеннон оценил плотность информации английского языка где-то между 0,6 и 1,3 бит на символ в своей статье 1951 года Предсказание и энтропия печатного английского языка (PDF, 1,6 МБ. Bell Sys. Tech. J (3) стр. 50-64).
По сути, вам нужно достаточно информации, чтобы восстановить вашу исходную информацию. Я думаю, что другие ответы более полезны для вашей теоретической дискуссии, но просто имейте это в виду.
Максимально возможная (средняя) степень сжатия - 1:1.
Число возможных входов равно числу выходов.
Должна быть возможность сопоставить выход с входом.
Чтобы иметь возможность хранить выход, необходим контейнер того же размера, что и минимальный контейнер для входа - что дает степень сжатия 1:1.