Кодирование Хаффмана: объяснение
Компьютеры обычно хранят каждую букву в одном и том же числе битов, в простом ASCII — в восьми. Это просто, но расточительно, ведь одни буквы встречаются гораздо чаще других. В 1951 году один студент нашёл наилучший способ дать каждому символу код собственной длины — частым короткий, редким длинный — с помощью построения настолько простого, что оно умещается в несколько строк. Сегодня кодирование Хаффмана работает почти в каждом сжатом файле, изображении и звуке, которые вы открываете.
Короткие коды для частых символов
Азбука Морзе использовала эту идею ещё в 1830-х годах: E, самая частая буква английского языка, — это одна точка, а Q — тире, тире, точка, тире. Такой код экономит время и место всякий раз, когда одни символы встречаются чаще других. Но переменная длина порождает проблему, которую Морзе решил паузами: как узнать, где кончается один код и начинается следующий? И какие длины назначить символам, чтобы сумма была как можно меньше?
Префиксные коды
Первая проблема исчезает, если ни один код не является началом другого. С кодами A = 0, B = 10, C = 110 и D = 111 биты 0101100 можно прочитать только как A B C A: как только прочитанные биты образуют код, этот код завершён. Такие префиксные коды в точности соответствуют двоичным деревьям с символами в листьях, где каждая левая ветвь означает 0, а каждая правая — 1. Выбрать код — значит выбрать дерево.
Построение Хаффмана
Начните с одного листа на каждый символ с весом, равным его числу вхождений. Возьмите два самых лёгких дерева, объедините их под новым узлом, вес которого равен их сумме, и повторяйте, пока не останется одно дерево. Вот и весь алгоритм. Редкие символы объединяются первыми и оказываются глубоко в дереве, с длинными кодами; частые объединяются последними и остаются близко к вершине, с короткими кодами. С очередью с приоритетом это занимает время, пропорциональное n log n для n символов.
Почему он оптимален
В наилучшем возможном дереве два самых редких символа всегда можно поместить братьями на самом глубоком уровне: обмен их с тем, что там находится, может только уменьшить сумму. Объедините их в один символ с общим весом, и остаток — та же задача с одним символом меньше, так что жадный шаг никогда не закрывает путь к наилучшему ответу. Общее число использованных битов равно сумме весов всех внутренних узлов, а объединение держит её минимальной.
Курсовая работа вместо экзамена
В 1951 году Дэвид Хаффман, аспирант MIT, слушал курс Роберта Фано по теории информации. Фано предложил студентам выбор: сдать итоговый экзамен или написать курсовую работу о поиске самого эффективного двоичного кода. Хаффман уже почти отказался от работы, когда понял, что построение дерева снизу вверх, а не разбиение сверху вниз, как в методе Шеннона — Фано, всегда даёт наилучший результат. Он опубликовал метод в 1952 году; метод студента превзошёл тот, что его профессор разработал вместе с Клодом Шенноном.
Близко к энтропии
Клод Шеннон показал, что никакой код не может в среднем использовать меньше битов на символ, чем энтропия источника. Код Хаффмана достигает энтропии ровно тогда, когда каждая вероятность — степень одной второй, и никогда не превышает её на целый бит на символ. Разрыв важен, когда один символ встречается очень часто: символу с долей 99% всё равно нужен хотя бы один целый бит, хотя он несёт лишь около 0,015 бита информации. Арифметическое кодирование и асимметричные системы счисления в новых компрессорах обходят это ограничение.
Коды Хаффмана повсюду
Кодирование Хаффмана редко используется само по себе, но образует последнюю ступень многих форматов. Deflate, работающий в ZIP, gzip и PNG, сначала заменяет повторы ссылками, а затем записывает результат кодами Хаффмана. JPEG применяет их к числам, оставшимся после преобразования изображения, MP3 — к своим аудиоданным, а факсы — к длинам серий чёрных и белых точек. Форматы обычно передают канонический код Хаффмана, в котором достаточно хранить только длины кодов, потому что сами коды можно по ним восстановить.
Попробуйте сами
Откройте конструктор кода Хаффмана, чтобы шаг за шагом построить дерево для ABRACADABRA, MISSISSIPPI RIVER, собственного предложения или любого другого текста. Смотрите, как на каждом шаге объединяются два самых лёгких дерева, нажмите на лист, чтобы увидеть его код, проследите символ в закодированных битах и сравните итог с кодом фиксированной длины, UTF-8 и энтропией.
Часто задаваемые вопросы
Чем кодирование Хаффмана отличается от кодирования Шеннона — Фано?
Кодирование Шеннона — Фано строит дерево сверху, снова и снова разбивая символы на две группы почти равного веса. Часто оно даёт хороший результат, но не всегда оптимальный. Хаффман строит дерево снизу, объединяя два самых лёгких дерева, и всегда получает самый короткий возможный префиксный код.
Нужно ли декодеру дерево?
Да, ему нужен тот же код. Поэтому сжатые файлы хранят его, обычно в виде списка длин кодов для канонического кода, который занимает всего несколько десятков байтов. Для коротких текстов эти накладные расходы могут перевесить экономию; конструктор считает только закодированные биты.
Может ли кодирование Хаффмана увеличить файл?
Закодированные символы никогда не занимают больше битов, чем код фиксированной длины для тех же символов. Но таблицу кодов тоже нужно хранить, поэтому для очень коротких или почти случайных данных результат может оказаться немного больше оригинала.
О чём говорит неравенство Крафта?
О том, что префиксный код с длинами кодовых слов l₁, l₂, … существует тогда и только тогда, когда сумма 2 в степени −l по всем символам не превышает 1. Для полного дерева, такого как любое дерево Хаффмана хотя бы с двумя символами, сумма равна ровно 1.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Открыть конструктор кода Хаффмана