LZW (LZW)

LZW (LZW) - универсальный словарный алгоритм обратимого сжатия данных, который заменяет повторяющиеся последовательности символов или элементов кодами из формируемого словаря. При распаковке данные восстанавливаются без изменений.

Что означает термин

Название LZW образовано от фамилий Авраама Лемпеля, Якоба Зива и Терри Велча. Алгоритм относится к методам сжатия без потерь и предназначен для уменьшения объёма данных, содержащих повторяющиеся последовательности.

Как устроено

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

Эффективность алгоритма зависит от структуры данных: для достаточно больших наборов с повторяющимися или избыточными последовательностями сжатие обычно результативнее. При небольшом количестве повторов коэффициент сжатия может быть невысоким. Для корректного восстановления кодировщик и декодировщик должны одинаково трактовать структуру и ограничения словаря.

Где применяется

LZW применялся для сжатия растровых изображений в формате GIF. Он также используется как один из вариантов сжатия в TIFF и PDF, а ранее лежал в основе Unix-утилиты compress.

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

История возникновения

LZW создан Авраамом Лемпелем, Якобом Зивом и Терри Велчем. Публикация алгоритма Терри Велчем состоялась в 1984 году; он был разработан как развитие LZ78.