Изменения

| 0 a || 00

| 1 b || 01

| 2 c || 10

| 3 d || 11|-| ... || ...|-| 31 || 11111

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

Пусть мы сжимаем последовательность 15, 25, 25, 17, 25, 25, 25"abacabadabacabae".

Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке “15” “a” и проверим, есть ли строка “15” “a” в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “15” “a” есть в таблице. <br>Далее мы читаем следующий символ 25 "b" из входного потока и проверяем, есть ли строка “15, 25” “ab” в таблице. Такой строки в таблице пока нет. <br>Добавляем в таблицу <324> “ab”. В поток: <0>; <br>“ba” — нет. В таблицу: <5> “ba”. В поток: <1>; <br>“ac” — нет. В таблицу: <6> “ac”. В поток: <0>; <br>“ca” — нет. В таблицу: <7> “ca”. В поток: <2>; <br>“ab” — есть в таблице; “aba” — нет. В таблицу: <8> “15, 25”“aba”. В поток: <4>;<br>“ad” — нет. В таблицу: <9> “ad”. В поток: <150>; <br>“25, 25” “da” — нет. В таблицу: <3310> “25, 25”“da”. В поток: <253>; <br>“25, 17” “aba” — есть в таблице; “abac” — нет. В таблицу: <3411> “25, 17”“abac”. В поток: <258>; <br>“17, 25” “ad” — нет. В таблицу: <359> “17, 25”“ad”. В поток: <170>; <br>“25, 25” “ca” — есть в таблице; “25, 25, 25” “cab” — нет. В таблицу: <3612> “25, 25, 25”“cab”. В поток: <337>;<br>И, наконец последняя строка “25”“aba”, за ней идет конец сообщения, поэтому мы просто выводим в поток <2511>.

| style="text-align: center;" | 15a| style="text-align: center;" | 25b| 15 0 || 1111000| style="border-right: none;" | 324:| style="border-left: none;" | 15, 25ab

| style="text-align: center;" | 25b| style="text-align: center;" | 25a| 25 1 || 11001001| style="border-right: none;" | 335:| style="border-left: none;" | 25, 25ba

| style="text-align: center;" | 25a| style="text-align: center;" | 17c| 25 0 || 11001000| style="border-right: none;" | 346:| style="border-left: none;" | 25, 17 ac

| style="text-align: center;" | 17c| style="text-align: center;" | 25a| 17 2 || 10001010| style="border-right: none;" | 357:| style="border-left: none;" | 17, 25ca

| style="text-align: center;" | 25a| style="text-align: center;" | 25b

| style="text-align: center;" | 25b| style="text-align: center;" | 25a| 33 4 || 100001100| style="border-right: none;" | 368:| style="border-left: none;" | 25, 25, 25aba|-| style="text-align: center;" | a| style="text-align: center;" | d| 0 || 000| style="border-right: none;" | 9:| style="border-left: none;" | ad|-| style="text-align: center;" | d| style="text-align: center;" | a| 3 || 011| style="border-right: none;" | 10:| style="border-left: none;" | da|-| style="text-align: center;" | a| style="text-align: center;" | b| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | b| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | a| style="text-align: center;" | c| 8 || 1000| style="border-right: none;" | 11:| style="border-left: none;" | abac|-| style="text-align: center;" | c| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | a| style="text-align: center;" | b| 7 || 0111| style="border-right: none;" | 12:| style="border-left: none;" | cab|-| style="text-align: center;" | b| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | a| style="text-align: center;" | e| 5 || 0101| style="border-right: none;" | 13:| style="border-left: none;" | abae

| style="text-align: center;" | 25e

| 25 4 || 110010100| style="border-right: none;" | -

Итак, мы получаем закодированное сообщение "15, 25, 25, 17, 33, 250 1 0 2 4 0 3 8 7 5 4", что на 4 бита 11 бит короче.

+ Для выполнения обратного процесса ("распаковки") нет необходимости сохранять таблицу кодов в документе.<br>+ Данный тип компрессии не вносит искажений в исходный графический файл, и подходит для сжатия растровых данных любого типа - монохромных, черно - белых, или полноцветных. <br>