Теорема о сжатии: почему нельзя сжать вообще всё

Идеального архиватора, который ужмёт любой файл хоть на байт, не существует — и это доказывается простым подсчётом.

Сжатие работает не потому, что мы умные, а потому что в реальных данных полно повторов. Случайные данные сжать нельзя в принципе — там нечего убирать.

Соблазнительная мечта

Что, если написать супер-архиватор, который любой файл делает хоть чуть-чуть меньше? Тогда можно было бы сжать результат снова. И снова. И ужать гигабайтный фильм до одного байта. Звучит как вечный двигатель — и, как вечный двигатель, это невозможно. Вот почему.

Доказательство на пальцах: голубятня

Воспользуемся принципом Дирихле (его ещё называют принципом голубей и ящиков): если голубей больше, чем гнёзд, хотя бы в одно гнездо сядут двое.

Посчитаем файлы. Сколько существует файлов ровно из 3 бит? Это все комбинации от 000 до 111 — ровно $2^3 = 8$ штук. А файлов покороче, из 2 бит и меньше? Их $2^2 + 2^1 + 2^0 = 4 + 2 + 1 = 7$ штук.

Теперь суть. Допустим, наш архиватор сжимает каждый 3-битный файл хотя бы до 2 бит. Тогда он должен запихнуть 8 разных файлов в 7 доступных коротких ячеек. По принципу Дирихле как минимум два разных исходных файла превратятся в один и тот же сжатый. А значит, распаковать обратно однозначно нельзя — мы потеряли информацию. Архиватор сломан.

Вывод неумолим

Раз коротких кодов всегда меньше, чем длинных файлов, никакой компрессор не может сжать все входы без потерь. Отсюда железное правило:

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

Хорошие архиваторы просто заключают выгодную сделку: они укорачивают типичные файлы (тексты, картинки, код — в них масса закономерностей) ценой того, что редкие «странные» данные чуть распухнут. Поскольку странные данные нам почти не встречаются, в среднем мы выигрываем.

Связь со случайностью

Отсюда вытекает красивое определение случайности (по Колмогорову): данные случайны ровно настолько, насколько их нельзя сжать. Если строку можно описать короче неё самой — в ней есть закономерность. Если нельзя — это чистый шум.

Вот почему попытка заархивировать ZIP-файл повторно почти ничего не даёт: архиватор уже выжал из него все закономерности, осталось нечто, неотличимое от случайного шума. По той же причине бессмысленно архивировать уже сжатые форматы — JPEG, MP3, готовый видеоролик: их создатели заранее удалили предсказуемость, и больше убирать нечего.

Практический смысл

Эта теорема — отличный детектор шарлатанов. Каждые несколько лет кто-то объявляет «революционный алгоритм, сжимающий любые данные на 50%». Это всегда обман или ошибка: математика запрещает такое так же строго, как закон сохранения энергии запрещает вечный двигатель. Реальные успехи в сжатии — это не магия, а всё более тонкое улавливание закономерностей в конкретных типах данных: в речи, в видео, в геноме. Универсального чуда не будет, а специализированное мастерство — будет всегда.