Изменения

'''Алгори́тм Ле́мпеля — Зи́ва — Ве́лча''' ('''Lempel-Ziv-Welch''', '''Непосредственным предшественником LZW''') — это универсальный является [[Алгоритмы LZ77 и LZ78|алгоритм сжатия данных без потерьLZ78]], созданный опубликованный Абрахамом Лемпелем(''Abraham Lempel''), и Якобом Зивом (''Jacob Ziv'') и в 1978 г. Этот алгоритм воспринимался как математическая абстракция до 1984 г., когда Терри Велчем Уэлч (''Terry A. Welch''). Он был опубликован Велчем в 1984 годуопубликовал свою работу с модифицированным алгоритмом, получившим в качестве улучшенной реализации [[Алгоритм LZ78|дальнейшем название LZW (''Lempel{{---}}Ziv{{---}}Welch''). == Применение == Опубликование алгоритма LZ78]]LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода.  Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, опубликованного Лемпелем и Зивом при полном отсутствии потерь или искажений в 1978 годуисходных файлах.Алгоритм разработан такВ настоящее время используется в файлах формата TIFF, PDF, чтобы его можно было быстро реализоватьGIF, но он не обязательно оптималенPostScript и других, поскольку он не проводит никакого анализа входных а также отчасти во многих популярных программах сжатия данных(ZIP, ARJ, LHA).

Данный алгоритм при сжатии Процесс сжатия выглядит следующим образом: последовательно считываются символы входного потока и происходит проверка, существует ли в созданной таблице строк такая строка. Если такая строка существует, считывается следующий символ, а если строка не существует, в поток заносится код для предыдущей найденной строки, строка заносится в таблицу, а поиск начинается снова.  Например, если сжимают байтовые данные (текст), то строк в таблице окажется <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. ''' Считать очередной символ <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</tex>. {| class="wikitable" border = 1, style="float:right; text-align: right; margin-left: auto; margin-right: auto;"|- bgcolor=#EEEEEE! Символ !! Битовый код !! Код |-| a || 000 || 0|-| b || 001 || 1|-| c || 010 || 2|-| d || 011 || 3|-| e || 100 || 4|} Больше в таблице не будет других кодов, обладающих этим свойством.<br>По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. <tex>8</tex>-битные группы дают <tex>256</tex> возможных комбинации бит фиксированной длины (обычно 12, поэтому, когда в словаре появится <tex>256</tex>-е слово, алгоритм должен перейти к <tex>9</tex>-битные)битным группам. Таблица инициализируется всеми 1При появлении <tex>512</tex>-ого слова произойдет переход к <tex>10</tex>-символьными строками битным группам, что дает возможность запоминать уже <tex>1024</tex> слова и т.д. В нашем примере алгоритму заранее известно о том, что будет использоваться всего <tex>5</tex> различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть <tex>3</tex> (в случае <tex>8-битных символов — это 256 записей</tex> различных комбинаций). По мере кодирования === Кодирование === Пусть мы сжимаем последовательность <tex>abacabadabacabae</tex>. * '''Шаг 1: '''Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке <tex>a</tex> и проверим, есть ли строка <tex>a</tex> в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, алгоритм просматривает текст то строка <tex>a</tex> есть в таблице. * '''Шаг 2: '''Далее мы читаем следующий символ <tex>b</tex> из входного потока и проверяем, есть ли строка <tex>ab</tex> в таблице. Такой строки в таблице пока нет.Добавляем в таблицу <tex>\langle5\rangle</tex> <tex>ab</tex>. В поток: <tex>\langle0\rangle</tex>;* '''Шаг 3: '''<tex>ba</tex> — нет. В таблицу: <tex>\langle6\rangle</tex> <tex>ba</tex>. В поток: <tex>\langle1\rangle</tex>;* '''Шаг 4: '''<tex>ac</tex> — нет. В таблицу: <tex>\langle7\rangle</tex> <tex>ac</tex>. В поток: <tex>\langle0\rangle</tex>;* '''Шаг 5: '''<tex>ca</tex> — нет. В таблицу: <tex>\langle8\rangle</tex> <tex>ca</tex>. В поток: <tex>\langle2\rangle</tex>;* '''Шаг 6: '''<tex>ab</tex> — есть в таблице; <tex>aba</tex> — нет. В таблицу: <tex>\langle9\rangle</tex> <tex>aba</tex>. В поток: <tex>\langle5\rangle</tex>;* '''Шаг 7: '''<tex>ad</tex> — нет. В таблицу: <tex>\langle10\rangle</tex> <tex>ad</tex>. В поток: <tex>\langle0\rangle</tex>;* '''Шаг 8: '''<tex>da</tex> — нет. В таблицу: <tex>\langle11\rangle</tex> <tex>da</tex>. В поток: <tex>\langle3\rangle</tex>;* '''Шаг 9: '''<tex>aba</tex> — есть в таблице; <tex>abac</tex> — нет. В таблицу: <tex>\langle12\rangle</tex> <tex>abac</tex>. В поток: <tex>\langle9\rangle</tex>;* '''Шаг 10: '''<tex>ca</tex> — есть в таблице; <tex>cab</tex> — нет. В таблицу: <tex>\langle13\rangle</tex> <tex>cab</tex>. В поток: <tex>\langle8\rangle</tex>;* '''Шаг 11: '''<tex>ba</tex> — есть в таблице; <tex>bae</tex> — нет. В таблицу: <tex>\langle14\rangle</tex> <tex>bae</tex>. В поток: <tex>\langle6\rangle</tex>;* '''Шаг 12: '''И, наконец последняя строка <tex>e</tex>, за символомней идет конец сообщения, и сохраняет каждую новуюпоэтому мы просто выводим в поток <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;" | ab| style="text-align: center;" | a| 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 || 0000| style="border-right: none;" | 10:| style="border-left: none;" | 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;" | 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| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | abac| style="text-align: center;" | a| style="text-align: center;" | c| 9 || 1001| style="border-right: none;" | 12:| style="border-left: none;" | abac|-| style="text-align: center;" | ca| style="text-align: center;" | c| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | cab| style="text-align: center;" | a| style="text-align: center;" | b| 8 || 1000| style="border-right: none;" | 13:| style="border-left: none;" | cab|-| style="text-align: center;" | ba| 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| style="text-align: center;" | -| 4 || 0100| style="border-right: none;" | -| style="border-left: none;" | -|-|} Итак, мы получаем закодированное сообщение <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> бит, что на <tex>8</tex> бит короче исходного. === Декодирование === Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в виде пары код/символфайл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.  Теперь представим, что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего нам нужно знать начальный словарь, где код ссылается а последующие записи словаря мы можем реконструировать уже на соответствующий первый символходу, поскольку они являются просто конкатенацией предыдущих записей. После Кроме того, в процессе кодировании и декодировании коды в словарь добавляются во время обработки одного и того как новая же символа, т.е. это происходит “синхронно”.   {| class="wikitable" border = 1, style="text-align: center; margin-left: auto; margin-right: auto;"|- bgcolor = #EEEEEE! colspan="2" | Данные! scope="col" width="6em" rowspan="2" | На выходе! colspan="4" | Новая запись|- bgcolor = #EEEEEE! Биты !! Код! scope="col" width="6em" colspan="2" | Полная! scope="col" width="6em" colspan="2" | Частичная|- | 000 || 0| style="text-align: center;" | a| style="border-right: none;" | -| style="border-left: none;" | -| style="border-right: none;" | 5:| style="border-left: none;" | a?|-| 001 || 1| style="text-align: center;" | b| style="border-right: none;" | 5:| style="border-left: none;" | ab| style="border-right: none;" | 6:| style="border-left: none;" | b?|-| 000 || 0| style="text-align: center;" | a| style="border-right: none;" | 6:| style="border-left: none;" | ba| style="border-right: none;" | 7:| style="border-left: none;" | a?|-| 010 || 2| style="text-align: center;" | c| style="border-right: none;" | 7:| style="border-left: none;" | ac| style="border-символьная строка сохранена в таблицеright: none;" | 8:| style="border-left: none;" | c?|-| 0101 || 5| style="text-align: center;" | ab| style="border-right: none;" | 8:| style="border-left: none;" | ca| style="border-right: none;" | 9:| style="border-left: none;" | ab?|-| 0000 || 0| style="text-align: center;" | a| style="border-right: none;" | 9:| style="border-left: none;" | aba| style="border-right: none;" | 10:| style="border-left: none;" | a?|-| 0011 || 3| style="text-align: center;" | d| style="border-right: none;" | 10:| style="border-left: none;" | ad| style="border-right: none;" | 11:| style="border-left: none;" | d?|-| 1001 || 9| style="text-align: center;" | aba| style="border-right: none;" | 11:| style="border-left: none;" | da| style="border-right: none;" | 12:| style="border-left: none;" | aba?|-| 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;" | -|-| 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> бит, что на <tex> 7 \cdot 3 - 12 = 9</tex> бит короче кодирования стандартным методом LZW.Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это <tex>\langle0\rangle</tex>, которому соответствует символ <tex>a</tex>. Затем читает код этой строки<tex>\langle5\rangle</tex>, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть <tex>a</tex>. Поэтому он добавит в свою таблицу строку <tex>aa</tex> с кодом <tex>\langle5\rangle</tex>, а следующий в выходной поток поместит <tex>aa</tex>. И так может быть раскодирована вся цепочка кодов. Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым символам, но и к последовательностям, у которых очередной добавляемый символ используется равен первому символу цепочки. === Преимущества алгоритма LZW === * Алгоритм является однопроходным. * Для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в качестве начала следующей строкисостоянии восстановить таблицу строк, пользуясь только потоком кодов. === Недостатки алгоритма 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 Википедия {{---}} Алгоритм Лемпеля {{---}} Зива {{---}} Велча] * [http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch Wikipedia {{---}} Lempel {{---}} Ziv {{---}} Welch] * [http://compression.ru/download/articles/rev_univ/semenyuk_2001_econom_encoding.pdf Семенюк В.В. {{---}} Экономное кодирование дискретной информации] * [http://algolist.manual.ru/compress/standard/lzw.php Метод LZW {{---}} сжатия данных {{---}} алгоритмы и методы] * [http://www.compression-pointers.ru/category_42.html Алгоритмы сжатия и компрессии] * [http://www.algoritmy.info/picture5.html Алгоритм LZW {{---}} Понятие алгоритма]