Код Хаффмана

В «Войне и мире» 2 904 144 знака, и в UTF-8 они занимают 5 179 058 байт: каждая русская буква — два байта, шестнадцать бит. Но пробел встречается 452 000 раз, буква «о» — 255 033 раза, а прописная «Й» — один раз на весь роман. Код Хаффмана даёт пробелу три бита, «о» — четыре, «Й» — двадцать один, и роман сжимается до 1,76 мегабайта, в 2,9 раза. Ниже дерево этого кода растёт из настоящих частот: каждый шаг склеивает два самых редких дерева. Высота узла — сколько раз встречаются его знаки, глубина листа — длина кода.

Запустите построение с начала. Первыми склеиваются знаки, которые встретились по разу: латинские буквы с акцентами из французских реплик, «№», «→», та самая «Й». Их деревья растут долго и глубоко, поэтому коды у них длинные. Буквы русского алфавита вступают позже, а пробел и «о» присоединяются почти у самого корня — у них короткие коды. Переключите на ДНК лямбды: четыре буквы встречаются почти одинаково часто, дерево вырождается в два уровня, и каждая буква получает ровно два бита. Сжимать там нечего — частоты почти равны.

Идея

Код, в котором ни одно кодовое слово не начинает другое, называют префиксным. Его можно читать без разделителей: набрали биты, совпало с кодом — это знак, начинаем следующий. Префиксный код — то же самое, что двоичное дерево: налево 0, направо 1, знаки в листьях, код знака — дорога к нему от корня. Длина кода — глубина листа, а цена всего текста — сумма по знакам «частота × глубина».

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

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

Есть удобная формула для цены кода. Каждый узел дерева, кроме листьев, лежит на пути от корня ко всем своим листьям, поэтому в сумме «частота × глубина» вес каждого узла посчитан ровно один раз за каждый его лист внизу. Отсюда

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

Почему это лучший код

Обратите внимание, где жадность была права, а где ошиблась бы. Предшественник Хаффмана, код Шеннона — Фано, тоже жадный, но строит дерево сверху: делит знаки на две группы с частотами как можно ближе. Самое ответственное решение — у корня — он принимает первым и не может потом исправить. Хаффман начинает с того конца, где жадный шаг удаётся доказать, — снизу. Пример, где сверху получается хуже, и дерево Шеннона — Фано рядом с деревом Хаффмана есть в главе курса о жадных алгоритмах.

Префиксные коды — не единственные, которые можно однозначно прочитать. Но и это не помогает: по неравенству Крафта — Макмиллана длины любого однозначно декодируемого кода удовлетворяют Σ 2^−ℓ_x ≤ 1, а для таких длин всегда есть префиксный код. Так что Хаффман лучший среди всех кодов, которые заменяют каждый знак отдельной цепочкой бит.

Насколько близко к пределу

Клод Шеннон в 1948 году доказал, что никакой такой код не потратит в среднем меньше энтропии бит на знак, H = −Σ p_x log₂ p_x, а код Хаффмана тратит меньше H + 1. На «Войне и мире» энтропия — 4,825 бита на знак, Хаффман — 4,862, на 0,8 % больше. Отставание бывает почти в целый бит, только когда один знак очень частый: если знак встречается в 99 % случаев, энтропия — 0,08 бита, а меньше одного бита на знак никакой код целым числом бит не даст. Тогда кодируют пары и тройки знаков или переходят на арифметическое кодирование, которое тратит дробное число бит на знак. Как устроена энтропия и почему предел именно такой, рассказывает глава «Царицы наук» о мере информации.

Но энтропия — предел только для кодов, которые смотрят на знаки по одному и не помнят соседей. Поменяйте алфавит — поменяется и предел. Если считать знаком целое слово, а пробелы и препинание — отдельными знаками, текст станет миллионом слов-символов, и код Хаффмана для них займёт уже 2,48 бита на знак текста. Справа от каждой полосы — сколько это бит на знак романа:

Словарь не бесплатный: чтобы раскодировать текст, получателю нужны все 54 169 слов и знаков, и сжатые zlib они занимают ещё 219 тысяч байт. Но даже вместе со словарём Хаффман по словам — 1,12 МБ — обходит zip с его 1,39 МБ. zip сжимает повторы на расстоянии до 32 килобайт, а слова романа повторяются по всему тексту. Архиваторы xz и bzip2 смотрят на контекст ещё шире и выигрывают у обоих. Снимите галочку «считать словарь», и увидите, как легко обмануть себя: без словаря Хаффман по словам «сжимает» роман лучше любого архиватора.

Код

Построение кода по частотам, декодирование и канонический код с теми же длинами — о нём следующий раздел. Номер order в куче разбивает ничьи: при равных частотах первым выходит дерево, созданное раньше, а листья создаются в порядке знаков. Так Python, Go и сцена выше строят одно и то же дерево.

И весь роман. Программа читает «Войну и мир» с сервера, где исполняется код, считает знаки, строит длины кодов и сравнивает с UTF-8 и энтропией; затем то же для алфавита из слов:

  1764902 bytes; the longest code: 21 bits, longer than 15 bits: 40 symbols

Эта строка — повод для следующего раздела.

Как код хранят и передают

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

Так устроен DEFLATE — сжатие внутри zip, gzip и PNG (RFC 1951). Блок начинается с длин кодов для 286 знаков и длин ссылок и для 30 расстояний, причём сами длины тоже сжаты кодом Хаффмана. И стандарт ограничивает длину кода 15 битами, чтобы декодер мог читать коды таблицей фиксированного размера. У «Войны и мира» побуквенный код длиннее: 40 знаков получили больше 15 бит, «Й» — 21 бит. Значит, настоящему архиватору оптимальный код Хаффмана иногда не подходит, и нужен оптимальный код с ограничением длины. Его строит алгоритм package-merge Лоуренса Лармора и Дэниела Хиршберга (1990); zlib поступает проще: строит обычное дерево и, если коды вышли слишком длинными, перекладывает листья, пока они не уложатся в предел. Сжатие от этого почти не страдает: на редкие знаки приходится ничтожная доля бит.

Декодеры не ходят по дереву бит за битом. Они смотрят сразу на следующие, скажем, девять бит и по таблице из 2⁹ записей узнают и знак, и длину его кода; длинные коды дочитывают второй таблицей. Канонический код удобен и здесь: коды одной длины — подряд идущие числа, поэтому знак находится вычитанием. Попробуйте в задаче о расшифровке по длинам.

Где ломается: один бит

У переменной длины кодов есть цена: ошибка в одном бите сбивает декодер с границ знаков. Ниже фраза из романа, записанная его кодом. Переверните любой бит.

В коде фиксированной длины перевёрнутый бит портил бы ровно один знак. Здесь декодер читает дальше уже с неправильной границы и выдаёт чужие знаки, пока границы случайно не совпадут снова. Обычно это происходит быстро: из 296 вариантов ошибки в этой фразе в 83 портится один знак, в среднем — шесть-семь. Но в 34 вариантах декодер так и не возвращается в такт до конца фразы. Поэтому форматы сжатия делят данные на блоки и проверяют их контрольными суммами: zip и gzip хранят CRC-32 каждого файла и замечают порчу, а не пытаются её исправить.

Сколько это стоит

Для алфавита из n знаков нужно n − 1 склеек, каждая — две операции извлечения из кучи и одна вставка, по O(log n). Итого O(n log n) на построение и O(n) памяти. Кодирование и декодирование текста — O(N), где N — число бит или знаков; для текстов это главное время, а построение кода для 165 знаков занимает микросекунды.

Если частоты уже отсортированы, кучу можно заменить двумя очередями (Ян ван Леувен, 1976). В первой — листья по возрастанию, во вторую складываются склеенные деревья. Суммы склеек при этом получаются неубывающими, поэтому вторая очередь тоже отсортирована сама собой, и два самых лёгких дерева всегда стоят в начале очередей. Каждая склейка — O(1), всё построение после сортировки — O(n). Замер: куча, две очереди (вместе с сортировкой) и поиск двух минимумов простым просмотром.

У просмотра наклон 2: вдесятеро больше знаков — в сто раз дольше. Куча и очереди растут почти линейно, а очереди быстрее кучи в два раза в Python и в несколько раз в Go. На алфавите из 54 тысяч слов романа знаков в 18 раз больше, чем в последней точке просмотра, — значит, и ждать его пришлось бы в триста с лишним раз дольше.

Где работает

Сам по себе код Хаффмана сжимает слабо — он не видит повторов и контекста. Зато он отлично доделывает работу за другими методами, которые превращают данные в поток знаков с неравными частотами.

• DEFLATE (zip, gzip, PNG, сжатие страниц сайтов): LZ77 заменяет повторы ссылками назад, а знаки и ссылки кодируются двумя кодами Хаффмана с длиной до 15 бит. Устройство DEFLATE разбирает глава курса о сжатии.
• JPEG: после дискретного косинусного преобразования и квантования остаются в основном нули и небольшие числа, и их серии кодируются кодами Хаффмана из таблиц, записанных в файле.
• HTTP/2 и HTTP/3: в стандарте сжатия заголовков HPACK (RFC 7541) записан один статический код Хаффмана для всех байтов, построенный по статистике настоящих заголовков; он сжимает адреса и cookie без передачи таблицы.
• MP3, Brotli, zstd: тоже префиксные коды для части потока. В zstd рядом с Хаффманом работает асимметричная система счисления (ANS) — она, как арифметическое кодирование, тратит дробное число бит на знак, но почти так же быстра.

История

В 1951 году Дэвид Хаффман, тогда аспирант, выбрал вместо экзамена по теории информации курсовую у Роберта Фано: найти самый экономный двоичный код. Фано и Шеннон к тому времени придумали метод деления сверху, но не могли доказать, что он лучший, — и он действительно не был лучшим. Хаффман после месяцев безуспешных попыток решил сдаться и, по его рассказу, уже выбрасывал записи, когда понял, что дерево надо строить снизу. Статья «A Method for the Construction of Minimum-Redundancy Codes» вышла в сентябре 1952 года в журнале Proceedings of the IRE и заняла четыре страницы. Подробнее эту историю рассказывает глава курса.

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

Задачи

В первой задаче нужен не код, а только его цена, и формула «сумма весов склеек» превращает её в несколько строк с кучей; ловушка — в одном знаке и в больших числах. Во второй код задан одними длинами, как в DEFLATE, и его надо восстановить и прочитать.