Сжатие LZW

Сжатие LZW — это алгоритм сжатия данных без потерь, основанный на построении динамического словаря (таблицы) строк, встречающихся во входном потоке. Алгоритм был разработан в 1984 году Абрахамом Лемпелем, Яаковом Зивом и Терри Уэлчем как усовершенствование алгоритма LZ78. LZW широко применялся в ранних форматах сжатия изображений (GIF, TIFF), в архиваторах (Compress) и в модемных протоколах (V.42bis). Отличительной особенностью LZW является однопроходное кодирование без необходимости предварительного анализа данных и отсутствие априорной информации о вероятностях символов.

История

Алгоритм LZW был опубликован Терри Уэлчем в 1984 году в статье «A Technique for High-Performance Data Compression» (IEEE Computer, vol. 17, no. 6). Уэлч работал в компании Sperry Research Center и ставил задачу создания эффективного и быстрого метода сжатия для дисковых контроллеров и модемов. Основой послужил алгоритм LZ78 (1978), предложенный Абрахамом Лемпелем и Яаковом Зивом. В LZ78 словарь строился из пар «номер предыдущей строки + новый символ», что требовало хранения явной структуры. Уэлч модифицировал этот подход: вместо пар он предложил хранить в словаре целые строки, а выходной поток кодировать номерами этих строк. Это упростило реализацию и повысило скорость сжатия.

В 1985 году алгоритм LZW был запатентован компанией Unisys (патент США 4,558,302). Патентные ограничения на LZW стали причиной длительных судебных разбирательств в 1990-х годах, особенно в связи с распространением формата GIF. В 2003 году срок действия патента истёк, и алгоритм перешёл в общественное достояние. В 1990-х годах LZW был стандартизирован в ряде протоколов и форматов, включая GIF (1987), TIFF (1988) и V.42bis (1990).

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

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

Кодирование

Алгоритм кодирования LZW можно описать следующим образом:

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

• В выходной поток записывается код (индекс) строки w.
• Строка w + k добавляется в словарь под следующим доступным индексом.
• w присваивается значение k (начинается новая строка).

1. Шаги 3–5 повторяются до конца входного потока.
2. После обработки последнего символа в выходной поток записывается код строки w.

Таким образом, кодер выводит коды только тех строк, которые уже есть в словаре, а новые строки добавляются после вывода кода их префикса.

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

Декодирование LZW является симметричным процессом, но требует особого внимания к случаю, когда код, поступающий на вход, ещё не присутствует в словаре (так называемая «ситуация KWK» — когда кодируется строка, состоящая из префикса и самого себя). Алгоритм декодирования:

1. Инициализация словаря теми же одиночными символами (0–255).
2. Чтение первого кода c из входного потока. Вывод строки, соответствующей c. Запоминание предыдущей строки prev как строки, соответствующей c.
3. Чтение следующего кода c.
4. Если код c присутствует в словаре:

• Вывод строки, соответствующей c.
• Строка prev + первый_символ(строка_для_c) добавляется в словарь.
• prev присваивается значение строки, соответствующей c.

1. Если код c отсутствует в словаре (ситуация KWK):

• Строка prev + первый_символ(prev) добавляется в словарь.
• Вывод этой новой строки.
• prev присваивается значение этой новой строки.

1. Шаги 3–5 повторяются до конца входного потока.

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

Степень сжатия

Степень сжатия LZW сильно зависит от характера данных. Алгоритм эффективен на данных с повторяющимися последовательностями (текст, монохромные изображения, повторяющиеся шаблоны). Типичная степень сжатия для текста на естественном языке составляет от 1,5 до 3 раз, для изображений с большими однородными областями — до 5–10 раз. На случайных или уже сжатых данных (например, JPEG, ZIP) LZW может увеличивать объём (коэффициент сжатия менее 1).

Размер словаря

Размер словаря в классической реализации LZW ограничен. Обычно используется 12-битный код, что даёт 4096 записей (индексы 0–4095). Первые 256 записей зарезервированы под одиночные символы. После заполнения словаря (4096 записей) дальнейшее добавление новых строк прекращается, и алгоритм продолжает работать только с существующими записями. В некоторых реализациях (например, в GIF) предусмотрена очистка словаря при его заполнении с помощью специального кода (clear code, обычно 256). В более поздних версиях (LZW-C) применяется адаптивное управление размером словаря.

Скорость

LZW является быстрым алгоритмом как при кодировании, так и при декодировании. Операции поиска в словаре реализуются через хеш-таблицы или деревья, что обеспечивает линейную сложность O(n) по времени. Декодирование обычно быстрее кодирования, так как не требует поиска — словарь строится последовательно.

Применение

Формат GIF

Наиболее известное применение LZW — формат GIF (Graphics Interchange Format), разработанный компанией CompuServe в 1987 году. GIF использует LZW для сжатия палитровых изображений (до 256 цветов). Патентные споры вокруг LZW привели к тому, что формат PNG (Portable Network Graphics) был создан как свободная альтернатива GIF, использующая алгоритм Deflate (LZ77 + Huffman).

Формат TIFF

TIFF (Tagged Image File Format) поддерживает LZW как один из методов сжатия (наряду с PackBits, CCITT Group 3/4, JPEG). LZW в TIFF используется для сжатия полутоновых и цветных изображений без потерь.

Архиватор Compress

В операционных системах Unix (начиная с 1980-х годов) утилита compress использовала LZW для сжатия файлов. Файлы сжимались с расширением .Z. Впоследствии compress был вытеснен более эффективными алгоритмами (gzip, bzip2, xz).

Протокол V.42bis

Международный стандарт V.42bis (1990) для модемов использует LZW для сжатия данных на физическом уровне. В этом протоколе LZW позволяет достичь коэффициента сжатия до 4:1 для текстовых данных, что увеличивает пропускную способность модемного соединения.

Другие применения

LZW применялся в ранних архиваторах (PKZIP, ARJ — в качестве опции), в форматах PostScript Level 2, в некоторых протоколах передачи данных (например, в протоколе PPP). В современных системах LZW используется редко, уступая место более эффективным алгоритмам (Deflate, LZMA, Brotli).

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

Основной недостаток LZW — патентные ограничения, действовавшие до 2003 года. Это привело к фрагментации экосистемы и появлению альтернативных форматов. Кроме того, LZW уступает более современным алгоритмам по степени сжатия (особенно на больших объёмах данных) и по скорости работы на современных процессорах. Алгоритм неэффективен на коротких сообщениях (менее 100 байт) из-за накладных расходов на построение словаря. Также LZW чувствителен к порядку следования данных: при изменении порядка повторяющихся последовательностей степень сжатия может значительно снизиться.

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

• Алгоритм LZW лежит в основе формата GIF, который до сих пор широко используется в интернете для анимированных изображений.
• Патентные споры вокруг LZW в 1990-х годах привели к созданию формата PNG и популяризации свободного программного обеспечения (например, библиотеки libpng).
• В 1993 году компания Unisys пыталась взимать лицензионные отчисления с разработчиков программ, использующих GIF, что вызвало массовое недовольство в сообществе.
• Алгоритм LZW является одним из немногих словарных методов сжатия, который был реализован в аппаратуре (например, в контроллерах жёстких дисков и модемах).

Источники

1. Welch T. A. A Technique for High-Performance Data Compression // IEEE Computer. — 1984. — Vol. 17, No. 6. — P. 8–19.
2. Ziv J., Lempel A. Compression of Individual Sequences via Variable-Rate Coding // IEEE Transactions on Information Theory. — 1978. — Vol. 24, No. 5. — P. 530–536.
3. Nelson M. The Data Compression Book. — 2nd ed. — M&T Books, 1996. — 560 p.
4. Salomon D. Data Compression: The Complete Reference. — 4th ed. — Springer, 2007. — 1092 p.
5. International Telecommunication Union. Recommendation V.42bis: Data Compression Procedures for Data Circuit Terminating Equipment (DCE) Using Error Correction Procedures. — ITU-T, 1990.
6. CompuServe Incorporated. Graphics Interchange Format (GIF) Specification. — 1987.