Открыть сервис
Главная → Блог → Алгоритм LZW

Алгоритм LZW

Алгоритм LZW (Lempel–Ziv–Welch) — это универсальный алгоритм сжатия данных без потерь, основанный на построении динамического словаря (таблицы) последовательностей символов (строк) из входного потока. Алгоритм был разработан в 1984 году Терри Уэлчем (Terry Welch) как усовершенствование алгоритмов LZ77 и LZ78, предложенных Абрахамом Лемпелем и Якобом Зивом. LZW широко применялся в ранних форматах сжатия изображений (GIF, TIFF) и в утилитах архивации (например, compress в Unix).

История

Алгоритмы сжатия семейства LZ (Lempel-Ziv) появились в конце 1970-х годов. В 1977 году Лемпель и Зив опубликовали алгоритм LZ77, использующий скользящее окно для поиска повторяющихся фрагментов. В 1978 году они предложили LZ78, где вместо окна строилась словарная таблица фраз. Однако практическая реализация LZ78 была неэффективной из-за неограниченного роста словаря и сложности кодирования.

В 1984 году Терри Уэлч, работавший в компании Sperry Research Center, опубликовал модификацию LZ78, названную LZW. Основные улучшения Уэлча:

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

LZW быстро стал популярным благодаря простоте реализации и хорошей степени сжатия для текстовых и графических данных. В 1987 году он был выбран для формата GIF (Graphics Interchange Format), разработанного компанией CompuServe. В 1990-х годах алгоритм использовался в утилите compress (Unix), а также в форматах TIFF и PostScript Level 2. С появлением более эффективных алгоритмов (DEFLATE, LZMA) и патентных ограничений LZW утратил доминирующее положение, но остаётся важным историческим примером.

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

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

Сжатие

Процесс сжатия состоит из следующих шагов:

  1. Инициализация словаря. В словарь заносятся все возможные односимвольные строки (коды 0–255 для байтовых данных). Каждому символу соответствует его числовое значение.
  2. Чтение входного потока. Алгоритм последовательно считывает символы из входного потока, накапливая текущую строку w.
  3. Поиск в словаре. Для каждого нового символа c проверяется, есть ли в словаре строка w + c.
  • Если есть — строка w расширяется до w + c, и алгоритм переходит к следующему символу.
  • Если нет — в выходной поток записывается код строки w (её индекс в словаре), а строка w + c добавляется в словарь с новым кодом. Затем w устанавливается равной c.
  1. Завершение. После обработки всего потока в выходной поток записывается код последней строки w.

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

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

Декомпрессия выполняется в обратном порядке, но с той же логикой построения словаря:

  1. Инициализация словаря теми же односимвольными строками.
  2. Чтение кодов из сжатого потока. Для каждого кода:
  • Если код есть в словаре — в выходной поток записывается соответствующая строка.
  • Если код отсутствует (особый случай, возникающий при последовательности вида cScSc, где S — уже известная строка) — строка восстанавливается как предыдущая_строка + первый_символ_предыдущей_строки.
  1. Обновление словаря. После записи каждой строки в словарь добавляется новая фраза, состоящая из предыдущей строки и первого символа текущей строки.

Декомпрессор всегда «догоняет» компрессор, так как новые коды добавляются в словарь только после их первого использования.

Пример работы

Рассмотрим сжатие строки «ABABABA» (символы A, B имеют коды 65, 66 соответственно, но для простоты используем условные коды 1 и 2).

Инициализация словаря:

  • Код 1: «A»
  • Код 2: «B»

Шаги сжатия:

  1. Читаем «A» → w = «A»
  2. Читаем «B» → w + c = «AB» нет в словаре → выводим код 1 (для «A»), добавляем «AB» с кодом 3, w = «B»
  3. Читаем «A» → w + c = «BA» нет → выводим код 2 (для «B»), добавляем «BA» с кодом 4, w = «A»
  4. Читаем «B» → w + c = «AB» есть (код 3) → w = «AB»
  5. Читаем «A» → w + c = «ABA» нет → выводим код 3 (для «AB»), добавляем «ABA» с кодом 5, w = «A»
  6. Читаем «B» → w + c = «AB» есть (код 3) → w = «AB»
  7. Читаем «A» → w + c = «ABA» есть (код 5) → w = «ABA»
  8. Конец потока → выводим код 5 (для «ABA»)

Выходной поток: 1, 2, 3, 5 (4 кода вместо 7 символов). Степень сжатия — 4/7 ≈ 57%.

Характеристики и ограничения

Достоинства

  • Простота реализации. Алгоритм требует минимум вычислительных ресурсов и памяти.
  • Однопроходность. Сжатие выполняется за один проход по данным, без предварительного анализа.
  • Адаптивность. Словарь строится под конкретные данные, что обеспечивает хорошее сжатие для повторяющихся структур.
  • Симметричность. Декомпрессия не требует дополнительной информации (кроме инициализированного словаря).

Недостатки

  • Ограниченный размер словаря. В классической реализации словарь фиксирован (обычно 4096 или 65536 записей). При переполнении словарь либо сбрасывается, либо перестаёт обновляться, что снижает эффективность.
  • Плохое сжатие коротких или случайных данных. Для неповторяющихся последовательностей размер сжатых данных может превысить исходный.
  • Патентные ограничения. Алгоритм LZW был запатентован в США (патент US4558302A, истёк в 2003 году), что ограничивало его свободное использование в программном обеспечении.
  • Чувствительность к ошибкам. Ошибка в одном коде может привести к неверному восстановлению всей последующей последовательности.

Применение

LZW использовался в следующих областях и форматах:

  • Формат GIF (Graphics Interchange Format). Основной алгоритм сжатия для изображений с палитрой до 256 цветов. Позволял эффективно сжимать изображения с большими одноцветными областями.
  • Формат TIFF (Tagged Image File Format). Один из вариантов сжатия для растровых изображений.
  • Утилита compress (Unix). Стандартная программа сжатия в системах Unix, использовавшая LZW.
  • Формат PostScript Level 2. Использовался для сжатия данных в языке описания страниц.
  • Модемные протоколы. В некоторых протоколах сжатия данных (например, V.42bis) применялись модификации LZW.

В настоящее время LZW в значительной степени вытеснен более эффективными алгоритмами, такими как DEFLATE (используется в PNG, ZIP, gzip) и LZMA (7z, XZ). Однако он остаётся важным для обратной совместимости с устаревшими форматами (GIF, TIFF).

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

  • Патент на LZW (US4558302A) принадлежал компании Unisys и был предметом судебных разбирательств в 1990-х годах. В 1999 году Unisys потребовала лицензионных отчислений от разработчиков программ, использующих GIF, что вызвало протесты в интернет-сообществе и привело к созданию формата PNG (Portable Network Graphics), не использующего запатентованные алгоритмы.
  • Алгоритм LZW является основой для многих учебных примеров по сжатию данных из-за своей наглядности.
  • В некоторых реализациях (например, в GIF) используется переменная длина кода (от 9 до 12 бит), что позволяет адаптироваться к размеру словаря.

Источники

  • Welch, T. A. (1984). «A Technique for High-Performance Data Compression». IEEE Computer, 17(6), 8–19.
  • Nelson, M., & Gailly, J.-L. (1995). The Data Compression Book. M&T Books.
  • Salomon, D. (2007). Data Compression: The Complete Reference. Springer.
  • RFC 1951 (DEFLATE Compressed Data Format Specification) — содержит описание алгоритмов, заменивших LZW.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы