Изменения
→Пример
Рассмотрим пример сжатия и декодирования сообщения.
Сначала создадим начальный словарь единичных символов. В стандартной кодировке ASCII имеется 256 различных символов, поэтому, для того, чтобы все они были корректно закодированы (если нам неизвестно, какие символы будут присутствовать в исходном файле, а какие - нет), начальный размер кода будет равен 8 битам. Если нам заранее известно, что в исходном файле будет меньшее количество различных символов, то вполне разумно уменьшить количество бит. Чтобы инициализировать таблицу, мы установим соответствие кода 0 соответствующему символу с битовым кодом <tex>00000000</tex>, тогда 1соответствует символу с кодом <tex>00000001</tex>, и т.д., до кода 255. На самом деле мы указали, что каждый код от 0 до 255 является корневым.
{| class="wikitable" border = 1, style="float:right; text-align: right; margin-left: auto; margin-right: auto;"
Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.
*''' ''' Итак, кодировщик заносит первую «а» <tex>a</tex> в строку, ищет и находит "а" <tex>a</tex> в словаре. Добавляет в строку следующую "а"<tex>a</tex>, находит, что "аа" <tex>aa</tex> нет в словаре. Тогда он добавляет запись <5>: "аа" <tex>aa</tex> в словарь и выводит метку <0> ("а"<tex>a</tex>) в выходной поток. *''' '''Далее строка инициализируется второй «а»<tex>a</tex>, то есть принимает вид "<tex>a?" </tex> вводится третья «а»<tex>a</tex>, строка вновь равна "аа"<tex>aa</tex>, которая теперь имеется в словаре. *''' '''Если появляется четвертая «а»<tex>a</tex>, то строка "<tex>aa?" </tex> равна "ааа"<tex>aaa</tex>, которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка <5> ("<tex>aa"</tex>). *''' '''После этого строка инициализируется третьей «а»<tex>a</tex>, и т.д. и т.п. Дальнейший процесс вполне ясен.
В результате на выходе получаем последовательность 0, 5, 6 …, которая короче прямого кодирования стандартным методом LZW.
Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это <0>, которому соответствует символ "<tex>a"</tex>. Затем читает код <5>, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть "<tex>a"</tex>. Поэтому он добавит в свою таблицу строку "<tex>aa" </tex> с кодом <5>, а в выходной поток поместит "<tex>aa"</tex>. И так может быть раскодирована вся цепочка кодов.
Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым символам, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.
