Код Хаффмана

Код Хаффмана: зачем он нужен

Если в задачах на кодирование символы превращаются в цепочки нулей и единиц, легко запутаться: почему одним буквам дают короткие коды, а другим длинные? Код Хаффмана помогает сжать сообщение без потери информации. Разобрав алгоритм по шагам, ты научишься строить двоичное дерево, получать коды символов и уверенно решать задания по теме «Системы счисления и кодирование».

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

Код Хаффмана относится к префиксным кодам. Это означает, что код одного символа не является началом кода другого. Благодаря этому последовательность 010011 можно разобрать единственным способом, даже если длины кодов различаются.

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

Основная идея алгоритма

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

После объединения снова ищут два узла с минимальными частотами. Процесс продолжается, пока все элементы не окажутся внутри одного общего корня. Так получается дерево Хаффмана.

Ветвям дерева назначают обозначения 0 и 1. Обычно левой ветви дают 0, правой — 1, но можно сделать наоборот: длины кодов и эффективность не изменятся. Код символа читают от корня к этому символу. Чем ближе символ к корню, тем короче его код.

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

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

Рассмотрим условный набор символов. Пусть частоты распределены так:

Символ	Частота
А	5
Б	7
В	10
Г	15

Сначала объединяем два минимальных значения: 5 и 7. Получаем узел с частотой 12. Теперь в списке находятся 10, 12 и 15. Следующими объединяются 10 и 12, получается 22. Последний шаг: 15 и 22 образуют корень с частотой 37.

Далее расставляем нули и единицы на ветвях. Пусть из корня к Г ведёт 0, а к узлу 22 — 1. Внутри узла 22 пусть к В ведёт 0, а к узлу 12 — 1. Внутри узла 12 к А ведёт 0, к Б — 1.

Г → 0
В → 10
А → 110
Б → 111
Проверка: 15 × 1 + 10 × 2 + 5 × 3 + 7 × 3 = 66 бит

Это полностью разобранный пример: мы выполнили объединения, построили дерево, назначили ветвям значения и посчитали общий объём закодированного сообщения.

Средняя длина кода здесь равна 66 ÷ 37, то есть примерно 1,78 бита на символ. Для сравнения, равномерный двоичный код четырёх символов потребовал бы 2 бита на каждый символ, или 74 бита.

Проверка и типичные ошибки

После построения дерева обязательно проверь три свойства. Во-первых, каждый исходный символ должен встретиться ровно один раз. Во-вторых, код не должен быть префиксом другого кода. Например, набор 0, 01, 11 неверен: код 0 является началом кода 01. В-третьих, сумма частот дочерних узлов должна совпадать с частотой родительского узла.

Частая ошибка — считать, что код Хаффмана всегда даёт одинаковые двоичные цепочки. Если частоты совпадают, можно выбрать разные варианты дерева. Они могут отличаться кодами символов, но сохранять одинаковую общую длину.

Ещё одна ошибка возникает при декодировании. Нельзя делить строку на равные куски: коды имеют разную длину. Нужно идти от корня дерева по одному биту. Дошёл до листа — записал символ и вернулся к корню.

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

Попрактиковаться в разборе подобных алгоритмов можно через бесплатные задания в личном кабинете, где удобно возвращаться к теме и повторять шаги.

Связь с системами счисления

Код Хаффмана работает с двоичными знаками, поэтому напрямую связан с системами счисления. Символы кодируются последовательностями 0 и 1, а длина такой последовательности измеряется в битах. Один бит может принять одно из двух значений: 0 или 1.

Если кодов четыре и все они имеют одинаковую длину, достаточно 2 бит, потому что 2² = 4. Для восьми вариантов нужно 3 бита, так как 2³ = 8. При неравномерных частотах код Хаффмана использует переменную длину: частые варианты получают меньше битов.

Не следует записывать код Хаффмана как обычное число и удалять ведущие нули. Последовательности 01 и 1 как двоичные числа могут выглядеть похоже после преобразования, но в кодировании это разные цепочки и разные пути в дереве.

Иногда в условии встречаются дроби или смешанные числа, например ¾ или 2⅓, но они относятся к расчётам средней длины, а не к самим кодам. Сначала работай с целыми частотами, затем при необходимости вычисляй среднее количество битов на один символ.

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

Что запомнить

Код Хаффмана — способ построить эффективный префиксный двоичный код по частотам символов. Алгоритм выглядит так: выпиши частоты, выбери два минимальных узла, объедини их, повторяй до получения корня, расставь 0 и 1 на ветвях, выпиши путь от корня к каждому символу.

Главные проверки: сумма частот в корне равна общему числу символов, каждый символ находится в отдельном листе, ни один код не является началом другого. При декодировании читай биты по дереву и возвращайся к корню после каждого листа.

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

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