Лекция: Сжатие и комбинаторика
Легко доказывается теорема.
| Для любого N > 0 нет алгоритма сжатия без потерь, который: 1. Любой файл длиной не более N байт или оставляет той же длины, или уменьшает. 2. Существует файл длиной не более N, который уменьшается хотя бы на один байт. |
Доказательство. Не ограничивая общности, можно предположить, что уменьшился файл A длины ровно N. Обозначим алфавит как. Рассмотрим множество. В этом множестве исходных файлов, в то время как сжатых не более чем. Поэтому функция декомпрессии неоднозначна, противоречие. Теорема доказана.
Впрочем, данная теорема нисколько не бросает тень на сжатие без потерь. Дело в том, что любой алгоритм сжатия можно модифицировать так, чтобы он увеличивал размер не более чем на 1 бит: если алгоритм уменьшил файл, пишем «1», потом сжатую последовательность, если увеличил — пишем «0», затем исходную. Пример того, как это реализуется на псевдо-C++, показан ниже:
Так что несжимаемые фрагменты не приведут к бесконтрольному «раздуванию» архива. «Реальных» же файлов длины N намного меньше, чем (говорят, что данные имеют низкую информационную энтропию) — например, маловероятно, чтобы буквосочетание «щы» встретилось в осмысленном тексте, а в оцифрованном звуке уровень не может за один сэмпл прыгнуть от 0 до 100 %. К тому же за счёт специализации алгоритмов на некоторый тип данных (текст, графику, звук и т. д.) удаётся добиться высокой степени сжатия: так, применяющиеся в архиваторах универсальные алгоритмы сжимают звук примерно на треть (в 1,5 раза), в то время как FLAC — в 2,5 раза. Большинство специализированных алгоритмов малопригодны для файлов «чужих» типов: например, звуковые данные плохо сжимаются алгоритмом, рассчитанным на тексты.