Непосредственным предшественником LZW является алгоритм LZ78, опубликованный Абрахамом Лемпелем (Abraham Lempel) и Якобом Зивом (Jacob Ziv) в 1978 г. Этот алгоритм воспринимался как математическая абстракция до 1984 г., когда Терри Уэлч (Terry A. Welch) опубликовал свою работу с модифицированным алгоритмом, получившим в дальнейшем название LZW (Lempel—Ziv—Welch).

6.1. Применение
Опубликование алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода.
Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. В настоящее время используется в файлах формата TIFF, PDF, GIF, PostScript и других, а также отчасти во многих популярных программах сжатия данных (ZIP, ARJ, LHA).

6.2. Описание
Процесс сжатия выглядит следующим образом: последовательно считываются символы входного потока и происходит проверка, существует ли в созданной таблице строк такая строка. Если такая строка существует, считывается следующий символ, а если строка не существует, в поток заносится код для предыдущей найденной строки, строка заносится в таблицу, а поиск начинается снова.
Например, если сжимают байтовые данные (текст), то строк в таблице окажется 256 (от "0" до "255"). Если используется 10-битный код, то под коды для строк остаются значения в диапазоне от 256 до 1023. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом.
Для декодирования на вход подается только закодированный текст, поскольку алгоритм LZW может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту. Алгоритм генерирует однозначно декодируемый код за счет того, что каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового. Таким образом, каждая строка будет храниться в единственном экземпляре и иметь свой уникальный номер. Следовательно, при декодировании во время получения нового кода генерируется новая строка, а при получении уже известного, строка извлекается из словаря.

6.3. Алгоритм
Кодирование:

• Начало.
• Шаг 1. Все возможные символы заносятся в словарь. Во входную фразу X заносится первый символ сообщения.
• Шаг 2. Считать очередной символ Y из сообщения.
• Шаг 3. Если Y — это символ конца сообщения, то выдать код для X, иначе:
• Если фраза XY уже имеется в словаре, то присвоить входной фразе значение XY и перейти к Шагу 2 ,
• Иначе выдать код для входной фразы X, добавить XY в словарь и присвоить входной фразе значение Y. Перейти к Шагу 2.
• Конец.

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

• Начало.
• Шаг 1. Все возможные символы заносятся в словарь. Во входную фразу X заносится первый код декодируемого сообщения.
• Шаг 2. Считать очередной код Y из сообщения.
• Шаг 3. Если Y — это конец сообщения, то выдать символ, соответствующий коду X, иначе:
• Если фразы под кодом XY нет в словаре, вывести фразу, соответствующую коду X, а фразу с кодом XY занести в словарь.
• Иначе присвоить входной фразе код XY и перейти к Шагу 2 .
• Конец.

6.4. Пример
Сжатие
Рассмотрим пример сжатия и декодирования сообщения. Сначала создадим начальный словарь единичных символов. В стандартной кодировке ASCII имеется 256 различных символов, поэтому, для того, чтобы все они были корректно закодированы (если нам неизвестно, какие символы будут присутствовать в исходном файле, а какие — нет), начальный размер кода будет равен 8 битам. Если нам заранее известно, что в исходном файле будет меньшее количество различных символов, то вполне разумно уменьшить количество бит. Чтобы инициализировать таблицу, мы установим соответствие кода 0 соответствующему символу с битовым кодом 00000000, тогда 1 соответствует символу с кодом 00000001, и т.д., до кода 255.

Больше в таблице не будет других кодов, обладающих этим свойством.
По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 8-битные группы дают 256 возможных комбинации бит, поэтому, когда в словаре появится 256-е слово, алгоритм должен перейти к 9-битным группам. При появлении 512-ого слова произойдет переход к 10-битным группам, что дает возможность запоминать уже 1024 слова и т.д.

В нашем примере алгоритму заранее известно о том, что будет использоваться всего 5 различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть 3 (8различных комбинаций).

Кодирование
Пусть мы сжимаем последовательность abacabadabacabae.

• Шаг 1: Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке a и проверим, есть ли строка a в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка a есть в таблице.
• Шаг 2: Далее мы читаем следующий символ b из входного потока и проверяем, есть ли строка ab в таблице. Такой строки в таблице пока нет.

Добавляем в таблицу ⟨5⟩ ab. В поток: ⟨0⟩;

• Шаг 3: ba — нет. В таблицу: ⟨6⟩ ba. В поток: ⟨1⟩;
• Шаг 4: ac — нет. В таблицу: ⟨7⟩ ac. В поток: ⟨0⟩;
• Шаг 5: ca — нет. В таблицу: ⟨8⟩ ca. В поток: ⟨2⟩;
• Шаг 6: ab — есть в таблице; aba — нет. В таблицу: ⟨9⟩ aba. В поток: ⟨5⟩;
• Шаг 7: ad — нет. В таблицу: ⟨10⟩ ad. В поток: ⟨0⟩;
• Шаг 8: da — нет. В таблицу: ⟨11⟩ da. В поток: ⟨3⟩;
• Шаг 9: aba — есть в таблице; abac — нет. В таблицу: ⟨12⟩ abac. В поток: ⟨9⟩;
• Шаг 10: ca — есть в таблице; cab — нет. В таблицу: ⟨13⟩ cab. В поток: ⟨8⟩;
• Шаг 11: ba — есть в таблице; bae — нет. В таблицу: ⟨14⟩ bae. В поток: ⟨6⟩;
• Шаг 12: И, наконец последняя строка e, за ней идет конец сообщения, поэтому мы просто выводим в поток ⟨4⟩.

Итак, мы получаем закодированное сообщение 01025039864 и его битовый эквивалент . Каждый символ исходного сообщения был закодирован группой из трех бит, сообщение содержало 16символов, следовательно длина сообщения составляла 3⋅16=48 бит.
Закодированное же сообщение так же сначала кодировалось трехбитными группами, а при появлении в словаре восьмого слова — четырехбитными, итого длина сообщения составила 4⋅3+7⋅4=40 бит, что на 8 бит короче исходного.

Преимущества алгоритма LZW

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

Недостатки алгоритма LZW

• Алгоритм не проводит анализ входных данных.