Информатика · объяснение и практика
Как объединение наименьших весов строит код Хаффмана
Строим код по четырём собственным частотам, считаем длину сообщения через глубину листьев и отделяем оптимум модели от размера готового файла.

В теме Кодирование чисел, текста, изображения и звука · Учебная карта
Главная мысль
Алгоритм Хаффмана строит двоичный префиксный код, повторно объединяя два узла с наименьшими весами. Внутренний узел получает сумму весов, а код символа задаётся путём к его листу. При заданных частотах получается минимальная взвешенная длина среди двоичных префиксных кодов символов.
После объединения в очередь возвращается сумма
Пусть знаки А, Б, В, Г встретились 11,7,4,2 раза. Сначала объединяем веса 2 и 4, получаем узел веса 6. Теперь рассматриваем веса 6,7,11: наименьшие 6 и 7 объединяются в 13. Последний шаг соединяет 11 и 13 в корень веса 24.
Знак А с весом 11 оказался ребёнком корня и имеет код длины 1. Б с весом 7 лежит на глубине 2. В и Г находятся на глубине 3. Например, допустимо назначить А=0, Б=10, В=110, Г=111. Поворот левого и правого ребёнка изменит биты, но не эти длины.
Пример
Полезная запись занимает 11×1+7×2+4×3+2×3=43 бита.
При равномерном двухбитном коде 24 знака заняли бы 48 бит. Выигрыш полезной части равен пяти битам, а не целому размеру файла вместе со служебными данными.
Почему выбирают именно лёгкие узлы
Каждое объединение увеличивает глубину всех листьев двух выбранных поддеревьев на один. Прибавка к общей взвешенной длине равна сумме их весов. Редким знакам выгоднее отдавать более длинные пути, а частым — короткие. Алгоритм применяет это соображение последовательно к листьям и уже собранным группам.
На очередном шаге сравнивают также созданные суммы, а не только оставшиеся исходные частоты. В нашем примере узел 6 должен участвовать в следующем выборе наравне с 7 и 11. Игнорирование внутренних узлов превратило бы процедуру в другой алгоритм. Для реализации такой очереди минимумов удобно использовать кучу.
Что именно оптимально и что может отличаться
При равных весах допустимы разные порядки объединения и разные таблицы кодов с одинаковой оптимальной стоимостью. Поэтому проверять только одну ожидаемую последовательность нулей и единиц неверно. Проверяют префиксность, наличие всех нужных символов и итоговую взвешенную длину. Для воспроизводимой таблицы задают правило разрешения равенств.
Оптимальность относится к данной модели: независимое кодирование отдельных символов с известными весами. Другие методы могут использовать блоки, зависимости или другой класс кодов. Кроме того, для маленького сообщения передача таблицы и длины способна перекрыть выигрыш полезных битов. Если символ всего один, заранее оговаривают, как передаются его количество и код: случай пустого пути в дереве требует отдельного соглашения.
От чтения к действию
А теперь — вы
Частые вопросы
Можно ли использовать частоты вместо вероятностей?
Да: деление всех весов на общую сумму не меняет порядок сравнений и выбранных объединений. Частоты удобны для точного подсчёта числа полезных битов.
Обязательно ли наиболее частый символ получает уникально самый короткий код?
Не обязательно: возможны равные длины и разные оптимальные деревья. Важно оптимальное взвешенное значение всей таблицы, а не заранее выбранный рисунок отдельных ветвей.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему двоичная куча выдаёт минимум без полной сортировки
Проверяем инвариант минимальной кучи, извлекаем корень из собственного массива и объясняем, почему оставшиеся элементы не обязаны идти по порядку.
Открыть темуКак длины кодовых слов ограничивает неравенство Крафта
Проверяем вместимость двоичного кодового дерева по длинам слов, строим допустимую таблицу и объясняем, почему одних длин недостаточно для проверки готового кода.
Открыть тему