Кратко и по делу.
Что такое LZ78 / LZW — структура и алгоритм
- LZ78 (обобщённо):
- Держит словарь уникальных фраз (строк). Каждая новая запись — предыдущая фраза + следующий символ.
- Кодирует вход как последовательность пар $(\text{индекс\_предш},\text{символ})$, где $\text{индекс\_предш}$ — индекс в словаре (0 для пустой), а $\text{символ}$ — следующий символ.
- При кодировании: читаем максимально длинную фразу, уже лежащую в словаре; выводим её индекс и следующий символ; добавляем в словарь конкатенацию (фраза + символ).
- Декодер воспроизводит фразы по тем же правилам — словарь строится детерминированно из входных кодов.
- LZW (практическая модификация LZ78, чаще используется):
- Словарь инициализируется всеми одиночными символами алфавита.
- Процесс: пусть текущая фраза $P$ (начально пустая). Читаем символ $c$. Если $P+c$ есть в словаре — расширяем $P$. Иначе: выводим код для $P$, добавляем в словарь запись $P+c$, устанавливаем $P=c$. В конце выводим код для оставшегося $P$.
- На выходе — последовательность кодов (целых чисел), каждый код соответствует фразе в словаре. Словарь расширяется по одному коду при появлении новой комбинации.
- Частая реализация: коды фиксированной/увеличивающейся ширины; типичный предел — например, $2^{12}=4096$ записей (12 бит).
Преимущества LZ-семейства
- Адаптивность: не требует предварительной статистики; словарь строится онлайн.
- Хорошо ловит повторяющиеся подстроки и большие шаблоны (длинные фразы -> высокая компрессия на повторах).
- Быстрая декодировка (детерминированное восстановление словаря).
- Подходит для потоковой обработки (single-pass кодер/декодер).
Недостатки LZ относительно Huffman/статистических методов
- Не даёт оптимальной энтропийной кодировки для символного распределения: кодовые слова (индексы) имеют собственное распределение, которое не обязательно оптимален.
- На коротких файлах или при малой периодичности фраз словарь плохо наполняется — накладные коды (ширина кодов) делают сжатие хуже.
- Зависимость от размера словаря: если ограничивать словарь, эффективность падает; если давать расти — растёт память.
- Ошибки/потери в потоке могут сломать последующее декодирование (потому что словарь синхронизирован).
Преимущества Huffman (сравнение)
- Статистический (символьный) энтропийный кодер: для известного распределения строит оптимальный префикс-код минимальной средней длины.
- Эффективен на коротких блоках для которых частоты надёжно оцениваются.
- Прост в реализации и декодировании; малые накладные расходы при небольшом алфавите.
- Но требует модели частот (статическая — две прохода / таблица; адаптивная — чуть менее эффективна).
Когда и как сочетаются LZ и Huffman (или арифметическое кодирование)
- Общая идея: LZ уменьшает корреляцию/повторяемость, превращая вход в поток кодовых индексов; затем применяют энтропийный кодер (Huffman или арифметика) к этим индексам/символам, чтобы достичь близкого к энтропийному предела.
- Практические примеры:
- DEFLATE = LZ77 + Huffman (LZ для поиска совпадений, потом два Huffman-дерева для литералов/длину/расстояний).
- LZW часто использует чистые коды, но может дополнительно упаковываться в битовый поток и затем подвергаться статистической обработке; в других схемах LZ-выход (индексы) кодируется арифметикой для лучшего сжатия.
- Почему это полезно:
- LZ устраняет долгие повторы (снижение редундантности на уровне подстрок), Huffman/арифметика оптимизируют представление получившихся символов/индексов под их частоты.
- В сумме часто получается лучше, чем только LZ или только Huffman.
Практические соображения и рекомендации
- Для текстов/файлов с повторами и структурой: LZ (+после него энтропийный кодер) обычно даёт хорошие результаты.
- Для данных, где нет длинных повторов, но есть явная статистика символов: Huffman/арифметика сами по себе могут быть предпочтительнее.
- Для потоковой/встраиваемой реализации выбирают ограничение словаря (периодические сбросы) и кодовую ширину (например, до 12–16 бит).
- Энтропийное кодирование выходных LZ-кодов (особенно арифметика) даёт приближение к теоретической границе: средняя длина кода стремится к энтропии $H(X)$ входного источника, т.е. среднее число бит на символ не может быть меньше $H(X)$.
Краткая формула-напоминание
- Энтропийная граница: средняя длина кода $L$ удовлетворяет $L\ge H(X)$, и комбинирование LZ + энтропийный кодер приближает достижение этой границы на больших объёмах данных.
Вывод в одну строку
- LZ78/LZW строят словарь фраз онлайн (LZ78 выдаёт пары $(индекс,символ)$, LZW — коды фраз), эффективно устраняют повторяющиеся подстроки; Huffman оптимизирует представление на уровне символов/индексов. Лучшие практики — комбинировать: LZ для поиска повторов, затем Huffman/арифметика для компактного кодирования выходных кодов.