Кодирование Хаффмана
Кодирование Хаффмана — алгоритм построения эффективного префиксного кода, в котором часто встречающиеся символы получают короткие слова, а редкие — длинные. Метод позволяет уменьшить среднюю длину сообщения без потери информации и однозначно восстановить исходный текст.
Основная идея и термины
Пусть сообщение состоит из символов алфавита \(a_1,a_2,\ldots,a_n\). Для каждого символа известна его частота — число появлений в сообщении или вероятность появления. Нужно сопоставить символам двоичные кодовые слова так, чтобы сообщение занимало как можно меньше битов.
Код Хаффмана — двоичный префиксный код, построенный по частотам символов с помощью последовательного объединения двух наименее частых элементов. Он является оптимальным среди двоичных префиксных кодов для заданных частот.
Префиксный код обладает важным свойством: ни одно кодовое слово не является началом другого. Поэтому декодирование выполняется слева направо без разделителей. Кодовое дерево представляет такой код: каждому переходу влево или вправо приписывают 0 или 1, а символы размещают в листьях.
Если символ находится на глубине \(l_i\), то его код имеет длину \(l_i\). Средняя длина кодирования одного символа определяется частотами \(p_i\) и длинами кодов.
Если вместо вероятностей даны количества появлений \(f_i\), можно использовать взвешенную сумму длин. Общее число битов равно сумме произведений частоты на длину кода.
Для построения кода Хаффмана два символа или узла с наименьшими частотами объединяют в один узел с суммарной частотой. Процесс повторяют, пока не останется один корневой узел. Затем по ветвям дерева выписывают двоичные коды.
Алгоритм построения
Алгоритм можно выполнять в таблице. На каждом шаге выбирайте два минимальных значения, складывайте их и возвращайте сумму в список. Важно сохранять структуру объединения: простого списка частот недостаточно, потому что в конце нужно восстановить коды.
- Запишите все символы и их частоты.
- Выберите два узла с наименьшими частотами.
- Объедините их в новый узел с частотой, равной сумме.
- Повторяйте действия, пока не получится один узел — корень дерева.
- Назначьте ветвям значения 0 и 1 и прочитайте код каждого символа от корня к листу.
Не имеет значения, какой из двух братьев помечен 0, а какой 1. Если поменять метки у ветвей, получится другой код с теми же длинами и той же эффективностью.
Разобранный пример
Построим код для символов \(A\), \(B\), \(C\), \(D\) с частотами соответственно 5, 7, 10 и 15. На каждом шаге объединяем два наименьших узла.
Закодируем строку \(CAD\): \(C\to10\), \(A\to110\), \(D\to0\), поэтому получится \(101100\). Читаем поток слева: \(10|110|0\). Ни один код не приходится разделять догадкой, так как код префиксный.
Какие два узла нужно объединить на первом шаге для частот 3, 8, 5 и 2?
Почему код получается эффективным
Частый символ выгодно поместить ближе к корню: тогда его код короче и он вносит меньший вклад в общее число битов. Редкий символ может находиться глубже, потому что его длинный код используется реже.
Алгоритм Хаффмана строит префиксный код с минимальной средней длиной среди всех двоичных префиксных кодов для данных частот. Если несколько частот совпадают, оптимальных вариантов может быть несколько; длины кодов и размер сообщения при этом могут совпадать.
Для сравнения с равномерным кодом найдите число символов \(n\) и оцените длину фиксированного кода как \(\lceil\log_2 n\rceil\) бит на символ. Хаффман может быть выгоднее, если частоты заметно различаются. При одинаковых частотах выигрыш обычно отсутствует или невелик.
Код Хаффмана не шифрует данные: частоты и способ построения могут раскрывать особенности сообщения. Его цель — сжатие информации, а не защита от чтения.
Что нужно уметь в задачах
- Находить два наименьших значения на каждом шаге.
- Строить дерево объединений и подписывать ветви 0 и 1.
- Выписывать код символа по пути от корня к листу.
- Проверять, что кодовые слова не являются префиксами друг друга.
- Считать длину закодированного сообщения по формуле \(B=\sum f_i l_i\).
- Сравнивать результат с равномерным или другим кодом.
Не объединяйте самые частые символы: выбираются два минимальных значения. Не путайте частоту с длиной кода: большая частота обычно приводит к меньшей длине, но не задаёт её напрямую. Не забывайте учитывать все появления символа в формуле общего объёма. При совпадении частот возможны разные деревья — это не обязательно ошибка. Наконец, код одного символа в строке нельзя искать по частям произвольно: декодирование идёт от корня дерева.
Два минимальных узла → объединение → повторение до корня → метки 0 и 1 → чтение кодов от корня к листьям.
Связь с другими способами кодирования
В дереве кодирования каждый символ располагается в листе, поэтому путь к нему задаёт код. Свойство префиксности обеспечивает однозначность декодирования. При оценке результата полезно отдельно учитывать число символов в алфавите, распределение частот и служебные данные, необходимые для передачи самого дерева.
Если сообщение нужно передавать блоками или поток непрерывен, декодер должен знать дерево Хаффмана. В практических форматах дерево или таблица кодов сохраняются вместе с закодированными данными. Для очень малых сообщений служебная информация может уменьшить или полностью уничтожить выигрыш от сжатия.
Итоговая проверка
Главное
- Код Хаффмана строится по частотам символов и является двоичным префиксным кодом.
- На каждом шаге объединяются два узла с наименьшими частотами.
- Код символа — путь от корня дерева к соответствующему листу; метки ветвей 0 и 1.
- Объём закодированного сообщения вычисляется как \(B=\sum f_i l_i\), а средняя длина — как \(L=\sum p_i l_i\).
- Разные варианты нумерации ветвей могут давать разные слова, но одинаковую эффективность.