LZW

LZW (Lempel-Ziv-Welch) — это универсальный алгоритм сжатия данных без потерь, основанный на построении динамического словаря. Алгоритм был разработан в 1984 году израильским математиком Абрахамом Лемпелем, израильским учёным Якобом Зивом и американским инженером Терри Велчем. LZW является модификацией более ранних алгоритмов LZ77 и LZ78, предложенных Лемпелем и Зивом в 1977 и 1978 годах соответственно. Основное отличие LZW от предшественников — использование словаря, который изначально содержит все возможные одиночные символы входного алфавита, и последующее добавление в него новых строк (последовательностей символов) по мере их обнаружения. Алгоритм широко применялся в форматах изображений GIF (Graphics Interchange Format) и TIFF (Tagged Image File Format), а также в архиваторах, таких как Unix-утилита compress. В настоящее время LZW в значительной степени вытеснен более эффективными алгоритмами, такими как Deflate (используется в форматах PNG, ZIP, gzip), но сохраняет историческое значение и используется в некоторых специализированных областях.

История

Предшественники: LZ77 и LZ78

Основа для LZW была заложена в 1977 и 1978 годах, когда Абрахам Лемпель и Якоб Зив опубликовали два ключевых алгоритма сжатия: LZ77 и LZ78. LZ77 использует скользящее окно для поиска повторяющихся последовательностей, кодируя их ссылками на уже обработанные данные. LZ78, в отличие от LZ77, строит словарь фраз, который динамически расширяется. LZW, предложенный Терри Велчем, является усовершенствованием LZ78, направленным на повышение скорости сжатия и упрощение реализации.

Разработка Терри Велчем

В 1984 году Терри Велч, работавший в компании Sperry Research Center (позднее вошедшей в состав Unisys), опубликовал статью «A Technique for High-Performance Data Compression» в журнале IEEE Computer. В ней он описал алгоритм, который получил название LZW. Велч модифицировал LZ78, предложив инициализировать словарь всеми возможными одиночными символами, что устранило необходимость в специальном коде для обозначения конца входного потока и упростило процесс декодирования. Алгоритм быстро завоевал популярность благодаря своей эффективности и простоте.

Патентные споры

LZW стал предметом многолетних патентных споров, что существенно повлияло на его распространение. Компания Unisys, владевшая патентом на LZW (патент США № 4,558,302, выданный в 1985 году), начала взимать лицензионные отчисления за использование алгоритма, особенно в формате GIF. Это привело к тому, что разработчики свободного программного обеспечения стали искать альтернативы. В 1990-х годах патентные претензии Unisys вызвали широкий общественный резонанс, что в конечном итоге привело к созданию формата PNG (Portable Network Graphics), который использует алгоритм Deflate, не защищённый патентами. Патент на LZW истёк в 2003 году (в США) и в 2004 году (в большинстве других стран), после чего использование алгоритма стало свободным.

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

Общая схема

LZW сжимает данные, заменяя повторяющиеся последовательности символов (строки) на коды, которые являются индексами в словаре. Словарь изначально содержит все возможные одиночные символы входного алфавита (например, для 8-битных данных — 256 значений от 0 до 255). В процессе сжатия алгоритм просматривает входной поток, накапливая строку, пока она присутствует в словаре. Как только следующая строка перестаёт быть в словаре, алгоритм выводит код предыдущей строки, добавляет новую строку в словарь и начинает накопление заново с текущего символа.

Сжатие

Процесс сжатия можно описать следующими шагами:

1. Инициализация словаря всеми одиночными символами (коды 0–255 для 8-битных данных).
2. Чтение первого символа входного потока, присвоение его переменной w.
3. Чтение следующего символа k.
4. Если строка w + k есть в словаре, то присвоить w = w + k и перейти к шагу 3.
5. Если строки w + k нет в словаре, то вывести код строки w, добавить строку w + k в словарь с новым кодом, присвоить w = k и перейти к шагу 3.
6. После обработки всего входного потока вывести код последней строки w.

Декомпрессия

Декомпрессия LZW является обратным процессом, но имеет особенность: декодер восстанавливает словарь на основе полученных кодов, не имея его изначально. Алгоритм декомпрессии:

1. Инициализация словаря всеми одиночными символами (коды 0–255).
2. Чтение первого кода c из сжатого потока, вывод соответствующей строки s.
3. Присвоение prev = c.
4. Чтение следующего кода c.
5. Если код c есть в словаре, то вывести строку s, соответствующую c, и добавить в словарь строку prev + первый_символ(s).
6. Если кода c нет в словаре (возникает в особых случаях, когда кодируется строка, ещё не добавленная в словарь), то вывести строку prev + первый_символ(prev) и добавить её в словарь.
7. Присвоить prev = c и перейти к шагу 4.

Пример сжатия

Рассмотрим сжатие строки «ABABABA» с 8-битным алфавитом (A=65, B=66). Изначальный словарь содержит коды 0–255. В процессе сжатия:

• Читаем A (65), затем B (66). Строки «AB» нет в словаре, выводим код 65, добавляем «AB» с кодом 256.
• Текущая строка = B (66). Читаем A (65). Строки «BA» нет, выводим 66, добавляем «BA» с кодом 257.
• Текущая строка = A (65). Читаем B (66). Строка «AB» есть (код 256). Текущая строка = «AB». Читаем A (65). Строки «ABA» нет, выводим код 256, добавляем «ABA» с кодом 258.
• Текущая строка = A (65). Читаем B (66). Строка «AB» есть (256). Читаем A (65). Строки «ABA» нет, выводим 256, добавляем «ABA» с кодом 259 (но она уже есть, поэтому дубликат не добавляется — в реальности словарь не допускает дубликатов, но для простоты примера это опускается).
• Конец потока, выводим код последней строки (65). Итоговая последовательность кодов: 65, 66, 256, 256, 65.

Характеристики

Коэффициент сжатия

Эффективность LZW сильно зависит от характера данных. Наибольшее сжатие достигается на данных с повторяющимися последовательностями, таких как тексты, изображения с однородными областями или двоичные файлы с повторяющимися паттернами. Для случайных данных сжатие может быть неэффективным или даже приводить к увеличению размера (из-за добавления кодов словаря). Типичные коэффициенты сжатия для текстовых файлов составляют от 1,5 до 3 раз, для изображений — от 1,5 до 5 раз в зависимости от сложности.

Скорость работы

LZW является относительно быстрым алгоритмом, особенно при декомпрессии, которая требует только поиска в словаре. Скорость сжатия несколько ниже из-за необходимости поиска и добавления новых строк. В современных реализациях скорость может достигать десятков мегабайт в секунду на стандартных процессорах.

Использование памяти

Размер словаря в LZW обычно ограничен, чтобы избежать чрезмерного потребления памяти. В классической реализации словарь имеет фиксированный размер (например, 4096 или 65536 записей). При заполнении словаря алгоритм может либо прекратить добавление новых строк, либо сбросить словарь и начать заново. Это ограничение влияет на эффективность сжатия на больших объёмах данных.

Применение

Формат GIF

Наиболее известное применение LZW — формат изображений GIF, разработанный компанией CompuServe в 1987 году. GIF использует LZW для сжатия растровых изображений с палитрой до 256 цветов. Алгоритм хорошо подходит для изображений с большими однородными областями, таких как логотипы, диаграммы и анимации. Однако из-за патентных ограничений GIF потерял популярность для фотографий, уступив место JPEG и PNG.

Формат TIFF

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

Архиваторы

В 1980-х и начале 1990-х годов LZW использовался в архиваторах, таких как Unix-утилита compress (с расширением .Z) и ранние версии PKZIP. Однако с появлением более эффективных алгоритмов, таких как Deflate, LZW был вытеснен из большинства современных архиваторов.

Другие области

LZW применялся в некоторых протоколах передачи данных (например, в модемах), в системах резервного копирования и в специализированных встраиваемых системах, где требовалось простое и быстрое сжатие.

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

Патентные проблемы

Основным недостатком LZW были патентные ограничения, которые на десятилетия затруднили его использование в свободном программном обеспечении. Это привело к созданию альтернативных алгоритмов и форматов, таких как PNG и Deflate.

Эффективность

LZW уступает более современным алгоритмам сжатия, таким как Deflate (LZ77 + Huffman) и LZMA, как по степени сжатия, так и по скорости на некоторых типах данных. Для текстовых данных LZW часто проигрывает алгоритмам, использующим контекстное моделирование (например, PPM).

Ограничение словаря

Фиксированный размер словаря в LZW может приводить к снижению эффективности на больших объёмах данных, так как после заполнения словаря алгоритм перестаёт адаптироваться к новым повторяющимся последовательностям.

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

• Алгоритм LZW лёг в основу формата GIF, который стал одним из первых широко распространённых форматов для анимации в интернете.
• Патентные споры вокруг LZW привели к созданию PNG, который стал свободной альтернативой GIF.
• Терри Велч не получал отчислений за использование своего алгоритма, так как патент принадлежал компании Unisys.
• LZW используется в некоторых протоколах сжатия данных для модемов, например, в протоколе V.42bis.

Источники

• Welch, T. A. (1984). «A Technique for High-Performance Data Compression». IEEE Computer, 17(6), 8–19.
• Ziv, J., & Lempel, A. (1977). «A Universal Algorithm for Sequential Data Compression». IEEE Transactions on Information Theory, 23(3), 337–343.
• Ziv, J., & Lempel, A. (1978). «Compression of Individual Sequences via Variable-Rate Coding». IEEE Transactions on Information Theory, 24(5), 530–536.
• Nelson, M. (1992). «The Data Compression Book». M&T Books.
• Salomon, D. (2007). «Data Compression: The Complete Reference». Springer.
• Патент США № 4,558,302 «High speed data compression and decompression apparatus and method».