Арифметическое кодирование и ANS

Каждое видео на YouTube сжато H.265, каждый архив 7-Zip использует range coding - всё это прямые потомки математики 1970-х. А zstd (который использует Facebook для сжатия трафика) использует ANS, опубликованный польским математиком в 2009.

• **CABAC** в H.264/H.265 использует арифметическое кодирование с контекстными моделями, что позволяет Netflix сжимать видео эффективнее старых кодеков.
• **zstd** (Facebook, 2016) использует tANS и достигает скорости сжатия 400+ МБ/с при сжатии, сравнимом с zlib-9.
• **LLM как компрессор**: GPT-4 неявно является мощнейшим компрессором текста - понимать языковые паттерны и предсказывать = сжимать.

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

• Lossless Coding: Huffman, LZ

Арифметическое кодирование

Хаффман назначает каждому символу целое число бит. Но что, если символ встречается с вероятностью 0.9? Оптимальная длина кода - 0.152 бита, а Хаффман даст минимум 1 бит - потери 6.5x. Арифметическое кодирование решает это элегантно: вместо кодирования символов по одному оно кодирует всю последовательность как единственное вещественное число в интервале [0, 1). Каждый новый символ сужает этот интервал пропорционально своей вероятности.

**Принцип:** Начинаем с [0, 1). Для каждого символа x с вероятностью p(x) берём соответствующий подинтервал. После обработки всей последовательности выбираем любое число в финальном интервале. Длина кода ≈ −log₂(произведение вероятностей) = сумма −log₂(p(xᵢ)) = H бит. Средняя избыточность: менее 2 бит на всю последовательность (не на символ!).

ANS: Asymmetric Numeral Systems

ANS (Ярослав Душа, 2009) - революционный метод, объединяющий оптимальность арифметического кодирования со скоростью Хаффмана. Идея: представить состояние кодера как натуральное число, а кодирование - как переход между состояниями. rANS (range ANS) работает с диапазоном чисел, tANS (tabled ANS) использует таблицу переходов для максимальной скорости. Оба метода обратимы - декодирование идёт в обратном порядке.

**rANS кодирование:** Состояние x ∈ [L, bL). Для символа s с вероятностью p(s) = fs/M: кодирование нормализует x до [fs, b·fs), выдаёт биты, затем x_new = (x/fs)·M + CDF(s) + (x mod fs). Декодирование идёт в обратном порядке. Избыточность практически нулевая.

Range Coding

Range coding (Мартин, 1979) - практическая реализация арифметического кодирования через целые числа. Вместо вещественных чисел используется целочисленный диапазон [low, high) большой ширины (обычно 32 или 64 бита). При сужении диапазона ниже порога старший байт выдаётся в поток, а диапазон масштабируется. Это устраняет проблему потери точности с плавающей запятой.

**Range coder:** Поддерживает два числа: low (нижняя граница) и range (ширина). Для символа с частотой [cumFreq, cumFreq+freq) из total: range_new = range × freq / total; low_new = low + range × cumFreq / total. Пока range < MIN_RANGE: выдаём старший байт low, сдвигаем. Применяется в 7-Zip (LZMA), bzip2, H.264 CABAC.

Оптимальное кодирование

Что значит «оптимальное» сжатие? С точки зрения теории информации - достижение нижней границы H(X) бит/символ для i.i.d. источника. Но реальные данные не i.i.d.: текст имеет контекст, изображения - корреляцию соседних пикселей. Оптимальное сжатие требует хорошей модели источника. Лучший кодер с плохой моделью проигрывает хорошей модели с простым кодером.

**Разделение модели и кодирования (Rissanen, 1976):** Любой компрессор = модель + энтропийный кодер. Модель предсказывает вероятность следующего символа, кодер кодирует по этой вероятности. Современные LLM - это модели источника; если передавать текст через LLM-модель + арифметический кодер, достигается очень высокое сжатие.

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

• **Арифметическое кодирование** кодирует всю последовательность как одно число, достигая H(X) + ε бит с ε < 2 бит на всю последовательность.
• **ANS** (rANS/tANS) совмещает оптимальность арифметического кодирования с высокой скоростью Хаффмана через целочисленные операции.
• **Range coding** - практическая реализация арифметического кодирования через целые числа. Основа LZMA (7-Zip) и CABAC (H.264).
• **Модель важнее кодера**: сжатие = модель + энтропийный кодер. Лучшая модель даёт больший выигрыш, чем лучший кодер.

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

Арифметическое кодирование завершает картину энтропийных кодеров и открывает путь к продвинутым темам:

• Кодирование без потерь: Хаффман, LZ — Предыдущий урок: символьные коды и словарные методы
• Сжатие данных: JPEG, H.265, LLM — Применение арифметического кодирования в реальных форматах
• Information Theory в ML — ELBO и вариационный вывод связаны с кодированием через принцип MDL

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

• Почему ANS декодирует символы в обратном порядке? Как это влияет на потоковое декодирование?
• DeepMind показала, что LLM сжимают лучше gzip. Что это говорит нам об «интеллекте» как понимании структуры данных?
• Если бы вы проектировали новый видеокодек, что выбрали бы как энтропийный кодер - Хаффман, CABAC или ANS, и почему?

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

• alg-01-big-o