Информатика · объяснение и практика

Как объединение наименьших весов строит код Хаффмана

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Кодирование чисел, текста, изображения и звука · Учебная карта

Главная мысль

Алгоритм Хаффмана строит двоичный префиксный код, повторно объединяя два узла с наименьшими весами. Внутренний узел получает сумму весов, а код символа задаётся путём к его листу. При заданных частотах получается минимальная взвешенная длина среди двоичных префиксных кодов символов.

После объединения в очередь возвращается сумма

Пусть знаки А, Б, В, Г встретились 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. Игнорирование внутренних узлов превратило бы процедуру в другой алгоритм. Для реализации такой очереди минимумов удобно использовать кучу.

Что именно оптимально и что может отличаться

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

Оптимальность относится к данной модели: независимое кодирование отдельных символов с известными весами. Другие методы могут использовать блоки, зависимости или другой класс кодов. Кроме того, для маленького сообщения передача таблицы и длины способна перекрыть выигрыш полезных битов. Если символ всего один, заранее оговаривают, как передаются его количество и код: случай пустого пути в дереве требует отдельного соглашения.

От чтения к действию

А теперь — вы

Имеются веса 17,6,5,3. Какие два узла Хаффман объединит на первом шаге?

Частые вопросы

Можно ли использовать частоты вместо вероятностей?

Да: деление всех весов на общую сумму не меняет порядок сравнений и выбранных объединений. Частоты удобны для точного подсчёта числа полезных битов.

Обязательно ли наиболее частый символ получает уникально самый короткий код?

Не обязательно: возможны равные длины и разные оптимальные деревья. Важно оптимальное взвешенное значение всей таблицы, а не заранее выбранный рисунок отдельных ветвей.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться