Математика сжатия: почему текст ужимается, а случайный шум — нет

Сжать данные — значит выгнать из них предсказуемость. Чем меньше сюрприза в каждом символе, тем сильнее он ужимается.

Энтропия — это математическая мера неожиданности. Она же — нижняя граница, ниже которой не сожмёт ни один архиватор на свете.

Вы кидаете в архиватор текст романа — он ужимается втрое. Кидаете уже сжатый файл или случайный мусор — размер почти не меняется. Почему программа «сдаётся»? Ответ дал Клод Шеннон в 1948 году, заложив целую науку — теорию информации.

Идея сжатия: частое — коротко, редкое — длинно

В обычном тексте символы встречаются неравномерно. Буквы «о» и «е» — на каждом шагу, а «ъ» и «ф» — изредка. Если кодировать все буквы одинаковым числом битов, мы расточительны: частым буквам достаётся столько же места, сколько редким.

Гениальная мысль: давать частым символам короткие коды, а редким — длинные. В среднем сообщение укоротится. На этом построен знаменитый код Хаффмана, который собирает буквы в дерево по их частоте.

Маленькая иллюстрация

Пусть буква «о» встречается в половине случаев. Глупо тратить на неё $8$ битов — хватит и одного-двух. А вот редкой «щ» можно отдать длинный код: она всё равно появляется нечасто, и общий объём почти не пострадает. Так экономятся биты на самом ходовом.

Энтропия: формула неожиданности

Шеннон ввёл точную меру того, сколько информации несёт сообщение, — энтропию. Если символ появляется с вероятностью $p$, то его «неожиданность» равна $-\log_2 p$: чем реже символ, тем больше бит он несёт. Средняя неожиданность по всему алфавиту и есть энтропия:

$$H = -\sum_{i} p_i \log_2 p_i$$

Здесь $p_i$ — вероятность $i$-го символа. Величина $H$ — это среднее число битов на символ, ниже которого сжать в принципе невозможно. Энтропия — это теоретический предел архивации.

Почему случайный шум не сжимается

В по-настоящему случайных данных все символы равновероятны, ничего не предсказать. Энтропия достигает максимума — каждый символ несёт полную порцию информации, лишнего нет. Сжимать нечего: нет ни частых символов, ни повторов, ни закономерностей. Архиватор честно разводит руками.

Сжатие без потерь и с потерями

Архиваторы вроде ZIP сжимают без потерь: распаковка возвращает байт в байт. А форматы JPEG и MP3 идут на хитрость — выбрасывают то, что человек всё равно не заметит (тончайшие оттенки, неслышимые частоты). Это сжатие с потерями, и оно ужимает куда сильнее — но восстановить оригинал точь-в-точь уже нельзя.

Повторы — ещё один источник сжатия

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

Граница, которую не перейти

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