Кратко и по делу — сравнение по сценарию использования, эффективности и ограничениям (обозначения: $A$ — размер алфавита, $N$ — длина входа, $D$ — размер словаря, $H$ — энтропия источника, $L$ — средняя длина кода).
1) Huffman
- Когда выгоден: простой статистический источник, маленькое $A$ (например байтовый алфавит), требование низкой задержки и малых затрат на декодер (аппаратные реализации, реальное время, блоки с быстрым доступом).
- Сильные стороны: простота реализации, быстрый бинарный код с поиском по таблице, легко делается канонический Huffman для компактного представления кодов.
- Ограничения по сжатию: оптимален только при целочисленных длинах кодов; для нулевого порядка даёт оценку $H\le L<H+1$ — до 1 бита/символ от энтропии.
- Сложность и память: построение таблицы $O(A\log A)$; кодирование/декодирование $O(N)$ (обычно $O(1)$ на символ с таблицей). Память $O(A)$ для дерева/таблицы кодов и $O(\sum \text{длина кода})$ для представления кодов.
2) LZW (словник)
- Когда выгоден: данные с повторяющимися подстроками и структурой (текст, лог-файлы, множество простых бинарных форматов, GIF), когда нужен адаптивный метод без предварительного моделирования.
- Сильные стороны: адаптивный словарь формируется на лету (нет необходимости в частотах заранее), простая реализация, хорош для умеренно повторяющихся данных.
- Ограничения по сжатию: неэффективен для высокоэнтропийных или почти случайных данных; компрессия зависит от ограничений словаря; для коротких потоков словарь малоэффективен.
- Сложность и память: амортизированное время ~$O(N)$ (операция вставки/поиска — хеш/trie, обычно $O(1)$ амортизировано), в худшем случае поиск префикса может быть дороже. Память пропорциональна $O(D)$ (число записей в словаре, например типичные реализации ограничивают $D$ до $2^{12}$ или $2^{16}$ — $2^{12}=4096$ и т.п.), плюс память для хранения строк/указателей.
3) Arithmetic coding (включая range coder)
- Когда выгоден: требуется максимальная компрессия близко к энтропии, источники со скошенными/дробными вероятностями, сложные статистические модели (контекстные модели, PPM, нейро-модели) — архивирование, энкодинг с моделированием.
- Сильные стороны: можно получить среднюю длину практически $L\approx H$ (приближение сколь угодно близко при достаточной точности), гибкость с дробными вероятностями и контекстными моделями.
- Ограничения: более сложная реализация, требования к точной арифметике/ренормализации; чувствительность к ошибкам (одна ошибка может испортить длинный участок) и сложность для прямого произвольного доступа; раньше были патенты (обычно уже не актуально).
- Сложность и память: кодирование/декодирование $O(N)$ с постоянным (но большим) коэффициентом на символ; требует целочисленной/фиксированной точности $P$ бит (часто $P=32$ или $64$) для регистра диапазона; модель требует $O(A)$ памяти для частот и дополнительной памяти для контекстной модели (может быть очень большой для PPM/нейро-моделей).
Дополнительные практические замечания (кратко)
- Адаптивность: LZW и adaptive Huffman/Arithmetic не требуют предварительной передачи модели; статический Huffman требует передачи таблицы. Arithmetic + мощная модель даёт наилучший результат при высоком вычислительном бюджете.
- Потоковая обработка и перестройка: все методы могут быть потоковыми, но arithmetic/range coder чаще требует аккуратной ренормализации; Huffman проще для аппаратного/параллельного декодирования; LZW поддерживает простой потоковый декодер, но словарь делает рандомный доступ проблематичным.
- Устойчивость к ошибкам: ни один из методов не даёт полной устойчивости; Huffman/блочный режим легче ресинхронизировать; arithmetic чувствительнее к битовым ошибкам.
- Выбор по сценарию:
- Нужна скорость, простота и низкая память → Huffman (или канонический Huffman).
- Данные с длинными повторяющимися подстроками, лёгкая адаптация → LZW.
- Максимальная компрессия с продвинутой моделью → Arithmetic/range coder (при готовности платить за время и память).
Если нужно, могу дать короткую сводную таблицу со сложностями/памятью в виде строк.