Сжатие данных: JPEG, H.265, LLM

Каждое JPEG-фото на вашем телефоне - это 50-летний алгоритм Насира Ахмеда (DCT, 1974). Каждый токен в ChatGPT - это алгоритм Gage (BPE, 1994). Теория информации незаметно пронизывает каждый байт данных.

• **Netflix** адаптивно меняет настройки H.265 в зависимости от сложности сцены. «Тёмные» сцены «Игры престолов» были сжаты хуже - и зрители заметили блочные артефакты. Netflix потом переобработал весь контент.
• **Apple HEIF** (iPhone 12+) хранит живые фото в H.265 контейнере с прозрачностью. Размер фото уменьшился в 2 раза без потери видимого качества.
• **Llama 3** перешёл с 32K на 128K токенов в словаре и улучшил поддержку не-английских языков и кода - прямой эффект токенизации.

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

• Rate-Distortion Theory

Transform Coding

Transform coding - универсальный принцип современного сжатия: преобразовать сигнал в домен, где энергия концентрируется в малом числе коэффициентов. DCT (дискретное косинусное преобразование) для изображений, MDCT для аудио, лифтинговые вейвлеты для JPEG2000. После трансформации большинство коэффициентов близки к нулю и хорошо квантуются.

**Karhunen-Loève Transform (KLT):** теоретически оптимальное преобразование - собственные векторы ковариационной матрицы. Декоррелирует компоненты полностью. DCT - практическое приближение KLT для стационарных сигналов. Для типичных изображений DCT почти оптимален.

Видеосжатие: H.265 и AV1

Видео - это последовательность изображений с высокой темпоральной корреляцией: соседние кадры отличаются незначительно. Видеокодеки используют это: inter-кодирование находит блок в предыдущем кадре (motion estimation) и кодирует только разницу (residual). H.265/HEVC и AV1 добавляют предсказание внутри кадра, иерархические блочные структуры и сложные энтропийные кодеры.

**Inter-кодирование:** текущий блок = predicted + residual. Predicted = блок из reference frame + motion vector. Residual = DCT(current − predicted). Если residual мал - почти нет потерь информации. Motion compensation может уменьшить энергию residual в 10-100 раз по сравнению с intra-кодированием.

Neural Compression

Нейросетевые кодеки (2017-2023) заменяют фиксированные трансформации (DCT) на обученные. Архитектура: энкодер → квантование → энтропийное кодирование → декодер. Это по сути VAE с явной оптимизацией R-D компромисса: L = rate + λ·distortion. Модели Balle et al. (Google), VCT, ELIC превзошли AV1 при низких битрейтах по PSNR и SSIM.

**Нейросетевой кодек:** min_{θ,φ} E[−log p_θ(ŷ)] + λ·d(x, decoder_φ(ŷ)), где ŷ = quantize(encoder(x)). Entropy model p_θ(ŷ) - гиперприорная сеть, оценивающая вероятности для ANS/арифм. кодера. При λ=0: только скорость (максимальное сжатие). При λ→∞: только качество.

Токенизация LLM как сжатие

BPE-токенизатор (Byte Pair Encoding) - это компрессор без потерь: он находит часто встречающиеся подстроки и заменяет их одним токеном. По сути это LZ78/LZW применённый к тексту. Словарь токенов - это «словарь» в смысле LZW. Количество токенов на слово ≈ 1/степень_сжатия. GPT-4 использует ~100K токенов, сжимая английский текст примерно в 3-4 раза относительно UTF-8.

**BPE как компрессия:** Инициализируем словарь байтами. Итеративно: находим пару с максимальной частотой, добавляем её в словарь. Повторяем V раз (V = размер словаря). Результат: оптимизированный словарь для данного корпуса. Compression ratio ≈ 3-4x для английского. LLM работает в токенном пространстве - токенизация влияет на эффективность модели.

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

• **Transform coding:** DCT/MDCT концентрирует энергию → квантование незначимых коэффициентов → энтропийное кодирование. Основа JPEG, MP3, H.265.
• **Видеосжатие:** inter-кодирование = motion estimation + residual coding. AV1 эффективнее H.264 на 65% при том же качестве.
• **Нейросетевые кодеки:** VAE-архитектура + оптимизация R(D). ELIC (2022) превосходит AV1 при низких битрейтах.
• **BPE-токенизация** - это LZW для текста. Качество токенизации влияет на математику, кодинг и многоязычность LLM.

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

Сжатие данных объединяет все разделы теории информации в практику:

• Rate-Distortion Theory — Теоретическая основа для всех lossy-форматов и нейросетевых кодеков
• Кодирование без потерь: Хаффман, LZ — BPE - это вариант LZ77/LZW применённый к тексту
• Information Theory в ML — Neural compression = VAE + явная R-D оптимизация

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

• BPE токенизация - это без-потерь или с-потерями для текста? Как это влияет на возможности LLM?
• Нейросетевые кодеки обучаются на конкретных данных (фотографии людей, природа). Что произойдёт при сжатии медицинских изображений?
• AV1 - открытый кодек, свободный от патентов. Как это повлияло на его принятие в индустрии по сравнению с H.265?

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

• alg-01-big-o
• dsp-05