Изменения

{{ОпределениеНепосредственным предшественником 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 - это способ сжатия данных, который извлекает преимущества при повторяющихся цепочках данныхпроизвело большое впечатление на всех специалистов по сжатию информации. Поскольку растровые данные обычно содержат довольно много таких повторений, LZW является хорошим методом для их сжатия За этим последовало большое количество программ и раскрытияприложений с различными вариантами этого метода.

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

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

Алгоритму Для декодирования на входе требуется вход подается только закодированный текст, поскольку он алгоритм 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'''.* Конец.

Рассмотрим пример сжатия и декодирования изображениясообщения.  Первой вещьюСначала создадим начальный словарь единичных символов. В стандартной кодировке ASCII имеется <tex>256</tex> различных символов, которую мы делаем при LZW-сжатиипоэтому, является инициализация нашей цепочки символов. Чтобы сделать этодля того, чтобы все они были корректно закодированы (если нам необходимо выбрать код размера (количество битнеизвестно, какие символы будут присутствовать в исходном файле, а какие — нет) и знать, сколько возможных значений могут принимать наши символыначальный размер кода будет равен <tex>8</tex> битам. Давайте положим код размера равным 12 битамЕсли нам заранее известно, что означает возможность запоминания 4096 элементов в нашей таблице цепочек. Давайте также предположимисходном файле будет меньшее количество различных символов, что мы имеем 32 возможных различных символато вполне разумно уменьшить количество бит. ( Это соответствует, например, картинке с 32 возможными цветами для каждого пиксела ) Чтобы инициализировать таблицу, мы установим соответствие кода <tex>0 </tex> соответствующему символу 0с битовым кодом <tex>00000000</tex>, кода тогда <tex>1 </tex>соответствует символу 1с кодом <tex>00000001</tex>, и т.д., до кода 31 и символа 31. На самом деле мы указали, что каждый код от 0 до 31 является корневым. Больше в таблице не будет других кодов, обладающих этим свойством<tex>255</tex>. Изначальный словарь: {| class="wikitable" border = 1, style="float:right; text-align: right; margin-left: auto; margin-right: auto;"

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

| 0 a || 000 || 000

| 1 b || 001 || 011

| 2 c || 010 || 102

| 3 d || 011 || 113

| ... e || ...100 |-| 31 || 111114

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

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

! scope="col" width="7em" rowspan="2" colspan="2" | Расширенный словарь! rowspan="2" | КомментарииСловарь

| style="text-align: center;" | 15ab| style="text-align: center;" | 25a| 15 style="text-align: center;" | b| 0 || 000| style="border-right: none;" | 5:| style="border-left: none;" | ab|-| style="text-align: center;" | ba| style="text-align: center;" | b| style="text-align: center;" | a| 1 || 001| style="border-right: none;" | 6:| style="border-left: none;" | ba|-| style="text-align: center;" | ac| style="text-align: center;" | a| style="text-align: center;" | c| 0 || 000| style="border-right: none;" | 7:| style="border-left: none;" | ac |-| style="text-align: center;" | ca| style="text-align: center;" | c| style="text-align: center;" | a| 2 || 010| style="border-right: none;" | 8:| style="border-left: none;" | ca|-| style="text-align: center;" | ab| style="text-align: center;" | a| style="text-align: center;" | b| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | aba| style="text-align: center;" | b| style="text-align: center;" | a| 5 || 0101| style="border-right: none;" | 9:| style="border-left: none;" | aba|-| style="text-align: center;" | ad| style="text-align: center;" | a| style="text-align: center;" | d| 0 || 11110000| style="border-right: none;" | 3210:| style="border-left: none;" | 15, 25 ad|-| style="text-align: center;" | da|style="text-align: center;" |d| style="text-align: center;" | a| 3 || 0011| style="border-right: none;" | 11:| style="border-left: none;" | da

| style="text-align: center;" | 25ab| style="text-align: center;" | 25a| 25 style="text-align: center;" |b| 10111- || -| style="border-right: none;" | 33:-| style="border-left: none;" | 25, 25 ||-

| style="text-align: center;" | 25aba| style="text-align: center;" | 17b| 25 style="text-align: center;" |a| 10111- || -| style="border-right: none;" | 34:-| style="border-left: none;" | 25, 17 ||-

| style="text-align: center;" | 17abac| style="text-align: center;" | 25a| 17 style="text-align: center;" | c|9 | 10001| 1001| style="border-right: none;" | 3512:| style="border-left: none;" | 17, 25 ||abac

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

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

| style="text-align: center;" | 25cab| style="text-align: center;" | 25| 33 || 100001a| style="bordertext-rightalign: nonecenter;" | 36:b| 8 || 1000| style="border-leftright: none;" | 25, 25, 25 ||13:| style="textborder-alignleft: leftnone;" | cab

| style="text-align: center;" | 25ba| style="text-align: center;" | b| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | bae| style="text-align: center;" | a| style="text-align: center;" | e| 6 || 0110| style="border-right: none;" | 14:| style="border-left: none;" | bae|-| style="text-align: center;" | e| style="text-align: center;" | e

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

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

| 01 000 || 10| style="text-align: center;" | Aa| style="border-right: none;" || style="border-left: none;" || style="border-right: none;" | 4:| style="border-left: none;" | A? |||-| 10 || 2| style="text-align: center;" | B| style="border-right: none;" | 4:| style="border-left: none;" | AB

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

| 11 001 || 31| style="text-align: center;" | Cb

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

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

| 100 000 || 40| style="text-align: center;" | ABa

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

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

| 110 010 || 62| style="text-align: center;" | CAc

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

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

| 101 0101 || 5| style="text-align: center;" | BCab

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

| style="border-left: none;" | BCab?| style="text-align: left;" |

| 111 0000 || 70| style="text-align: center;" | ABCa

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

| style="border-left: none;" | ABCa?| style="text-align: left;" |

| 1010 0011 || 103| style="text-align: center;" | ABCAd

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

| style="border-left: none;" | ABCAd? || Решение проблемы см. ниже

| 101 1001 || 59| style="text-align: center;" | BCaba

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

| style="border-left: none;" | BCaba? |-|1000 || 8| style="text-align: center;" | ca| style="border-right: none;" | 12:| style="border-left: none;" | abac| style="border-right: none;" | 13:| style="border-left: none;" | ca?|-| 0110 || 6| style="text-align: center;" | ba| style="border-right: none;" | 13:| style="border-left: none;" | cab| style="border-right: none;" | 14:| style="border-left: none;" | ba?|-| 0100 || 4| style="text-align: center;" | e| style="border-right: none;" | 14:| style="border-left: none;" | bae| style="border-right: none;" | -| style="border-left: none;" | -|-|} === Примечание === Для повышения степени сжатия изображений данным методом часто используется одна “хитрость” реализации этого алгоритма. Некоторые файлы, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых символов, например <tex>aaaaaaaaaaaaa... </tex> или <tex>303030</tex> … и т. п. Их непосредственное сжатие будет генерировать выходной код <tex>005000600007...</tex>. Спрашивается, можно ли в этом частном случае повысить степень сжатия? Оказывается, это возможно, если оговорить некоторые действия: Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.*''' ''' Пусть словарь состоит из слов : <tex>a, b, c, d, e</tex>. Будем кодировать строку <tex> aaaaaaaaaa </tex>*''' ''' Итак, кодировщик заносит первую <tex>a</tex> в строку, ищет и находит <tex>a</tex> в словаре под номером <tex>\langle0\rangle</tex>. Добавляет в строку следующую <tex>a</tex>, находит, что <tex>aa</tex> нет в словаре. Тогда он добавляет запись <tex>\langle5\rangle</tex>: <tex>aa</tex> в словарь и выводит метку <tex>\langle0\rangle</tex> (<tex>a</tex>) в выходной поток. *''' '''Далее строка инициализируется второй <tex>a</tex>, то есть принимает вид <tex>a?</tex> вводится третья <tex>a</tex>, строка вновь равна <tex>aa</tex>, которая теперь имеется в словаре. *''' '''Если появляется четвертая <tex>a</tex>, то строка <tex>aa?</tex> равна <tex>aaa</tex>, которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка <tex>\langle5\rangle</tex> (<tex>aa</tex>). *''' '''После этого строка инициализируется третьей <tex>a</tex>, и т.д. и т.п. Дальнейший процесс вполне ясен.  [[Файл: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;" | -

| 000000 || 0| style="text-align: center;" | #aa| style="bordertext-rightalign: nonecenter;" | a| style="bordertext-leftalign: nonecenter;" |a| - || -| style="border-right: none;" |-| style="border-left: none;" | ||- 

Единственная небольшая трудность может возникнутьВ результате на выходе получаем последовательность <tex>0567</tex>. При кодировании использовались только трехбитные группы. Длина закодированного сообщения составила <tex> 4 \cdot 3 = 12 </tex> бит, если новое слово словаря пересылается немедленночто на <tex> 7 \cdot 3 - 12 = 9</tex> бит короче кодирования стандартным методом LZW. В приведённом выше примере декодированияМожно показать, когда декодер встречает что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это <tex>\langle0\rangle</tex>, которому соответствует символ<tex>a</tex>. Затем читает код <tex>\langle5\rangle</tex>, '''ABC?'''но этого кода в его таблице нет. Но мы уже знаем, он знаетчто такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что слово 10 начинается считанной последовательности, то есть <tex>a</tex>. Поэтому он добавит в свою таблицу строку <tex>aa</tex> с ABCкодом <tex>\langle5\rangle</tex>, а в выходной поток поместит <tex>aa</tex>. И так может быть раскодирована вся цепочка кодов. Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым символам, но чем оно заканчивается? Проиллюстрируем проблему следующим примероми к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки. Мы декодируем сообщение '''ABABA''': Данные: На выходе: Новая запись: Полная: Частичная:=== Преимущества алгоритма LZW ===  * Алгоритм является однопроходным. * Для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов. . 011101 = 29 AB 46: (word) 47: AB? 101111 = 47 AB? <--- что нам с этим делать?= Недостатки алгоритма LZW ===

На первый взгляд, для декодера это неразрешимая ситуация. Мы знаем наперёд, что словом 47 должно быть '''ABA''', но как декодер узнает об этом?Заметим, что слово 47 состоит из слова 29 плюс символ идущий следующим. Таким образом, слово 47 заканчивается на «символ идущий следующим». Но, поскольку это слово посылается немедленно, то оно должно начинаться с «символа идущего следующим», и поэтому оно заканчивается тем же символом что и начинается, в данном случае — '''A'''. Этот трюк позволяет декодеру определить, что слово 47 это '''ABA'''* Алгоритм не проводит анализ входных данных.

== Патенты ==На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах* [http://ru. К настоящему времени, сроки всех патентов истеклиwikipedia.org/wiki/%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 Википедия {{---}} Алгоритм Лемпеля {{---}} Зива {{---}} Велча]

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

К настоящему сроку патенты истекли, поэтому спор утих* [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 Семенюк В.В. - Экономное кодирование дискретной информацииАлгоритмы сжатия]]