Изменения

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

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

Первой вещью, которую мы делаем при LZW-сжатии, является инициализация нашей цепочки Сначала создадим начальный словарь единичных символов. Чтобы сделать это, нам необходимо выбрать код размера (количество бит) и знать, сколько возможных значений могут принимать наши символы. Давайте положим код размера равным 3 битам, что означает возможность запоминания 8 элементов в нашей таблице цепочек. Давайте также Также предположим, что мы имеем 5 возможных различных символа. ( Это соответствует, например, картинке с 5 возможными цветами для каждого пиксела ). Чтобы инициализировать таблицу, мы установим соответствие кода 0 символу a, кода 1 символу b, и т.д., до кода 4 и символа e. На самом деле мы указали, что каждый код от 0 до 4 является корневым. Больше в таблице не будет других кодов, обладающих этим свойством.<br>По мере роста словаря, размер групп должен расти, с тем , чтобы учесть новые элементы. 3-битные группы дают 8 возможных комбинации бит, поэтому, когда в словаре появится 9-е слово, алгоритм должен перейти к 4-битным группам. При появлении 17-ого слова произойдет переход к 5-битным группам, что дает возможность запоминать уже 32 слова и т.д.

Для повышения степени сжатия изображений данным методом часто используется одна «хитрость» реализации этого алгоритма. Некоторые изображенияфайлы, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых значенийсимволов, например 12, 12, 12 aaaaaa … или 30, 30, 30 … и т. п. Их непосредственное сжатие будет генерировать выходной код 120, 120, 32 5 и т.д. Спрашивается, можно ли в этом частном случае повысить степень сжатия? Оказывается, да, если мы оговорим следующие действия по кодированию и декодированию. <br>Кодирование таких цепочек будем осуществлять следующим образом:<br>Первый цвет 12 записывает с его же кодом из таблицы 12Кодер заносит первую «а» в строку, ищет и находит "а" в словаре. Следующий цвет тоже 12, тогда добавляем Добавляет в таблицу строку 12следующую "а", находит, 12 с кодом 32 что "аа" нет в словаре. Тогда он добавляет запись <5>: "аа" в словарь и выводит метку <0> ("а") в выходной поток сразу заносим этот код. Далее строка инициализируется второй «а», то есть 32. Смотрим входной поток дальшепринимает вид "a?" вводится третья «а», строка вновь равна "аа", которая теперь имеется в словаре. Если на вход опять поступает цвет 12появляется четвертая «а», он есть в таблице, смотрим следующий – 12, последовательность 12то строка "aa?" равна "ааа", 12 тоже есть которой нет в таблицесловаре. Словарь пополняется этой строкой, смотрим дальше – 12а на выход идет метка <5> ("aa"). После этого строка инициализируется третьей «а», последовательности 12, 12, 12 присваиваем код 33 и заносим его в выходной потокт.д. и т.п. Дальнейший процесс вполне ясен. <br> В результате на выходе получаем последовательность 120, 325, 33 6 …, которая гораздо короче прямого кодирования стандартным методом LZW. 

Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это 12<0>, которому соответствует цвет 12символ "a". Затем читает код 32<5>, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть 12"a". Поэтому он добавит в свою таблицу строку 12, 12 "aa" с кодом 32<5>, а в выходной поток поместит 12, 12"aa". И так может быть раскодирована вся цепочка кодов.

Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым цветам точексимволам, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.