LZ78

LZ78 — это алгоритм сжатия данных без потерь, относящийся к классу словарных методов (Lempel-Ziv). Разработан в 1978 году израильскими учёными Абрахамом Лемпелем и Якобом Зивом как усовершенствование их предыдущего алгоритма LZ77. LZ78 лёг в основу многих популярных форматов сжатия, включая GIF, TIFF и ранние версии LZW.

История создания

Алгоритм LZ78 был опубликован в 1978 году в статье «Compression of Individual Sequences via Variable-Rate Coding» (IEEE Transactions on Information Theory). Разработчики стремились устранить недостатки LZ77, который требовал хранения скользящего окна и имел ограничения по длине совпадений. В LZ78 была предложена принципиально иная структура: вместо поиска повторяющихся строк в окне использовался растущий словарь фраз, что упрощало реализацию и снижало требования к памяти.

В 1984 году Терри Уэлч (Terry Welch) модифицировал LZ78, создав алгоритм LZW (Lempel-Ziv-Welch), который стал широко применяться в форматах GIF (CompuServe, 1987) и TIFF, а также в утилите compress для UNIX. В 1985 году LZ78 был запатентован в США (патент № 4,464,650), что впоследствии привело к юридическим спорам, особенно в связи с использованием LZW в GIF.

Принцип работы

LZ78 относится к словарным методам сжатия, где словарь строится динамически в процессе кодирования. В отличие от LZ77, где совпадения ищутся в скользящем окне, LZ78 использует глобальный словарь фраз, который пополняется по мере обработки данных.

Кодирование

Алгоритм работает следующим образом:

1. Инициализация: словарь изначально пуст или содержит все возможные одиночные символы (в зависимости от реализации). Каждому элементу словаря присваивается уникальный индекс (целое число).
2. Чтение входного потока: алгоритм последовательно читает символы, накапливая текущую фразу (самую длинную последовательность, уже присутствующую в словаре).
3. Поиск совпадения: если текущая фраза есть в словаре, алгоритм продолжает добавлять следующий символ, пока не встретит фразу, отсутствующую в словаре.
4. Вывод кода: когда найдена фраза, которой нет в словаре, алгоритм выводит пару (индекс предыдущей фразы, следующий символ). Индекс указывает на самую длинную совпавшую фразу из словаря, а символ — это новый символ, который не входит в совпадение.
5. Добавление в словарь: новая фраза (предыдущая фраза + новый символ) добавляется в словарь с новым индексом.
6. Повторение: процесс продолжается до конца входных данных.

Пример кодирования строки «ababcbababaaaa»:

• Словарь изначально пуст (или содержит пустую строку с индексом 0).
• Читаем 'a': нет в словаре → вывод (0, 'a'), добавляем «a» с индексом 1.
• Читаем 'b': нет в словаре → вывод (0, 'b'), добавляем «b» с индексом 2.
• Читаем 'a': есть в словаре (индекс 1), читаем следующий 'b' → «ab» нет в словаре → вывод (1, 'b'), добавляем «ab» с индексом 3.
• Читаем 'c': нет в словаре → вывод (0, 'c'), добавляем «c» с индексом 4.
• Читаем 'b': есть в словаре (индекс 2), читаем 'a' → «ba» нет в словаре → вывод (2, 'a'), добавляем «ba» с индексом 5.
• Читаем 'b': есть в словаре (индекс 2), читаем 'a' → «ba» есть в словаре (индекс 5), читаем 'b' → «bab» нет в словаре → вывод (5, 'b'), добавляем «bab» с индексом 6.
• Читаем 'a': есть в словаре (индекс 1), читаем 'a' → «aa» нет в словаре → вывод (1, 'a'), добавляем «aa» с индексом 7.
• Читаем 'a': есть в словаре (индекс 1), читаем 'a' → «aa» есть в словаре (индекс 7), читаем 'a' → «aaa» нет в словаре → вывод (7, 'a'), добавляем «aaa» с индексом 8.
• Конец данных.

Выходной поток: (0,'a'), (0,'b'), (1,'b'), (0,'c'), (2,'a'), (5,'b'), (1,'a'), (7,'a').

Декодирование

Декодирование LZ78 является симметричным процессом, при котором словарь восстанавливается идентично кодировщику. Декодер читает пары (индекс, символ) и:

1. Извлекает из словаря фразу по индексу.
2. Добавляет к ней полученный символ — это и есть декодированная часть.
3. Добавляет полученную фразу в словарь с новым индексом (тем же, что и у кодировщика).

Сравнение с LZ77

Модификации и производные

LZW (Lempel-Ziv-Welch)

Наиболее известная модификация LZ78, разработанная Терри Уэлчем в 1984 году. Отличия от LZ78:

• Словарь инициализируется всеми возможными одиночными символами (например, 256 байт для 8-битных данных).
• Выходной код — только индекс фразы, без дополнительного символа.
• При добавлении новой фразы в словарь используется принцип «сначала код, потом фраза» (код выводится до добавления фразы в словарь).

LZW использовался в формате GIF (до 2003 года, когда истёк патент), в TIFF, PDF, а также в утилите compress для UNIX. В 1990-х годах возникли юридические споры вокруг патента Unisys на LZW, что привело к ограничению его использования в свободном программном обеспечении.

LZMW и LZAP

• LZMW (Lempel-Ziv-Miller-Wegman) — модификация, где в словарь добавляются не только фразы вида «предыдущая фраза + символ», но и комбинации двух последних фраз.
• LZAP (Lempel-Ziv-All-Prefixes) — расширение, добавляющее в словарь все префиксы каждой новой фразы.

LZSS (Lempel-Ziv-Storer-Szymanski)

Хотя формально LZSS является модификацией LZ77, он часто сравнивается с LZ78. В LZSS используется битовый флаг для различения ссылок на словарь и литеральных символов, что улучшает сжатие по сравнению с базовым LZ77.

Применение

LZ78 и его производные нашли широкое применение в различных областях:

• Графические форматы: GIF (LZW), TIFF (LZW), PNG (использует Deflate, основанный на LZ77, но с элементами LZ78).
• Архиваторы: compress (UNIX), ранние версии PKZIP (использовали LZW).
• Сетевые протоколы: V.42bis (сжатие данных в модемах), PPP Compression Control Protocol (CCP).
• Файловые системы: сжатие в NTFS (использует LZNT1, основанный на LZ77, но с некоторыми идеями из LZ78).
• Встраиваемые системы: благодаря низким требованиям к памяти, LZ78 применялся в ранних микроконтроллерах и устройствах хранения данных.

Критика и ограничения

Основные недостатки LZ78:

• Неограниченный рост словаря: без управления размером словаря он может занимать слишком много памяти, особенно при сжатии больших файлов. На практике вводят ограничение на максимальное количество фраз (например, 4096 для LZW в GIF).
• Патентные ограничения: алгоритм LZW был запатентован, что препятствовало его свободному использованию в течение 20 лет (1985–2003). Это привело к разработке альтернатив, таких как Deflate (основан на LZ77).
• Меньшая эффективность на коротких данных: для небольших объёмов данных словарь не успевает накопить достаточное количество фраз, и сжатие может быть хуже, чем у LZ77.
• Уязвимость к атакам: в некоторых реализациях LZ78 (например, в GIF) возможны атаки на основе словарных коллизий, что может привести к утечке данных.

Интересные факты

• LZ78 стал первым алгоритмом сжатия, который использовал динамически растущий словарь, что впоследствии повлияло на развитие методов сжатия с контекстным моделированием (PPM, PAQ).
• Формат GIF, использующий LZW, долгое время был основным форматом для анимированной графики в интернете, несмотря на патентные споры.
• В 1990-х годах компания Unisys пыталась взимать лицензионные отчисления за использование LZW в GIF, что вызвало массовое недовольство и привело к созданию формата PNG (Portable Network Graphics), который использует алгоритм Deflate.
• Алгоритм LZ78 является основой для стандарта сжатия V.42bis, рекомендованного Международным союзом электросвязи (ITU) для модемной связи.

Источники

• Lempel, A., Ziv, J. (1978). «Compression of Individual Sequences via Variable-Rate Coding». IEEE Transactions on Information Theory, 24(5), 530–536.
• Welch, T. A. (1984). «A Technique for High-Performance Data Compression». Computer, 17(6), 8–19.
• Nelson, M., Gailly, J.-L. (1996). The Data Compression Book (2nd ed.). M&T Books.
• Salomon, D. (2007). Data Compression: The Complete Reference (4th ed.). Springer.
• Bell, T. C., Cleary, J. G., Witten, I. H. (1990). Text Compression. Prentice Hall.