Код Хаффмана: жадный алгоритм сжатия на куче с разбором и кодом
Код Хаффмана простыми словами: префиксные коды, построение дерева жадным алгоритмом на куче, доказательство оптимальности, кодирование и декодирование, канонические коды. Код на Python.
Коротко
| Вопрос | Ответ |
|---|---|
| Задача | Назначить символам двоичные коды так, чтобы закодированный текст был как можно короче |
| Главная идея | Два самых редких символа склеиваем в один узел с суммарной частотой и повторяем, пока не останется дерево |
| Структура | Min-куча по частотам: каждый шаг — два heappop и один heappush |
| Сложность | , где — длина текста, — число разных символов |
| Где встречается | DEFLATE (zip, gzip, PNG), JPEG, задачи «минимальная стоимость слияния» на LeetCode |
Код Хаффмана — редкий алгоритм, который одинаково хорош и для собеседования, и для понимания реального мира. Он короткий, опирается на кучу и жадный выбор, а его оптимальность доказывается в пару абзацев. Заодно это лучший пример того, почему жадность иногда работает идеально.
Зачем вообще менять коды символов
В ASCII каждый символ занимает 8 бит, неважно, встречается он через раз или один раз на книгу. Это удобно, но расточительно. Если в тексте почти одни буквы a, логично дать a короткий код, а редким символам — длинный. Так устроена азбука Морзе: самая частая буква английского E — одна точка.
Возьмём строку abracadabra. В ней 11 символов и 5 разных букв:
| Символ | a | b | r | c | d |
|---|---|---|---|---|---|
| Частота | 5 | 2 | 2 | 1 | 1 |
Код фиксированной длины для пяти символов требует бита на символ, итого 33 бита. Код Хаффмана для этой строки уложится в 23 бита. Посмотрим, откуда берётся экономия.
Префиксные коды
С переменной длиной кода есть проблема: как понять, где кончается один символ и начинается другой? Попробуем наивно: a = 0, b = 1, r = 01. Строка 01 — это ab или r? Однозначно раскодировать нельзя.
Решение — префиксный код: ни одно кодовое слово не является началом другого. Тогда декодер читает биты по одному и, как только набранная последовательность совпала с каким-то кодом, смело выдаёт символ: продолжения быть не может.
Любой префиксный код удобно представить двоичным деревом:
- символы живут только в листьях;
- путь от корня к листу — это код: шаг влево пишет
0, шаг вправо —1; - раз символы только в листьях, ни один путь не продолжает другой — код префиксный автоматически.
Длина кода символа равна глубине его листа. Значит, задача сводится к такой: построить двоичное дерево, в котором сумма минимальна, где — частота символа, — глубина его листа. Эта сумма и есть длина закодированного текста в битах.
Алгоритм Хаффмана
Идея, которую Дэвид Хаффман опубликовал в 1952 году, удивительно проста:
- Сделайте из каждого символа отдельный узел с его частотой.
- Возьмите два узла с наименьшими частотами.
- Склейте их в новый узел-родитель, частота которого равна сумме частот детей.
- Верните новый узел в набор. Повторяйте шаги 2–4, пока не останется один узел — корень.
Каждое склеивание уменьшает число узлов на один, поэтому для символов будет ровно склеиваний. Достать два минимума и вставить новый элемент — ровно то, для чего существует двоичная куча. В Python это модуль heapq, подробнее о нём — в статье про очередь с приоритетом.
Почему склеиваем именно редкие? Склеенные узлы опускаются на уровень глубже, и каждый их символ получит в коде на один бит больше. Платить этот бит дешевле всего тем, кто встречается реже всех.
Разбор на примере
Частоты для abracadabra: a:5, b:2, r:2, c:1, d:1.
| Шаг | Куча до шага | Склеиваем | Новый узел |
|---|---|---|---|
| 1 | c:1, d:1, b:2, r:2, a:5 | c:1 + d:1 | cd:2 |
| 2 | b:2, r:2, cd:2, a:5 | b:2 + r:2 | br:4 |
| 3 | cd:2, br:4, a:5 | cd:2 + br:4 | cdbr:6 |
| 4 | a:5, cdbr:6 | a:5 + cdbr:6 | корень:11 |
Получилось дерево:
(11)
0/ \1
a:5 (6)
0/ \1
(2) (4)
0/ \1 0/ \1
c d b r
Читаем коды по путям: a = 0, c = 100, d = 101, b = 110, r = 111. Длина текста: бита против 33 у кода фиксированной длины.
Обратите внимание на шаг 2: в куче было три узла с частотой 2, и можно было склеить любые два. Дерево Хаффмана не единственно, коды могут отличаться от реализации к реализации. Но длина закодированного текста у всех вариантов одинаковая и минимальная.
Код на Python
import heapq from collections import Counter from itertools import count def build_codes(text): freq = Counter(text) if not freq: return {} if len(freq) == 1: # один символ: дерево из одного листа return {next(iter(freq)): '0'} tie = count() # разрывает ничьи, чтобы heapq не сравнивал узлы heap = [(f, next(tie), ch) for ch, f in freq.items()] heapq.heapify(heap) while len(heap) > 1: f1, _, left = heapq.heappop(heap) f2, _, right = heapq.heappop(heap) heapq.heappush(heap, (f1 + f2, next(tie), (left, right))) codes = {} def walk(node, prefix): if isinstance(node, tuple): # внутренний узел: (левый, правый) walk(node[0], prefix + '0') walk(node[1], prefix + '1') else: # лист: символ codes[node] = prefix walk(heap[0][2], '') return codes print(sorted(build_codes('abracadabra').items())) # [('a', '0'), ('b', '110'), ('c', '100'), ('d', '101'), ('r', '111')]
Три детали, на которых чаще всего спотыкаются:
- Счётчик
tie. При равных частотахheapqначнёт сравнивать следующий элемент кортежа. Сравнить строку с кортежем Python не умеет и броситTypeError. Уникальный порядковый номер гарантирует, что до сравнения узлов дело не дойдёт. - Один уникальный символ. Строка
aaaaдаёт дерево из одного листа, и путь к нему пустой. Без отдельной ветки код уaбудет пустой строкой, а закодированный текст — нулевой длины. Поэтому явно назначаем'0'. - Узлы — обычные кортежи. Отдельный класс
Nodeтоже подходит, но тогда ему понадобится__lt__или тот же счётчик в кортеже.
Кодирование и декодирование
Кодирование — просто склейка кодов. Декодирование опирается на префиксность: копим биты, пока не совпадём с каким-нибудь кодом.
def encode(text, codes): return ''.join(codes[ch] for ch in text) def decode(bits, codes): reverse = {code: ch for ch, code in codes.items()} out, cur = [], '' for b in bits: cur += b if cur in reverse: # префиксный код: первое совпадение и есть символ out.append(reverse[cur]) cur = '' return ''.join(out) codes = build_codes('abracadabra') bits = encode('abracadabra', codes) print(bits, len(bits)) # 01101110100010101101110 23 print(decode(bits, codes)) # abracadabra
На практике декодер чаще идёт по самому дереву: 0 — влево, 1 — вправо, дошли до листа — выдали символ и вернулись в корень. Это то же самое, что поиск по префиксному дереву, только алфавит из двух букв. Боевые декодеры (zlib и компания) идут дальше и строят таблицы, которые за одно обращение по первым нескольким битам сразу выдают символ и длину его кода.
Почему жадность здесь оптимальна
На собеседовании про Хаффмана нередко спрашивают: «А почему это работает?» В статье про жадные алгоритмы разобрано, что жадный выбор надо доказывать, иначе легко получить неверный ответ. Для Хаффмана доказательство держится на двух леммах.
Лемма 1: два самых редких символа можно сделать братьями на самой глубине
Возьмём любое оптимальное дерево. Оно полное: у каждого внутреннего узла два ребёнка. Иначе узел с одним ребёнком можно выкинуть, подняв поддерево на уровень выше, и код станет короче.
Значит, на самом глубоком уровне есть два листа-брата и . Пусть и — два самых редких символа. Поменяем местами с , а — с . Редкий уходит вниз, на глубину , а более частый поднимается на место . Обмен меняет стоимость на
так как и . Стоимость не выросла, дерево по-прежнему оптимально, и теперь и — братья на максимальной глубине. Это классический аргумент обмена.
Лемма 2: склейка сохраняет оптимальность
Склеим и в новый символ с частотой . Любое дерево для нового алфавита превращается в дерево для старого: вешаем к листу двух детей и . При этом
Добавка не зависит от формы дерева. Поэтому, минимизируя стоимость для меньшего алфавита, мы минимизируем её и для исходного. Дальше индукция по числу символов, и алгоритм Хаффмана — ровно эта индукция, записанная циклом.
Из леммы 2 следует полезное наблюдение: длина закодированного текста равна сумме всех склеек. Каждая склейка добавляет по одному биту всем символам внутри узла, то есть ровно частоту узла. Для нашего примера: .
Насколько близко к пределу
Шеннон показал, что меньше энтропии в среднем на символ не сожмёшь:
Средняя длина кода Хаффмана удовлетворяет . Для abracadabra энтропия около 2,04 бита на символ, а Хаффман даёт . Почти впритык.
Слабое место — тот самый «плюс один». Код Хаффмана тратит на символ целое число бит. Если один символ встречается в 99% случаев, его энтропия около 0,08 бита, а Хаффман всё равно потратит минимум 1 бит. Поэтому в современных форматах рядом с Хаффманом используют арифметическое кодирование и ANS, которые умеют тратить дробные биты.
Та же идея в задачах на собеседовании
Сама формулировка «постройте код Хаффмана» на собеседованиях встречается не так часто. Гораздо чаще та же жадность прячется в задаче про слияние: «Даны палки длин sticks. Соединить две палки стоит сумму их длин. Найдите минимальную стоимость соединения всех палок в одну» (LeetCode 1167, Minimum Cost to Connect Sticks). Это в точности стоимость дерева Хаффмана: каждая длина входит в ответ столько раз, на какой глубине окажется.
import heapq def huffman_cost(freqs): heap = list(freqs) heapq.heapify(heap) total = 0 while len(heap) > 1: a = heapq.heappop(heap) b = heapq.heappop(heap) total += a + b heapq.heappush(heap, a + b) return total print(huffman_cost([2, 4, 3])) # 14 print(huffman_cost([1, 8, 3, 5])) # 30 print(huffman_cost([5, 2, 2, 1, 1])) # 23 — те же 23 бита, что у abracadabra
Та же схема встречается в задаче об оптимальном слиянии отсортированных файлов: слить два файла стоит суммы их размеров, порядок слияний выбираем сами. Если же сливать можно только соседние кучки (камни в ряд), жадность уже не работает: нужен интервальный DP.
Подготовительная часть алгоритма — подсчитать частоты и работать с кучей по частоте — один в один повторяет задачу «k самых частых элементов». Поэтому в блоке задач ниже она и стоит: если уверенно решаете её через Counter и heapq, код Хаффмана напишете без шпаргалки.
Сложность
- Подсчёт частот: , где — длина текста.
- Построение кучи: , затем итераций по . Итого .
- Обход дерева для получения кодов: узлов, но склейка строк-префиксов добавляет суммарную длину всех кодов.
- Кодирование и декодирование: , линейно по числу бит результата.
Для байтов , так что построение дерева практически бесплатно, всё время уходит на проход по данным.
Если частоты уже отсортированы, кучу можно заменить двумя очередями: в первой лежат исходные листья по возрастанию, во вторую складываем склеенные узлы. Суммы склеек растут монотонно, поэтому вторая очередь тоже остаётся отсортированной, а минимум всегда в начале одной из двух очередей. Построение становится линейным.
Канонические коды: как хранить дерево
Чтобы раскодировать файл, декодеру нужны коды. Передавать всё дерево дорого. Хитрость в том, что достаточно передать только длины кодов: по ним однозначно восстанавливается так называемый канонический код.
Правило: сортируем символы по длине кода, а при равной длине — по самому символу. Первый получает код из одних нулей, каждый следующий — предыдущий плюс единица; при росте длины дописываем нули справа.
def canonical_codes(lengths): # lengths: {символ: длина кода} из дерева Хаффмана items = sorted(lengths.items(), key=lambda kv: (kv[1], kv[0])) codes, code, prev_len = {}, 0, items[0][1] for ch, length in items: code <<= length - prev_len # длина выросла — дописываем нули справа codes[ch] = format(code, f'0{length}b') code += 1 prev_len = length return codes print(canonical_codes({'a': 1, 'b': 3, 'c': 3, 'd': 3, 'r': 3})) # {'a': '0', 'b': '100', 'c': '101', 'd': '110', 'r': '111'}
Длины кодов те же, что у исходного дерева, значит, и сжатие то же. Так устроен DEFLATE: в заголовке блока лежат длины кодов (тоже сжатые), а сами коды декодер восстанавливает по этому правилу. Подробнее про сдвиги и маски — в статье про битовые операции.
Типичные ошибки
Склеивать не два минимума
Иногда пытаются склеивать самый редкий символ с уже построенным деревом по очереди, получая «лесенку». На равномерных частотах это даёт коды длиной до вместо . Каждый шаг — строго два наименьших элемента кучи, неважно, листья это или склеенные узлы.
TypeError при равных частотах
Кортеж (частота, узел) без счётчика упадёт на первой же ничьей, если узлы — разнотипные объекты. Решение — (частота, счётчик, узел) или __lt__ у класса узла.
Забытый случай одного символа
Пустой код у единственного символа — классический баг. Пустая строка тоже требует проверки: Counter('') пуст, и heap[0] упадёт с IndexError.
Глубокая рекурсия при обходе
На частотах, растущих как числа Фибоначчи (1, 1, 2, 3, 5, 8, …), дерево вырождается в цепочку, и глубина равна . Для байтов это не страшно, но если алфавит — слова текста, рекурсивный обход упрётся в лимит рекурсии Python. Обходите дерево стеком вместо рекурсии.
Ожидание, что Хаффман сжимает всё
Если символы распределены равномерно (случайные байты, уже сжатый файл), выигрыша не будет, а к данным ещё добавится таблица кодов. Хаффман выигрывает только на неравномерных частотах.
Где это встречается на собеседованиях
- Прямой вопрос «расскажите про код Хаффмана». Ждут: префиксный код, дерево, жадное склеивание двух минимумов на куче, сложность . Плюс — если сами упомянете, почему код префиксный и почему жадность оптимальна.
- Задачи на слияние с минимальной стоимостью. Палки, верёвки, файлы. Узнали схему — решили за пять строк.
- Как пример жадного алгоритма с доказательством. Если спрашивают «приведите жадный алгоритм, который точно оптимален», Хаффман с аргументом обмена — сильный ответ.
- Системный вопрос про сжатие. Как устроен gzip, почему JPEG-файл почти не жмётся zip-ом, что такое энтропия. Достаточно знать, что DEFLATE — это LZ77 плюс Хаффман, и что сжатые данные близки к случайным.
Для тренировки начните с задачи о самых частых элементах: она отрабатывает ту же связку «подсчитали частоты — положили в кучу». Затем реализуйте build_codes, encode и decode целиком и проверьте на случайных строках, что decode(encode(s)) == s, а длина кода совпадает с huffman_cost. Если обе проверки проходят на тысяче строк, алгоритм вы понимаете.