Канонический код Хаффмана: передать код одними длинами

Коротко

Код Хаффмана сжимает, но декодеру нужно знать сам код - и передавать вместе с данными дерево дорого и неудобно. Канонический код Хаффмана использует факт: для сжатия важны только ДЛИНЫ кодов, а сами коды при тех же длинах можно выбрать любыми, лишь бы префиксными. Договоримся выбирать их по правилу: символы сортируются по (длина, символ), и коды раздаются подряд, как двоичные числа - 0, 10, 110, 111; при росте длины к следующему номеру дописывают нули. Тогда в заголовке достаточно длины каждого символа (по 4 бита), а декодер восстановит коды сам и раскодирует поток по таблице «первый код каждой длины», без всякого дерева. Так устроены deflate, JPEG и многие другие форматы.

Если ты знаешь, как построить канонический код по длинам и как декодировать его без дерева, листай до «Теперь сам».

Как думаешь, что передать вместе со сжатым текстом

Хаффман из раздела про жадные алгоритмы построил дерево, и текст сжат. Чтобы на другом конце его раскодировали, декодеру нужно то же дерево. Передать дерево - это и форма, и символы в листьях, и легко ошибиться в формате.

Прежде чем читать дальше, ответь себе: важно ли, что символу а достался код 010, а не 011? Изменится ли длина сжатого текста, если поменять местами коды двух символов одинаковой длины?

На что это похоже

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

Механизм: раздать коды подряд и декодировать по первым кодам

ПО ДЛИНАМ - КОДЫ
отсортировать символы по (длина, символ)
код = 0, пред_длина = длина первого
для каждого символа:
    код = код · 2^(длина − пред_длина)   (длина выросла - дописать нули)
    выдать код длиной «длина» битами
    код += 1
коды разной длины не пересекаются и не являются началами друг друга:
    это префиксный код с теми же длинами, что у Хаффмана

ДЕКОДИРОВАНИЕ ПО ДЛИНАМ
для каждой длины L: первый код этой длины и сколько символов длины L
читаем биты по одному, набирая число kod длиной L:
    kod − первый[L] < сколько[L]  → символ номер
        (смещение длины L + разность) в отсортированном списке

Почему длин достаточно. Сжатие зависит только от того, сколько бит получает каждый символ; длины задают его полностью. Любой префиксный код с теми же длинами сжимает так же, а канонический - единственный такой код, который можно восстановить по одним длинам. Длины ещё и мало весят: обычно до 15 бит, то есть 4 бита на символ.

Правило

Сжатие кода Хаффмана определяют только длины кодов. Канонический код раздаёт коды подряд по сортировке (длина, символ): следующий код - предыдущий плюс один, а при росте длины - с дописанными нулями. Передают только длины; декодер восстанавливает коды и декодирует по таблице «первый код и число символов каждой длины», без дерева.

Разбор: четыре символа

длины от Хаффмана:  А 2,  Б 1,  В 3,  Г 3
порядок (длина, символ):  Б(1)  А(2)  В(3)  Г(3)

Б: код 0                        → 0
А: код 0 + 1 = 1, длина 1 → 2:  1·2 = 2  → 10
В: 2 + 1 = 3, длина 2 → 3:      3·2 = 6  → 110
Г: 6 + 1 = 7                             → 111

первый код и число по длинам:
    L=1: 0 (1 символ),  L=2: 10 (1),  L=3: 110 (2)
декодируем 0 10 111 110:
    «0»     L=1: 0 − 0 = 0 < 1    → Б
    «10»    L=1: 1 - не годится;  L=2: 2 − 2 = 0 < 1  → А
    «111»   L=3: 7 − 6 = 1 < 2    → второй символ длины 3: Г
    «110»   L=3: 6 − 6 = 0        → В

Заголовок для этих четырёх символов - четыре числа длин. Дерево с формой и символами в листьях потребовало бы описывать каждое внутреннее разветвление.

Разбор: скороговорки

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

kanon.py

import heapq
from collections import Counter

tekst = ("на дворе трава на траве дрова не руби дрова на траве двора "
         * 40 + "шла саша по шоссе и сосала сушку " * 25)


def dliny_haffmana(chastoty):         # только длины кодов, без дерева
    kucha = [(c, i, {s: 0})
             for i, (s, c) in enumerate(chastoty.items())]
    heapq.heapify(kucha)
    n = len(kucha)
    while len(kucha) > 1:
        c1, _, a = heapq.heappop(kucha)
        c2, _, b = heapq.heappop(kucha)
        sliyanie = {s: d + 1 for s, d in (a | b).items()}
        heapq.heappush(kucha, (c1 + c2, n, sliyanie))
        n += 1
    return kucha[0][2]


def kanonicheskij(dliny):             # коды по (длина, символ) подряд
    kody, kod, pred = {}, 0, 0
    for s in sorted(dliny, key=lambda s: (dliny[s], s)):
        kod *= 2 ** (dliny[s] - pred) # длина выросла - дописать нули
        kody[s] = format(kod, f"0{dliny[s]}b")
        kod, pred = kod + 1, dliny[s]
    return kody


def raskodirovat(bity, dliny):        # нужны только длины, а не дерево
    poryadok = sorted(dliny, key=lambda s: (dliny[s], s))
    skolko = Counter(dliny.values())
    pervyj, kod, nomer = {}, 0, 0     # первый код и номер для длины
    for L in range(1, max(skolko) + 1):
        pervyj[L] = (kod, nomer)
        kod = (kod + skolko[L]) * 2
        nomer += skolko[L]
    out, kod, L = [], 0, 0
    for b in bity:
        kod, L = kod * 2 + int(b), L + 1
        if L in pervyj and kod - pervyj[L][0] < skolko[L]:
            out.append(poryadok[pervyj[L][1] + kod - pervyj[L][0]])
            kod, L = 0, 0
    return "".join(out)


chastoty = Counter(tekst)
dliny = dliny_haffmana(chastoty)
kody = kanonicheskij(dliny)
bity = "".join(kody[s] for s in tekst)
assert raskodirovat(bity, dliny) == tekst
for s in sorted(kody, key=lambda s: (dliny[s], s))[:6]:
    print(repr(s), dliny[s], kody[s])
print("символов", len(tekst), " бит", len(bity),
      f" на символ {len(bity) / len(tekst):.2f}")
print("заголовок: длины кодов -", len(dliny), "чисел по 4 бита =",
      4 * len(dliny), "бит")

↳ выводpython3 kanon.py

' ' 2 00
'а' 3 010
'р' 3 011
'в' 4 1000
'д' 4 1001
'е' 4 1010
символов 3185  бит 11505  на символ 3.61
заголовок: длины кодов - 17 чисел по 4 бита = 68 бит

Текст восстановлен точно. Самый частый символ - пробел - получил двухбитный код 00, первые по порядку коды идут подряд, как и обещает правило. Заголовок - 68 бит на 17 символов; сам текст сжат до 3.61 бита на символ против 16 бит на символ в UTF-16 или 8 в однобайтной кодировке.

Что ломается без этого

Первая ошибка - сортировать символы при построении кода не так, как декодер: например, кодер по (длина, символ), а декодер по (длина, частота) - коды разъедутся, и поток раскодируется в мусор без единой ошибки формата. Правило сортировки - часть формата. Вторая - забыть дописывать нули при росте длины: коды разной длины начнут совпадать началом, и декодер остановится не там. Третья - позволить длинам расти без ограничения: на перекошенных частотах Хаффман даёт коды в десятки бит, а форматы держат предел (в deflate - 15 бит), поэтому длины после Хаффмана подрезают, жертвуя долей процента сжатия.

Зачем это в работе

Все распространённые форматы с кодом Хаффмана передают его канонически: deflate (zip, gzip, PNG), JPEG, многие видеокодеки. Знание канонического кода объясняет, почему заголовок блока deflate - это список длин, сжатый ещё одним маленьким кодом Хаффмана, и как написать быстрый декодер: по первому коду каждой длины, без обхода дерева. Тот же принцип «передать параметры, а не конструкцию» встречается шире: передать семя генератора вместо последовательности, длины вместо дерева, правило вместо таблицы.

Теперь сам

Длины: x 3, y 2, z 3, w 2, v 2. Построй канонический код.

Ответ. Порядок: v 2, w 2, y 2, x 3, z 3 (длина, потом символ). v - 00, w - 01, y - 10. Следующий код 11, длина растёт до 3: 11·2 = 110 - x, и z - 111. Код: v 00, w 01, y 10, x 110, z 111. Проверка префиксности: ни один двухбитный код не начинает трёхбитные 110 и 111, потому что 11 не выдан как код длины 2.

Главное

Сжатие кода Хаффмана определяют только длины кодов, поэтому код выбирают канонически: по сортировке (длина, символ), подряд, дописывая нули при росте длины. Тогда в заголовке хватает длин, а декодер восстанавливает коды и читает поток по таблице первых кодов, без дерева. На скороговорках - 68 бит заголовка и 3.61 бита на символ, и текст восстановлен по одним длинам.