Як Хаффман будує оптимальний код
Хеммінг представляє кодування Хаффмана як жадібний алгоритм, який будує код без префіксів з мінімальною середньою довжиною. Ключева ідея: будувати дерево знизу вверх, завжди об'єднуючи два найменш вірогідні символи.
Прямий прохід (Будування)
1. Відсортуйте всі символи за вірогідністю, від найвищої до найнижчої.
2. Возьміть два найменш вірогідні символи. Об'єднайте їх у новий метасимвол з вірогідністю = сума двох.
3. Вставте метасимвол на його відсортоване місце.
4. Повторюйте, доки не залишиться два символи.
5. Призначте 0 і 1 двом залишившимся символам.
Зворотний прохід (Призначення кодів)
Скасуйте об'єднання у зворотному порядку: при кожному розділенні два символи, що були об'єднані, отримують ті самі префіксні біти, що й їхній об'єднаний батько, плюс додатковий 0 (одна дочірня вершина) або 1 (інша дочірня вершина). Призначення 0/1 довільне — обидва варіанти дійсні.
Чому це оптимально: якби якийсь інший код мав меншу середню довжину L', застосування того ж прямого скорочення в кінцевому рахунку дало б два символи із середньою довжиною менше 1 біта — неможливо для коду з 2 символами. Суперечність.
Відстеження алгоритму
Приклад від Хеммінга: чотири символи A, B, C, D з p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
Прямий прохід:
Крок 1: Відсортовано: A(0,5), B(0,25), C(0,125), D(0,125). Два найнижчі: C, D.
Крок 2: Об'єднайте CD з p=0,25. Новий список: A(0,5), B(0,25), CD(0,25).
Крок 3: Два найнижчі: B(0,25), CD(0,25). Об'єднайте BCD з p=0,5.
Крок 4: Залишилось два символи: A(0,5), BCD(0,5). Призначте A=0, BCD=1.
Зворотний прохід:
BCD → B отримує 10, CD отримує 11. CD → C отримує 110, D отримує 111.
Фінальний код: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75 біт.
Кілька дійсних кодів Хаффмана
Хеммінг відзначає два джерела неунікальності:
1. Довільне призначення 0/1. При кожному розділенні ви можете дати 0 будь-якій дочірній вершині. Обмін 0 та 1 повсюди дає інший код з однаковим L.
2. Розв'язування нічиїх. Коли два вузли мають однакову вірогідність, будь-який можна розмістити 'вище' (об'єднати першим). Різні вибори розв'язування нічиїх можуть утворити структурно різні дерева — 'довгі' проти 'пишних' — з однаковим L, але різними розподілами довжин кодів.
Довгі проти пишних
Довге дерево (перекошене): один символ на кожному рівні глибини (структура подібна до Фібоначчі). Довжини кодів сильно різняться: один символ отримує короткий код, інші каскадом переходять до довших кодів.
Пишне дерево (збалансоване): символи рівномірно розташовані по рівнях глибини. Довжини кодів групуються близько до середнього. Нижча дисперсія.
Рекомендація Хеммінга: коли у вас є вибір, надайте перевагу пишному дереву. Той самий L, але менша дисперсія довжин кодів → більш рівномірний час декодування → менші вимоги до буфера в додатках реального часу.
Обчислення дисперсії довжини коду
Дисперсія довжин кодів: Var = E[l²] − (E[l])²
Для коду {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} з p=[0,5, 0,25, 0,125, 0,125]:
E[l] = L = 1,75
E[l²] = 0,5·1² + 0,25·2² + 0,125·3² + 0,125·3² = 0,5 + 1,0 + 1,125 + 1,125 = 3,75
Var = 3,75 − 1,75² = 3,75 − 3,0625 = 0,6875
Альтернативний пишний код для символів з рівною вірогідністю використовує всі коди довжини 2: L=2, Var=0.
Виграш у стисненні проти розподілу символів
Правило Хеммінга: кодування Хаффмана окупається тільки коли вірогідності символів суттєво відрізняються.
Рівні вірогідності. Якщо всі 2^k символів мають рівну вірогідність 1/2^k, Хаффман утворює блоковий код: кожен символ отримує довжину k. L = H = k. Жодного виграшу над простим блоковим кодом.
Перекошені вірогідності. Якщо один символ домінує (p >> 1/2^k для інших), Хаффман призначає йому дуже короткий код (довжина 1 або 2), різко зменшуючи L.
Код з комою (термін Хеммінга). Коли кожна вірогідність перевищує 2/3 від решти суми, Хаффман природно утворює: p(s1)→0, p(s2)→10, p(s3)→110, ..., до двох кодів рівної довжини в кінці. Це 'код з комою': нуль після серії одиниць діє як кома.
Хеммінг зазначає: стиснення даних у реальному світі (резервне копіювання, архівація файлів) може зменшити сховище більш ніж вдвічі, коли джерело має перекошені вірогідності — англійський текст є чудовим прикладом.
Хаффман проти блокового коду: числове порівняння
Другий приклад Хеммінга: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
Блоковий код: 8 символів → 3 біта кожен → L_block = 3.
Хеммінг обчислює код Хаффмана і повідомляє L_Huffman ≈ 2,58 біта.
Економія: (3 − 2,58)/3 ≈ 14% стиснення порівняно з блоковим кодуванням.
Коли вірогідності символів сильно відрізняються (1/3 проти 1/30 тут, коефіцієнт 10:1), кодування змінної довжини окупається суттєво.
Саморозширювальні програми
Хеммінг завершує главу 11 вражаючою ідеєю: кодер Хаффмана може кодувати себе. Дерево декодування (яке говорить декодеру, як читати стиснене повідомлення) передається разом зі стиснутими даними. Одержувач не потребує попередніх знань коду.
Кодер: бере вибірку даних, оцінює вірогідності, будує код Хаффмана, кодує дерево декодування як заголовок, потім кодує дані.
Декодер: читає заголовок для відновлення дерева, потім декодує дані за його допомогою.
Точка Хеммінга: весь цей конвеєр може працювати як функція бібліотеки без людської участі. Ви викликаєте його, він автоматично стискує та розпаковує. Сучасні формати архівування (ZIP, gzip, bzip2) реалізують саме цей шаблон.
Глибший принцип: інтелект є в алгоритмі, а не у фіксованій таблиці кодів. Алгоритм адаптується до будь-яких отриманих даних. Це шаблон, який Хеммінг бачить у всіх великих інженерних системах: адаптивність вбудована, а не прикріплена.