Изменения

{{ОпределениеНепосредственным предшественником LZW является [[Алгоритмы LZ77 и LZ78|definition='''Алгори́тм Ле́мпеля — Зи́ва — Ве́лча''' ('''Lempel-Ziv-Welch'''алгоритм LZ78]], '''LZW''') — это универсальный алгоритм сжатия данных без потерь}}Он был создан опубликованный Абрахамом Лемпелем(''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). 

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

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

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

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

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

| a || 000 || 000

| b || 001 || 001

| c || 010|| 2

| d || 011|| 3

| e || 100|| 4

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

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

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

| style="border-right: none;" | -

| 4 5 || 1000101

| 0 || 0000000

| 3 || 0110011

| 8 9 || 10001001

| 7 8 || 01111000

| 5 6 || 01010110

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

Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов. <br>

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

| style="border-right: none;" |-| style="border-left: none;" |-

| 101 0101 || 5

| 000 0000 || 0

| 011 0011 || 3

| style="border-left: none;" | aaba?

| style="text-align: center;" | 25ca| style="border-right: none;" | 3612:| style="border-left: none;" | 25, 25, 25abac| style="border-right: none;" |13:| style="border-left: none;" |ca?

| style="text-align: center;" | 25ba| style="border-right: none;" | 3613:| style="border-left: none;" | 25, 25, 25cab| style="border-right: none;" |14:| style="border-left: none;" |ba?

| style="text-align: center;" | 25e| style="border-right: none;" | 3614:| style="border-left: none;" | 25, 25, 25bae| style="border-right: none;" |-| style="border-left: none;" |-

Для повышения степени сжатия изображений данным методом часто используется одна «хитрость» “хитрость” реализации этого алгоритма. Некоторые изображенияфайлы, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых значенийсимволов, например 12, 12, 12 … <tex>aaaaaaaaaaaaa... </tex> или 30, 30, 30 <tex>303030</tex> … и т. п. Их непосредственное сжатие будет генерировать выходной код 12, 12, 32 и т<tex>005000600007...д</tex>. Спрашивается, можно ли в этом частном случае повысить степень сжатия?  Оказывается, даэто возможно, если мы оговорим следующие оговорить некоторые действия по кодированию : Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и декодированиюсимвола, с которого начинается следующая строка в потоке.*''' ''' Пусть словарь состоит из слов : <tex>a, b, c, d, e</tex>. Будем кодировать строку <brtex>Кодирование таких цепочек будем осуществлять следующим образом:aaaaaaaaaa <br/tex>Первый цвет 12 записывает с его же кодом из таблицы 12. Следующий цвет тоже 12*''' ''' Итак, тогда добавляем кодировщик заносит первую <tex>a</tex> в таблицу строку 12, 12 с кодом 32 ищет и находит <tex>a</tex> в словаре под номером <tex>\langle0\rangle</tex>. Добавляет в выходной поток сразу заносим этот кодстроку следующую <tex>a</tex>, находит, то есть 32что <tex>aa</tex> нет в словаре. Смотрим входной Тогда он добавляет запись <tex>\langle5\rangle</tex>: <tex>aa</tex> в словарь и выводит метку <tex>\langle0\rangle</tex> (<tex>a</tex>) в выходной поток дальше. Если на вход опять поступает цвет 12*''' '''Далее строка инициализируется второй <tex>a</tex>, он то есть в таблицепринимает вид <tex>a?</tex> вводится третья <tex>a</tex>, смотрим следующий – 12строка вновь равна <tex>aa</tex>, последовательность 12, 12 тоже есть которая теперь имеется в таблицесловаре. *''' '''Если появляется четвертая <tex>a</tex>, смотрим дальше – 12то строка <tex>aa?</tex> равна <tex>aaa</tex>, последовательности 12которой нет в словаре. Словарь пополняется этой строкой, 12а на выход идет метка <tex>\langle5\rangle</tex> (<tex>aa</tex>). *''' '''После этого строка инициализируется третьей <tex>a</tex>, 12 присваиваем код 33 и заносим его т.д. и т.п. Дальнейший процесс вполне ясен.  [[Файл:LZW-img.jpg|center|Работа алгоритма LZW]] {| class="wikitable" border = 1, style="text-align: center; margin-left: auto; margin-right: auto;"|- bgcolor=#EEEEEE! Слово !! Номер в выходной поток. словаре|-| a || <tex>\langle0\rangle</tex>|-| b || <tex>\langle1\rangle</tex>|-| c || <tex>\langle2\rangle</tex>|-| d || <tex>\langle3\rangle</tex>|-| e || <tex>\langle4\rangle</tex>|} {| class="wikitable" border =1, style="text-align: center; margin-left: auto; margin-right: auto;"|- bgcolor =#EEEEEE! scope="col" width="6em" rowspan="2" | Текущая строка! scope="col" width="6em" rowspan="2" | Текущий символ! scope="col" width="4em" rowspan="2" | Следующий символ! colspan="2" | Вывод! scope="col" width="7em" rowspan="2" colspan="2" | Словарь|- bgcolor =#EEEEEE! Код || Биты|-| style="text-align: center;" | aa| style="text-align: center;" | a| style="text-align: center;" | a| 0 || 000| style="border-right: none;" | 5:| style="border-left: none;" | aa|-| style="text-align: center;" | aa| style="text-align: center;" | a| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | aaa| style="text-align: center;" | a| style="text-align: center;" | a| 5 || 101| style="border-right: none;" | 6:| style="border-left: none;" | aaa |-| style="text-align: center;" | a| style="text-align: center;" | a| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | - |-| style="text-align: center;" | aa| style="text-align: center;" | a| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | aaa| style="text-align: center;" | a| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | aaaa| style="text-align: center;" | a| style="text-align: center;" | a| 6 || 110| style="border-right: none;" | 7:| style="border-left: none;" | aaaa|-| style="text-align: center;" | a| style="text-align: center;" | a| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | aa| style="text-align: center;" | a| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | - |-| style="text-align: center;" | aaa| style="text-align: center;" | a| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | aaaa| style="text-align: center;" | a| style="text-align: center;" | a| 7 || 111| style="border-right: none;" | 8:| style="border-left: none;" | aaaaa|} В результате на выходе получаем последовательность <tex>0567</tex>. При кодировании использовались только трехбитные группы. Длина закодированного сообщения составила <tex> 4 \cdot 3 = 12</tex> бит, 32, 33 …, которая гораздо что на <tex> 7 \cdot 3 - 12 = 9</tex> бит короче прямого кодирования стандартным методом LZW.<br><br>Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это 12<tex>\langle0\rangle</tex>, которому соответствует цвет 12символ <tex>a</tex>. Затем читает код 32<tex>\langle5\rangle</tex>, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть 12<tex>a</tex>. Поэтому он добавит в свою таблицу строку 12, 12 <tex>aa</tex> с кодом 32<tex>\langle5\rangle</tex>, а в выходной поток поместит 12, 12<tex>aa</tex>. И так может быть раскодирована вся цепочка кодов.<br><br>Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым цветам точексимволам, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки. === Преимущества алгоритма LZW === * Алгоритм является однопроходным. * Для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.

== Достоинства и недостатки = Недостатки алгоритма LZW ===

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

На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах* [http://en. <br>Среди обладателей патентов была компания Unisyswikipedia. Поэтому использование формата GIF, в котором он используется, было раскритиковано изorg/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch Wikipedia {{-за лицензионных отчислений. Был предложен альтернативный формат PNG (PNG not GIF).--}} Lempel {{---}} Ziv {{---}} Welch]

Когда в 2003 году закончился срок действия патента на метод сжатия данных LZW, он остался востребованным только для формата GIF* [http://compression.ru/download/articles/rev_univ/semenyuk_2001_econom_encoding.pdf Семенюк В.В. {{---}} Экономное кодирование дискретной информации]

* [http://ruwww.wikipediacompression-pointers.orgru/wiki/LZW Wikipedia | LZW (рус)category_42.html Алгоритмы сжатия и компрессии]

* [http://enwww.wikipediaalgoritmy.orginfo/wiki/LZW Wikipedia | picture5.html Алгоритм LZW (англ){{---}} Понятие алгоритма]

* [http[Категория: Дискретная математика и алгоритмы]][[Категория://compression.ru/download/articles/rev_univ/semenyuk_2001_econom_encoding.pdf Семенюк В.В. - Экономное кодирование дискретной информацииАлгоритмы сжатия]]