Кодирование без потерь: Хаффман, LZ

1952: студент MIT придумывает оптимальный код за несколько недель. 1977: два израильских математика изобретают принцип скользящего окна. 2009: польский математик совмещает скорость и оптимальность в ANS. Каждый HTTP-запрос, каждый PNG, каждый AV1-видеопоток - это цепочка этих идей. Три алгоритма, семь десятилетий, петабайты ежедневно.

• **gzip / HTTP**: DEFLATE = LZ77 + Хаффман. Каждый ответ nginx с Content-Encoding: gzip использует алгоритм 1952 года
• **PNG**: DEFLATE (zlib). Скриншоты, иконки, WebP - всё это Хаффман + LZ77 без единого патента
• **zstd**: LZ77 + ANS. Facebook использует внутри для логов и баз данных; в 3x быстрее gzip при схожем ratio
• **AV1 / H.266**: видеокодеки используют ANS для энтропийного кодирования коэффициентов. Netflix, YouTube 8K

Предварительные знания

• KL-Divergence and Cross-Entropy

Код Хаффмана

Профессор Роберт Фано не смог доказать оптимальность своего кода Шеннона-Фано. Вместо экзамена он предложил студентам: докажите оптимальность или придумайте лучше. Дэвид Хаффман выбрал второе - и придумал. Идея проста до обидного: строй дерево снизу вверх, объединяя два наименее вероятных символа. Результат: длина кода символа x - $\lceil -\log_2 p(x) \rceil$ бит.

**Теорема Хаффмана**: среди всех однозначно декодируемых кодов Хаффман даёт минимальную ожидаемую длину. Гарантия: $H(X) \leq L_{Huffman} < H(X) + 1$ бит/символ. При блочном кодировании n символов: $H(X) \leq L/n < H(X) + 1/n$ - избыток стремится к нулю.

Хаффман работает идеально, когда вероятности - степени двойки: тогда $-\log_2 p(x)$ целое, и код достигает H(X). Но 'e' в английском имеет p ≈ 0.127, а $-\log_2(0.127) ≈ 2.98$ бит - не целое. Хаффман округляет до 3, теряя 0.02 бита/символ. Арифметическое кодирование решает это.

LZ77: скользящее окно

Хаффман знает статистику символов заранее. LZ77 (Лемпель и Зив, 1977) - нет. Он вообще не считает частоты. Вместо этого: держит окно из последних N байт и ищет в нём повторения. 'abcabcabc' - это не 9 независимых символов, это 'abc' + ссылка назад три раза.

**LZ77 токен**: тройка (offset, length, next_char). offset - сколько позиций назад в окне, length - длина совпадения, next_char - следующий не совпавший символ. При нулевом совпадении: (0, 0, char). Окно в gzip - 32 KB, в zstd - до 128 MB.

LZ77 - это неявная контекстная модель. Чем длиннее окно, тем больше контекста, тем лучше сжатие. DEFLATE (gzip, ZIP, PNG) - это LZ77 + Хаффман: LZ77 ловит повторения, Хаффман дожимает оставшуюся статистику. Этот тандем ежедневно обрабатывает петабайты HTTP-трафика.

LZ78, LZW и патентный скандал с GIF

1994 год. Unisys объявляет: компании, использующие GIF на коммерческих сайтах, обязаны платить лицензию за LZW - алгоритм, лежащий в основе формата. Веб разделился: платить или искать альтернативу. Ответом стал PNG (1996) на свободном DEFLATE.

LZW (Уэлч, 1984) - улучшение LZ78 (Лемпель и Зив, 1978). Ключевой трюк: словарь не передаётся отдельно. Декодер строит его сам, применяя те же правила что и кодер. Синхронизация - автоматическая.

ANS: современный предел

2009-2014. Ярослав Душа (Jarek Duda), математик из Кракова, разрабатывает **ANS (Asymmetric Numeral Systems)**. Задача: получить скорость Хаффмана при оптимальности арифметического кодирования. Это казалось невозможным - Хаффман быстрый, но теряет до 1 бита; арифметика оптимальна, но медленная. ANS решил обе проблемы.

Сегодня ANS - в zstd (Facebook), LZFSE (Apple), кодеке AV1 (Google/Alliance for Open Media) и H.266. Каждый раз когда Chrome сжимает HTTP/2 HPACK-заголовки или Safari декодирует видео HEVC - там ANS или его потомок.

**Граница Шеннона**: ни один код не может сжать источник с энтропией H(X) ниже H(X) бит/символ в среднем. Это нижняя граница. ANS приближается к ней практически вплотную при реальных скоростях работы - именно поэтому Душа получил несколько наград IEEE.

Ключевые идеи

• **Хаффман**: дерево снизу вверх, частые символы - короткие коды. Гарантия: $H(X) \leq L < H(X)+1$. Основа gzip
• **LZ77**: скользящее окно, повторения → ссылки назад. Ловит структуру без знания статистики заранее
• **LZW**: явный словарь без передачи - декодер строит его сам. История с GIF и патентом ускорила создание PNG
• **ANS**: ≈ H(X) при скорости Хаффмана. Современный стандарт в zstd, AV1, H.266 - лучший из существующих кодеров

Связанные темы

Кодирование без потерь - практическое воплощение границы Шеннона:

• Энтропия Шеннона — H(X) - теоретический предел, к которому стремятся все эти алгоритмы
• Арифметическое кодирование и ANS — Следующий уровень: дробные биты, ANS в деталях, контекстные модели

Вопросы для размышления

• Почему gzip использует LZ77 И Хаффман вместе, а не только один? Что каждый добавляет?
• Файл с абсолютно случайными байтами (максимальная энтропия). Как поведут себя LZ77 и Хаффман? Почему?
• В чём принципиальное различие LZ-методов и Хаффмана с точки зрения 'модели источника'?

Связанные уроки

• alg-01-big-o
• ds-06-hash-intro