Как сжать текст без потери ни одной буквы: коды Хаффмана

Ты скачиваешь zip-архив, он весит вдвое меньше — а распаковываешь, и текст возвращается слово в слово, буква в букву. Куда делась половина файла и откуда она берётся обратно? Никакого фокуса: всё держится на одной красивой идее, которую в 1952 году придумал студент по имени Дэвид Хаффман. Поехали разбираться.

Почему обычный текст хранится расточительно

В компьютере каждая буква — это число. В классической кодировке вроде ASCII под каждый символ отводят ровно 8 бит (восемь нулей и единиц). И букве «а», и редкому символу «щ» достаётся одинаковая порция места — восемь бит, ни больше ни меньше.

Но если приглядеться к любому тексту, видно несправедливость. Буквы «о», «е», «а» встречаются на каждом шагу, а «ъ», «ф», «щ» — редкие гости. Зачем тратить на частую букву столько же места, сколько на ту, что мелькнёт раз в сто слов? Это как если бы почта брала одинаковую плату за открытку и за тяжёлую посылку.

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

Азбука Морзе почти угадала

Эта мысль не нова. Вспомни азбуку Морзе: самая частая в английском буква «E» — это одна точка, а редкая «Q» — длинная последовательность «тире-тире-точка-тире». Телеграфисты ещё в XIX веке сообразили: часто отправляешь — делай короче.

Но у Морзе есть скрытая проблема. Между буквами там нужна пауза, иначе непонятно, где кончается одна и начинается другая. Точка-точка — это «I» или два раза «E»? Без паузы не разберёшь. А в компьютере паузы нет — там сплошной поток нулей и единиц. Нужен код, который читается без всяких разделителей и при этом всегда расшифровывается однозначно.

Главный фокус Хаффмана: ни один код не должен быть началом другого кода. Тогда поток битов читается на лету, без единой паузы — и ошибиться невозможно.

Это свойство называют префиксным кодом. Если код буквы «о» — это 01, то никакой другой код не имеет права начинаться с 01. Дойдя до 01, декодер уверенно говорит: «это „о“» — и начинает читать следующую букву с чистого листа.

Как строится дерево Хаффмана

Самое красивое — то, как алгоритм сам находит идеальные коды. Он строит дерево, и делает это снизу вверх, жадно склеивая самое мелкое.

Представь, что буквы — это команды на школьном турнире, а «сила» команды — это частота буквы в тексте. Правило простое:

Выписываем все буквы и считаем, сколько раз каждая встречается.
Берём две самые редкие буквы и объединяем их в одну пару — «узел». Его частота равна сумме двух частот.
Кидаем этот новый узел обратно в общую кучу и снова ищем два самых редких элемента — теперь среди них и наша свежесклеенная пара.
Повторяем, пока всё не соберётся в одно большое дерево с единственной вершиной наверху.

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

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

Маленький пример и большая экономия

Возьмём слово, где буквы встречаются по-разному, скажем поток из символов A, B, C, где A — частая, B — пореже, C — совсем редкая. Хаффман выдаст что-то вроде: A = 0, B = 10, C = 11. Частая A занимает всего один бит вместо восьми. Прочитать поток 0100110 можно только одним способом: A, B, A, C, A — попробуй, разделители не нужны.

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

Где это живёт прямо сейчас

Может показаться, что это древняя теория из учебника. Ничего подобного — коды Хаффмана работают вокруг тебя каждую секунду:

Внутри форматов ZIP и GZIP — когда ты качаешь архив или сайт отдаёт сжатую страницу.
В формате картинок JPEG и в PNG — как финальный шаг упаковки данных.
В MP3 и видеокодеках — на последнем этапе, чтобы дожать уже обработанный поток.

Дэвид Хаффман придумал свой метод, будучи студентом, вместо того чтобы сдавать обычный экзамен по курсу. Его решение оказалось не просто хорошим, а математически оптимальным для своего класса задач: лучше расставить коды по отдельным буквам уже нельзя. Неплохо для домашнего задания, которое до сих пор живёт в каждом твоём гаджете.