Вопрос #1615370

Кратко — по сути и с пояснениями.
Общие теоретические ориентиры
- Энтропия источника: \(\;H(X) = -\sum_x p(x)\log_2 p(x)\;\). Ни один идеально универсальный безусловный код не даст среднего количества бит меньше \(\;H(X)\;\) (для даного статистического закона).
- Для практических кодов важны три компонента: байты, нужные для описания модели/слов.словаря, и длина кода данных при этой модели. Часто общий объём: \(\;\text{bits} = \text{model\_size} + \sum -\log_2 p_\theta(x_i)\;\).
Статистические методы (Huffman, Arithmetic/ANS)
- Принцип: кодирование символов по их вероятностям.
- Факты:
- Хаффман: гарантирует среднюю длину \(L\) с оценкой \(\;H \le L < H + 1\;\) бит/символ (символьная кодировка целыми битами).
- Арифметическое кодирование / ANS: позволяет приближаться к \(\;H\;\) произвольно близко, кодирует дробные биты за символы; ANS быстрее и лучше подходит для практики.
- Плюсы:
- Простота и низкие затраты памяти; хорошие для известных распределений маленького алфавита.
- Арифметическое/ANS эффективны при точной модели вероятностей и при моделях контекста.
- Поддерживают адаптивность (обновление частот онлайн).
- Минусы:
- Нужна хорошая модель вероятностей; простые модели (независимые символы) игнорируют высоко-порядковые зависимости.
- Арифметическое кодирование последовательное, требует больше вычислений; ANS решает часть этой проблемы.
- Когда выгодно:
- Малые алфавиты с нетривиальными частотами (текст с хорошей статистикой символов/байтов).
- Когда есть сильный, вычислимо описываемый статистический модель (например, контекстные модели PPM, n-gram), особенно в паре с арифметическим/ANS кодером.
Словарные методы (LZ77, LZ78 и их реализации: DEFLATE)
- Принцип: заменяют повторяющиеся подстроки ссылками на ранее встречавшиеся фрагменты (LZ77 — скользящее окно; LZ78 — построение словаря).
- Плюсы:
- Очень хорошо выявляют локальные и длинные повторы и повторяющиеся блоки (репликация, логи, двоичные паттерны).
- Работают без предварительного обучения — «универсальны» для многих типов данных.
- Эффективны в потоках (LZ77 естественно онлайн со скользящим окном).
- На практике (DEFLATE = LZ77 + Huffman) дают отличный компромисс скорость/сжатие для файлов, архивов, текстов с повторениями.
- Минусы:
- Могут плохо работать на данных с высокой энтропией или где повторы не локальны (рекурсивные структуры, семантические повторения).
- Для редких но статистически предсказуемых последовательностей (высокие порядокные зависимости без прямого повтора) уступают методам с моделью вероятности.
- Когда выгодно:
- Данные с длинными/частыми повторами: текст с повторяющимися фразами, логи, бинарные файлы с повторяющимися блоками, компилированные ресурсы.
- Потоковое сжатие и приложения с ограниченной памятью/реaltime.
Модели с обучением (нейросетевые компрессоры, статистические обучаемые модели)
- Принцип: учат параметрическую модель \(p_\theta(x)\) (ядерные модели последовательностей, RNN/Transformer, Flow/VAE/Autoregressive) и кодируют по этой модели (обычно через арифметику/ANS, иногда bits-back). Для потерьных компрессоров оптимизируют компромисс «rate–distortion».
- Плюсы:
- Могут захватывать очень сложные долгосрочные и высокоуровневые зависимости, которые традиционные статистические или LZ методы не моделируют.
- Для структурированных высокоразмерных данных (изображения, аудио, видео, табличные данные с семантикой) нейросетевые методы (lossy) зачастую дают лучшие rate–distortion результаты.
- В lossless вариантах, при хорошем обучении, могут превзойти классические методы на специфичных доменах (медицинские снимки, геномика, лог-файлы с характерными паттернами).
- Минусы:
- Требуют обучающего набора, значительных вычислений и памяти; модельный overhead (\(\text{model\_size}\)) может быть большим, поэтому на малых файлах выгодность сомнительна.
- Кодирование/декодирование часто медленнее и ресурсоёмко; нужны специальные приёмы (bits-back, quantization, entropy model pruning) для эффективности.
- Риск переобучения и плохой генерализации на данных вне тренировочного распределения.
- Когда выгодно:
- Большие потоки однотипных данных, где можно амортизировать стоимость модели (серверное архивирование, специализированные датасеты).
- Сжатие мультимедийных данных в lossly режиме (изображения/видео) с требованием высокого качества при низком битрейте.
- Когда нужно моделировать долгие/сложные зависимости и есть доступ к обучающим данным и вычислениям.
Практические соображения и рекомендации (правила выбора)
- Малый размер данных / неизвестный домен: LZ77/DEFLATE — надёжный выбор (быстро, без обучения).
- Хорошо известная статистика с маленьким алфавитом и строгие требования к битовой эффективности: контекстные статистические модели + арифметическое/ANS.
- Длинные/дальние повторы и потоковое сжатие: LZ77 и его вариации.
- Специфичный домен больших объёмов и допустимо обучать/передавать модель: нейросетевые компрессоры (lossless для узко-специфичных данных; lossy для мультимедиа) могут дать лучшее качество/битрейт.
- Ограничения по ресурсам и задержке: Huffman/LZ просты и быстры; neural — тяжёлая инфраструктура.
- Учтите стоимость модели: сравнивайте скорость и суммарные биты включая \(\text{model\_size}\).
Краткая сводка по преимуществам
- Huffman/арифметика: когда есть хорошая вероятностная модель на умеренном алфавите — близко к энтропии; арифметика/ANS лучше для тонкой фракционной экономии.
- LZ77/78: выигрыш на повторах и потоках без подготовки; простота и скорость.
- Нейросети/обучение: выигрыш при сложных структурных зависимостях и при больших однотипных наборах (или в lossly мультимедиа) — дороже по ресурсам и требует обучения.
Если нужно — могу привести короткий чеклист выбора под конкретный тип данных (текст, логи, изображения, видео, БД).