Код Хаффмана: жадный алгоритм сжатия на куче с разбором и кодом

Код Хаффмана простыми словами: префиксные коды, построение дерева жадным алгоритмом на куче, доказательство оптимальности, кодирование и декодирование, канонические коды. Код на Python.

12 мин чтенияалгоритмы · жадные алгоритмы · куча · python

Коротко

ВопросОтвет
ЗадачаНазначить символам двоичные коды так, чтобы закодированный текст был как можно короче
Главная идеяДва самых редких символа склеиваем в один узел с суммарной частотой и повторяем, пока не останется дерево
СтруктураMin-куча по частотам: каждый шаг — два heappop и один heappush
СложностьO(n+σlog⁡σ)O(n + \sigma \log \sigma), где nn — длина текста, σ\sigma — число разных символов
Где встречаетсяDEFLATE (zip, gzip, PNG), JPEG, задачи «минимальная стоимость слияния» на LeetCode

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

Зачем вообще менять коды символов

В ASCII каждый символ занимает 8 бит, неважно, встречается он через раз или один раз на книгу. Это удобно, но расточительно. Если в тексте почти одни буквы a, логично дать a короткий код, а редким символам — длинный. Так устроена азбука Морзе: самая частая буква английского E — одна точка.

Возьмём строку abracadabra. В ней 11 символов и 5 разных букв:

Символabrcd
Частота52211

Код фиксированной длины для пяти символов требует ⌈log⁡25⌉=3\lceil \log_2 5 \rceil = 3 бита на символ, итого 33 бита. Код Хаффмана для этой строки уложится в 23 бита. Посмотрим, откуда берётся экономия.

Префиксные коды

С переменной длиной кода есть проблема: как понять, где кончается один символ и начинается другой? Попробуем наивно: a = 0, b = 1, r = 01. Строка 01 — это ab или r? Однозначно раскодировать нельзя.

Решение — префиксный код: ни одно кодовое слово не является началом другого. Тогда декодер читает биты по одному и, как только набранная последовательность совпала с каким-то кодом, смело выдаёт символ: продолжения быть не может.

Любой префиксный код удобно представить двоичным деревом:

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

Длина кода символа равна глубине его листа. Значит, задача сводится к такой: построить двоичное дерево, в котором сумма ∑fi⋅di\sum f_i \cdot d_i минимальна, где fif_i — частота символа, did_i — глубина его листа. Эта сумма и есть длина закодированного текста в битах.

Алгоритм Хаффмана

Идея, которую Дэвид Хаффман опубликовал в 1952 году, удивительно проста:

  1. Сделайте из каждого символа отдельный узел с его частотой.
  2. Возьмите два узла с наименьшими частотами.
  3. Склейте их в новый узел-родитель, частота которого равна сумме частот детей.
  4. Верните новый узел в набор. Повторяйте шаги 2–4, пока не останется один узел — корень.

Каждое склеивание уменьшает число узлов на один, поэтому для σ\sigma символов будет ровно σ−1\sigma - 1 склеиваний. Достать два минимума и вставить новый элемент — ровно то, для чего существует двоичная куча. В Python это модуль heapq, подробнее о нём — в статье про очередь с приоритетом.

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

Разбор на примере

Частоты для abracadabra: a:5, b:2, r:2, c:1, d:1.

ШагКуча до шагаСклеиваемНовый узел
1c:1, d:1, b:2, r:2, a:5c:1 + d:1cd:2
2b:2, r:2, cd:2, a:5b:2 + r:2br:4
3cd:2, br:4, a:5cd:2 + br:4cdbr:6
4a:5, cdbr:6a: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. Длина текста: 5⋅1+2⋅3+2⋅3+1⋅3+1⋅3=235 \cdot 1 + 2 \cdot 3 + 2 \cdot 3 + 1 \cdot 3 + 1 \cdot 3 = 23 бита против 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: два самых редких символа можно сделать братьями на самой глубине

Возьмём любое оптимальное дерево. Оно полное: у каждого внутреннего узла два ребёнка. Иначе узел с одним ребёнком можно выкинуть, подняв поддерево на уровень выше, и код станет короче.

Значит, на самом глубоком уровне есть два листа-брата xx и yy. Пусть aa и bb — два самых редких символа. Поменяем aa местами с xx, а bb — с yy. Редкий aa уходит вниз, на глубину xx, а более частый xx поднимается на место aa. Обмен меняет стоимость на

(fx−fa)(da−dx)≤0,(f_x - f_a)(d_a - d_x) \le 0,

так как fx≥faf_x \ge f_a и dx≥dad_x \ge d_a. Стоимость не выросла, дерево по-прежнему оптимально, и теперь aa и bb — братья на максимальной глубине. Это классический аргумент обмена.

Лемма 2: склейка сохраняет оптимальность

Склеим aa и bb в новый символ zz с частотой fa+fbf_a + f_b. Любое дерево T′T' для нового алфавита превращается в дерево TT для старого: вешаем к листу zz двух детей aa и bb. При этом

cost(T)=cost(T′)+fa+fb.\text{cost}(T) = \text{cost}(T') + f_a + f_b.

Добавка fa+fbf_a + f_b не зависит от формы дерева. Поэтому, минимизируя стоимость для меньшего алфавита, мы минимизируем её и для исходного. Дальше индукция по числу символов, и алгоритм Хаффмана — ровно эта индукция, записанная циклом.

Из леммы 2 следует полезное наблюдение: длина закодированного текста равна сумме всех склеек. Каждая склейка добавляет по одному биту всем символам внутри узла, то есть ровно частоту узла. Для нашего примера: 2+4+6+11=232 + 4 + 6 + 11 = 23.

Насколько близко к пределу

Шеннон показал, что меньше энтропии в среднем на символ не сожмёшь:

H=−∑ipilog⁡2pi.H = -\sum_i p_i \log_2 p_i.

Средняя длина кода Хаффмана LL удовлетворяет H≤L<H+1H \le L < H + 1. Для abracadabra энтропия около 2,04 бита на символ, а Хаффман даёт 23/11≈2,0923 / 11 \approx 2{,}09. Почти впритык.

Слабое место — тот самый «плюс один». Код Хаффмана тратит на символ целое число бит. Если один символ встречается в 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, код Хаффмана напишете без шпаргалки.

Сложность

  • Подсчёт частот: O(n)O(n), где nn — длина текста.
  • Построение кучи: O(σ)O(\sigma), затем σ−1\sigma - 1 итераций по O(log⁡σ)O(\log \sigma). Итого O(σlog⁡σ)O(\sigma \log \sigma).
  • Обход дерева для получения кодов: O(σ)O(\sigma) узлов, но склейка строк-префиксов добавляет суммарную длину всех кодов.
  • Кодирование и декодирование: O(n⋅Lˉ)O(n \cdot \bar{L}), линейно по числу бит результата.

Для байтов σ≤256\sigma \le 256, так что построение дерева практически бесплатно, всё время уходит на проход по данным.

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

Канонические коды: как хранить дерево

Чтобы раскодировать файл, декодеру нужны коды. Передавать всё дерево дорого. Хитрость в том, что достаточно передать только длины кодов: по ним однозначно восстанавливается так называемый канонический код.

Правило: сортируем символы по длине кода, а при равной длине — по самому символу. Первый получает код из одних нулей, каждый следующий — предыдущий плюс единица; при росте длины дописываем нули справа.

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: в заголовке блока лежат длины кодов (тоже сжатые), а сами коды декодер восстанавливает по этому правилу. Подробнее про сдвиги и маски — в статье про битовые операции.

Типичные ошибки

Склеивать не два минимума

Иногда пытаются склеивать самый редкий символ с уже построенным деревом по очереди, получая «лесенку». На равномерных частотах это даёт коды длиной до σ−1\sigma - 1 вместо log⁡2σ\log_2 \sigma. Каждый шаг — строго два наименьших элемента кучи, неважно, листья это или склеенные узлы.

TypeError при равных частотах

Кортеж (частота, узел) без счётчика упадёт на первой же ничьей, если узлы — разнотипные объекты. Решение — (частота, счётчик, узел) или __lt__ у класса узла.

Забытый случай одного символа

Пустой код у единственного символа — классический баг. Пустая строка тоже требует проверки: Counter('') пуст, и heap[0] упадёт с IndexError.

Глубокая рекурсия при обходе

На частотах, растущих как числа Фибоначчи (1, 1, 2, 3, 5, 8, …), дерево вырождается в цепочку, и глубина равна σ−1\sigma - 1. Для байтов это не страшно, но если алфавит — слова текста, рекурсивный обход упрётся в лимит рекурсии Python. Обходите дерево стеком вместо рекурсии.

Ожидание, что Хаффман сжимает всё

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

Где это встречается на собеседованиях

  • Прямой вопрос «расскажите про код Хаффмана». Ждут: префиксный код, дерево, жадное склеивание двух минимумов на куче, сложность O(σlog⁡σ)O(\sigma \log \sigma). Плюс — если сами упомянете, почему код префиксный и почему жадность оптимальна.
  • Задачи на слияние с минимальной стоимостью. Палки, верёвки, файлы. Узнали схему — решили за пять строк.
  • Как пример жадного алгоритма с доказательством. Если спрашивают «приведите жадный алгоритм, который точно оптимален», Хаффман с аргументом обмена — сильный ответ.
  • Системный вопрос про сжатие. Как устроен gzip, почему JPEG-файл почти не жмётся zip-ом, что такое энтропия. Достаточно знать, что DEFLATE — это LZ77 плюс Хаффман, и что сжатые данные близки к случайным.

Для тренировки начните с задачи о самых частых элементах: она отрабатывает ту же связку «подсчитали частоты — положили в кучу». Затем реализуйте build_codes, encode и decode целиком и проверьте на случайных строках, что decode(encode(s)) == s, а длина кода совпадает с huffman_cost. Если обе проверки проходят на тысяче строк, алгоритм вы понимаете.

Потренироваться в спокойной обстановке

Все задачи