Изменения

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

Процесс сжатия выглядит следующим образом. Последовательно : последовательно считываются символы входного потока и происходит проверка, существует ли в созданной таблице строк такая строка. Если такая строка существует, считывается следующий символ, а если строка не существует, в поток заносится код для предыдущей найденной строки, строка заносится в таблицу, а поиск начинается снова. <br>

Например, если сжимают байтовые данные (текст), то строк в таблице окажется <tex>256 </tex> (от <tex>"0" </tex> до <tex>"255"</tex>). Если используется <tex>10</tex>-битный код, то под коды для строк остаются значения в диапазоне от <tex>256 </tex> до <tex>1023</tex>. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом. <br>

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

Таким образом, каждая строка будет храниться в единственном экземпляре и иметь свой уникальный номер. Следовательно, при дешифровании при получении декодировании во время получения нового кода генерируется новая строка, а при получении уже известного, строка ивлекается извлекается из словаря.

# Инициализация словаря всеми возможными односимвольными фразами* Начало. Инициализация входной фразы * ''' Шаг 1. ''' Все возможные символы заносятся в словарь. Во входную фразу <tex>X первым символом </tex> заносится первый символ сообщения.# * ''' Шаг 2. ''' Считать очередной символ <tex>Y </tex> из кодируемого сообщения.# * ''' Шаг 3. ''' Если КОНЕЦ_СООБЩЕНИЯ<tex>Y</tex> {{---}} это символ конца сообщения, то выдать код для <tex>X</tex>, иначе: ** Если фраза <tex>XY </tex> уже есть имеется в словаре, то присвоить входной фразе значение <tex>XY </tex> и перейти к ''' Шагу 2''', иначе ** Иначе выдать код для входной фразы <tex>X</tex>, добавить <tex>XY </tex> в словарь, и присвоить входной фразе значение <tex>Y и перейти </tex>. Перейти к ''' Шагу 2. '''* Конец.

# Инициализация словаря всеми возможными односимвольными фразами* Начало. Инициализация входной фразы * ''' Шаг 1. ''' Все возможные символы заносятся в словарь. Во входную фразу <tex>X первым кодом </tex> заносится первый код декодируемого сообщения.# * ''' Шаг 2. ''' Считать очередной код <tex>Y </tex> из декодируемого сообщения.# * ''' Шаг 3. ''' Если КОНЕЦ_СООБЩЕНИЯ<tex>Y</tex> {{---}} это конец сообщения, то выдать символ для кода , соответствующий коду <tex>X</tex>, иначе: ** Если фразы под кодом <tex>XY </tex> нет в словаре, вывести фразу с кодом , соответствующую коду <tex>X</tex>, а фразу с кодом <tex>XY </tex> занести в словарь. ** Иначе присвоить входной фразе код <tex>XY </tex> и перейти к шагу ''' Шагу 2'''.* Конец.

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

! Символ !! Битовый код!! Код

| a || 000 || 000

| b || 001 || 001

| c || 010|| 2

| d || 011|| 3

| e || 100|| 4

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

Пусть мы сжимаем последовательность "<tex>abacabadabacabae"</tex>.

* '''Шаг 1: '''Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке “a” <tex>a</tex> и проверим, есть ли строка “a” <tex>a</tex> в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “a” <tex>a</tex> есть в таблице. * '''Шаг 2: '''Далее мы читаем следующий символ "<tex>b" </tex> из входного потока и проверяем, есть ли строка “ab” <tex>ab</tex> в таблице. Такой строки в таблице пока нет.Добавляем в таблицу <5tex>\langle5\rangle</tex> <tex>ab</tex> “ab”. В поток: <0tex>\langle0\rangle</tex>;* '''Шаг 3: '''“ba” <tex>ba</tex> — нет. В таблицу: <6tex>\langle6\rangle</tex> <tex>ba</tex> “ba”. В поток: <1tex>\langle1\rangle</tex>;* '''Шаг 4: '''“ac” <tex>ac</tex> — нет. В таблицу: <7tex>\langle7\rangle</tex> <tex>ac</tex> “ac”. В поток: <0tex>\langle0\rangle</tex>;* '''Шаг 5: '''“ca” <tex>ca</tex> — нет. В таблицу: <8tex>\langle8\rangle</tex> <tex>ca</tex> “ca”. В поток: <2tex>\langle2\rangle</tex>;* '''Шаг 6: '''“ab” <tex>ab</tex> — есть в таблице; “aba” <tex>aba</tex> — нет. В таблицу: <9tex>\langle9\rangle</tex> <tex>aba</tex> “aba”. В поток: <5tex>\langle5\rangle</tex>;* '''Шаг 7: '''“ad” <tex>ad</tex> — нет. В таблицу: <10tex>\langle10\rangle</tex> <tex>ad</tex> “ad”. В поток: <0tex>\langle0\rangle</tex>;* '''Шаг 8: '''“da” <tex>da</tex> — нет. В таблицу: <11tex>\langle11\rangle</tex> <tex>da</tex> “da”. В поток: <3tex>\langle3\rangle</tex>;* '''Шаг 9: '''“aba” <tex>aba</tex> — есть в таблице; “abac” <tex>abac</tex> — нет. В таблицу: <12tex>\langle12\rangle</tex> <tex>abac</tex> “abac”. В поток: <9tex>\langle9\rangle</tex>;* '''Шаг 10: '''“ca” <tex>ca</tex> — есть в таблице; “cab” <tex>cab</tex> — нет. В таблицу: <13tex>\langle13\rangle</tex> <tex>cab</tex> “cab”. В поток: <8tex>\langle8\rangle</tex>;* '''Шаг 11: '''“ba” <tex>ba</tex> — есть в таблице; “bae” <tex>bae</tex> — нет. В таблицу: <14tex>\langle14\rangle</tex> <tex>bae</tex> “bae”. В поток: <6tex>\langle6\rangle</tex>;* '''Шаг 12: '''И, наконец последняя строка “e”<tex>e</tex>, за ней идет конец сообщения, поэтому мы просто выводим в поток <4tex>\langle4\rangle</tex>.

| 5 || 1010101

| 0 || 0000000

| 3 || 0110011

Итак, мы получаем закодированное сообщение "<tex>0 1 0 2 5 0 3 9 8 6 4"</tex> и его битовый эквивалент <tex>000 001 000 010 0101 0000 0011 1001 1000 0110 0100</tex>. Каждый символ исходного сообщения был закодирован группой из трех бит, сообщение содержало <tex>16 </tex> символов, следовательно длина сообщения составляла <tex>3 * \cdot 16 = 48 </tex> бит.

Закодированное же сообщение так же сначала кодировалось трехбитными группами, а про при появлении в словаре восьмого слова - — четырехбитными, итого длина сообщения составила 7 * <tex>4 \cdot 3 + 4 * 7 \cdot 4 = 37 40</tex> бит, что на 11 <tex>8</tex> бит короче исходного.

Теперь представим ,что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей. Кроме того, в процессе кодировании и декодировании коды в словарь добавляются во время обработки одного и того же символа, т.е. это происходит “синхронно”.

| 101 0101 || 5

| 000 0000 || 0

| 011 0011 || 3

Для повышения степени сжатия изображений данным методом часто используется одна «хитрость» “хитрость” реализации этого алгоритма. Некоторые файлы, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых символов, например aaaaaa … <tex>aaaaaaaaaaaaa... </tex> или 30, 30, 30 <tex>303030</tex> … и т. п. Их непосредственное сжатие будет генерировать выходной код 0, 0, 5 и т<tex>005000600007...д</tex>. Спрашивается, можно ли в этом частном случае повысить степень сжатия?

*''' ''' ИтакВ результате на выходе получаем последовательность <tex>0567</tex>. При кодировании использовались только трехбитные группы. Длина закодированного сообщения составила <tex> 4 \cdot 3 = 12 </tex> бит, кодировщик заносит первую «а» в строкучто на <tex> 7 \cdot 3 - 12 = 9</tex> бит короче кодирования стандартным методом LZW.Можно показать, ищет и находит "а" в словаречто такая последовательность будет корректно восстановлена. Добавляет в строку следующую "а"Декодировщик сначала читает первый код – это <tex>\langle0\rangle</tex>, находит, что "аа" нет в словарекоторому соответствует символ <tex>a</tex>. Тогда он добавляет запись Затем читает код <5tex>: "аа" в словарь и выводит метку \langle5\rangle<0/tex> ("а") , но этого кода в выходной потокего таблице нет. *''' '''Далее строка инициализируется второй «а»Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть принимает вид "<tex>a?" вводится третья «а», строка вновь равна "аа", которая теперь имеется </tex>. Поэтому он добавит в словаре. *''' '''Если появляется четвертая «а», то строка "свою таблицу строку <tex>aa?" равна "ааа"</tex> с кодом <tex>\langle5\rangle</tex>, которой нет а в словаре. Словарь пополняется этой строкой, а на выход идет метка выходной поток поместит <5tex> ("aa"). *''' '''После этого строка инициализируется третьей «а», и т.д. и т.п</tex>. Дальнейший процесс вполне ясенИ так может быть раскодирована вся цепочка кодов.

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

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

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

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

==Источникиинформации==

* [http://ru.wikipedia.org/wiki/LZW Алгоритм Лемпеля%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%BC%D0%BF%D0%B5%D0%BB%D1%8F_%E2%80%94_%D0%97%D0%B8%D0%B2%D0%B0_%E2%80%94_%D0%92%D0%B5%D0%BB%D1%87%D0%B0 Википедия {{---}}ЗиваАлгоритм Лемпеля {{---}}Велча Зива {{---}} ВикипедияВелча]

* [http://en.wikipedia.org/wiki/LZW Lempel%E2%80%93Ziv%E2%80%93Welch Wikipedia {{---}}ZivLempel {{---}}Welch Ziv {{---}} WikipediaWelch]

* [http://algolist.manual.ru/compress/standard/lzw.php Метод LZW{{---}}сжатия данных {{---}} алгоритмы и методы]