Алгоритм LZW — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Кодирование)
м (rollbackEdits.php mass rollback)
 
(не показано 158 промежуточных версий 10 участников)
Строка 1: Строка 1:
{{Определение
+
Непосредственным предшественником LZW является [[Алгоритмы LZ77 и LZ78|алгоритм LZ78]], опубликованный Абрахамом Лемпелем (''Abraham Lempel'') и Якобом Зивом (''Jacob Ziv'') в 1978 г. Этот алгоритм воспринимался как математическая абстракция до 1984 г., когда Терри Уэлч (''Terry A. Welch'') опубликовал свою работу с модифицированным алгоритмом, получившим в дальнейшем название LZW (''Lempel{{---}}Ziv{{---}}Welch'').
|definition=
 
'''Алгори́тм Ле́мпеля — Зи́ва — Ве́лча''' ('''Lempel-Ziv-Welch''', '''LZW''') — это универсальный алгоритм сжатия данных без потерь
 
}}
 
Он был создан Абрахамом Лемпелем(''Abraham Lempel''), Якобом Зивом (''Jacob Ziv'') и Терри Велчем (''Terry Welch''). Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации [[Алгоритмы LZ77 и LZ78|алгоритма LZ78]], опубликованного Лемпелем и Зивом в 1978 году.
 
Алгоритм не проводит анализ входных данных поэтому не оптимален, но быстро реализуем.
 
  
 
== Применение ==
 
== Применение ==
  
В свое время LZW был лучшим алгоритмом сжатия. Он стал первым широко используемым на компьютерах методом сжатия данных.
+
Опубликование алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода.  
  
Алгоритм был реализован в программе compress, которая стала более или менее стандартной утилитой Unix-систем приблизительно в 1986 году. Многие другие утилиты-архиваторы также используют этот метод или близкие к нему.
+
Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. В настоящее время используется в файлах формата TIFF, PDF, GIF, PostScript и других, а также отчасти во многих популярных программах сжатия данных (ZIP, ARJ, LHA).
  
В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может (опционально) использоваться в формате TIFF.
+
== Описание ==
  
PDF содержит этот алгоритм.
+
Процесс сжатия выглядит следующим образом: последовательно считываются символы входного потока и происходит проверка, существует ли в созданной таблице строк такая строка. Если такая строка существует, считывается следующий символ, а если строка не существует, в поток заносится код для предыдущей найденной строки, строка заносится в таблицу, а поиск начинается снова.  
  
== Описание ==
+
Например, если сжимают байтовые данные (текст), то строк в таблице окажется  <tex>256</tex> (от <tex>"0"</tex> до <tex>"255"</tex>). Если используется <tex>10</tex>-битный код, то под коды для строк остаются значения в диапазоне от <tex>256</tex> до <tex>1023</tex>. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом.
  
Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.
+
Для декодирования на вход подается только закодированный текст, поскольку алгоритм LZW может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту.  
 
+
Алгоритм генерирует однозначно декодируемый код за счет того, что каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового.  
Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту.
+
Таким образом, каждая строка будет храниться в единственном экземпляре и иметь свой уникальный номер. Следовательно, при декодировании во время получения нового кода генерируется новая строка, а при получении уже известного, строка извлекается из словаря.
  
 
== Алгоритм ==
 
== Алгоритм ==
  
# Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы ω первым символом сообщения.
+
=== Кодирование ===
# Считать очередной символ K из кодируемого сообщения.
+
* Начало.
# Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для ω, иначе
+
* ''' Шаг  1. ''' Все возможные символы заносятся в словарь. Во входную фразу <tex>X</tex> заносится первый символ сообщения.
# Если фраза ωK уже есть в словаре, присвоить входной фразе значение ωK и перейти к Шагу 2, иначе выдать код ω, добавить ωK в словарь, присвоить входной фразе значение K и перейти к Шагу 2.
+
* ''' Шаг 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 '''.
 +
* Конец.
  
 
== Пример ==
 
== Пример ==
  
Данный пример показывает алгоритм LZW в действии, показывая состояние выходных данных и словаря на каждой стадии, как при кодировании, так и при раскодировании сообщения. С тем чтобы сделать изложение проще, мы ограничимся алфавитом из трех букв.
+
Рассмотрим пример сжатия и декодирования сообщения.  
Сообщение, которое нужно сжать, выглядит следующим образом:
+
Сначала создадим начальный словарь единичных символов. В стандартной кодировке ASCII имеется <tex>256</tex> различных символов, поэтому, для того, чтобы все они были корректно закодированы (если нам неизвестно, какие символы будут присутствовать в исходном файле, а какие — нет), начальный размер кода будет равен <tex>8</tex> битам. Если нам заранее известно, что в исходном файле будет меньшее количество различных символов, то вполне разумно уменьшить количество бит. Чтобы инициализировать таблицу, мы установим соответствие кода <tex>0</tex> соответствующему символу с битовым кодом <tex>00000000</tex>, тогда <tex>1</tex>
ABCABCABCABCABCABC#
+
соответствует символу с кодом <tex>00000001</tex>, и т.д., до кода <tex>255</tex>.
Маркер '''#''' используется для обозначения конца сообщения. Тем самым, в нашем алфавите 4 символа. Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 2 бит на символ. По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 2-битные группы дают 2<sup>2</sup> = 4 возможные комбинации бит, поэтому, когда в словаре появится 5-е слово, алгоритм должен перейти к 3-битным группам. Заметим, что, поскольку используется группа из всех нолей 00, то 5-я группа имеет код '''4'''. Начальный словарь будет содержать:
+
 
+
{| class="wikitable" border = 1, style="float:right; text-align: right; margin-left: auto; margin-right: auto;"
{| class="wikitable" border = 1, style="text-align: right; margin-left: auto; margin-right: auto;"
 
 
|- bgcolor=#EEEEEE
 
|- bgcolor=#EEEEEE
! Символ !! Битовый код !! Номер
+
! Символ !! Битовый код !! Код
 +
|-
 +
| a || 000 || 0
 
|-
 
|-
| # || 00 || 0
+
| b || 001 || 1
 
|-
 
|-
| A || 01 || 1
+
| c || 010 || 2
 
|-
 
|-
| B || 10 || 2
+
| d || 011 || 3
 
|-
 
|-
| C || 11 || 3
+
| e || 100 || 4
 
|}
 
|}
 +
 +
Больше в таблице не будет других кодов, обладающих этим свойством.<br>
 +
По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. <tex>8</tex>-битные группы дают <tex>256</tex> возможных комбинации бит, поэтому, когда в словаре появится <tex>256</tex>-е слово, алгоритм должен перейти к <tex>9</tex>-битным группам. При появлении <tex>512</tex>-ого слова произойдет переход к <tex>10</tex>-битным группам, что дает возможность запоминать уже <tex>1024</tex> слова и т.д.
 +
 +
В нашем примере алгоритму заранее известно о том, что будет использоваться всего <tex>5</tex> различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть <tex>3</tex> (<tex>8</tex> различных комбинаций).
  
 
=== Кодирование ===
 
=== Кодирование ===
Без использования алгоритма LZW, при передаче сообщения как оно есть — 25 символов по 5 бит на каждый — оно займёт 125 бит. Сравним это с тем, что получается при использовании LZW:
+
 
 +
Пусть мы сжимаем последовательность <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;"
 
{| class="wikitable" border =1, style="text-align: center; margin-left: auto; margin-right: auto;"
 
|- bgcolor =#EEEEEE
 
|- bgcolor =#EEEEEE
 +
! scope="col" width="6em" rowspan="2" | Текущая строка
 
! scope="col" width="6em" rowspan="2" | Текущий символ
 
! scope="col" width="6em" rowspan="2" | Текущий символ
 
! scope="col" width="4em" rowspan="2" | Следующий символ
 
! scope="col" width="4em" rowspan="2" | Следующий символ
 
! colspan="2" | Вывод
 
! colspan="2" | Вывод
! scope="col" width="7em" rowspan="2" colspan="2" | Расширенный словарь
+
! scope="col" width="7em" rowspan="2" colspan="2" | Словарь
! rowspan="2" | Комментарии
 
 
|- bgcolor =#EEEEEE
 
|- bgcolor =#EEEEEE
 
!  Код  || Биты
 
!  Код  || Биты
|-
 
| style="text-align: center;" | NULL
 
| style="text-align: center;" | A || ||
 
| style="border-right: none;" |
 
| style="border-left: none;" | ||
 
 
|-
 
|-
| style="text-align: center;" | A
+
| style="text-align: center;" | ab
| style="text-align: center;" | B
+
| style="text-align: center;" | a
| 20 || 10100
+
| style="text-align: center;" | b
 +
| 0 || 000
 
| style="border-right: none;" | 5:
 
| style="border-right: none;" | 5:
| style="border-left: none;" | AB
+
| style="border-left: none;" | ab
| style="text-align: left;" |
 
 
|-
 
|-
| style="text-align: center;" | B
+
| style="text-align: center;" | ba
| style="text-align: center;" | C
+
| style="text-align: center;" | b
| 15 || 01111
+
| style="text-align: center;" | a
 +
| 1 || 001
 
| style="border-right: none;" | 6:
 
| style="border-right: none;" | 6:
| style="border-left: none;" | BC ||
+
| style="border-left: none;" | ba
 
|-
 
|-
| style="text-align: center;" | C
+
| style="text-align: center;" | ac
| style="text-align: center;" | A
+
| style="text-align: center;" | a
| 2 || 00010
+
| style="text-align: center;" | c
 +
| 0 || 000
 
| style="border-right: none;" | 7:
 
| style="border-right: none;" | 7:
| style="border-left: none;" | CA ||
+
| style="border-left: none;" | ac
 
|-
 
|-
| style="text-align: center;" | AB
+
| style="text-align: center;" | ca
| style="text-align: center;" | C
+
| style="text-align: center;" | c
| 5 || 00101
+
| style="text-align: center;" | a
 +
| 2 || 010
 
| style="border-right: none;" | 8:
 
| style="border-right: none;" | 8:
| style="border-left: none;" | ABC ||
+
| style="border-left: none;" | ca
 
|-
 
|-
| style="text-align: center;" | CA
+
| style="text-align: center;" | ab
| style="text-align: center;" | B
+
| style="text-align: center;" | a
| 15 || 01111
+
| 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-right: none;" | 9:
| style="border-left: none;" | CAB ||
+
| style="border-left: none;" | aba
 
|-
 
|-
| style="text-align: center;" | BC
+
| style="text-align: center;" | ad
| style="text-align: center;" | A
+
| style="text-align: center;" | a
| 18 || 10010
+
| style="text-align: center;" | d
 +
| 0 || 0000
 
| style="border-right: none;" | 10:
 
| style="border-right: none;" | 10:
| style="border-left: none;" | BCA
+
| style="border-left: none;" | ad
| style="text-align: left;" |
 
 
|-
 
|-
| style="text-align: center;" | N
+
| style="text-align: center;" | da
| style="text-align: center;" | O
+
| style="text-align: center;" | d
| 14 || 001110
+
| style="text-align: center;" | a
| style="border-right: none;" | 33:
+
| 3 || 0011
| style="border-left: none;" | NO || начинаем использовать 6 битов
+
| style="border-right: none;" | 11:
 +
| style="border-left: none;" | da
 
|-
 
|-
| style="text-align: center;" | O
+
| style="text-align: center;" | ab
| style="text-align: center;" | T
+
| style="text-align: center;" | a
| 15 || 001111
+
| style="text-align: center;" | b
| style="border-right: none;" | 34:
+
| - || -
| style="border-left: none;" | OT ||
+
| style="border-right: none;" | -
 +
| style="border-left: none;" | -
 
|-
 
|-
| style="text-align: center;" | T
+
| style="text-align: center;" | aba
| style="text-align: center;" | T
+
| style="text-align: center;" | b
| 20 || 010100
+
| style="text-align: center;" | a
| style="border-right: none;" | 35:
+
| - || -
| style="border-left: none;" | TT ||
+
| style="border-right: none;" | -
 +
| style="border-left: none;" | -
 
|-
 
|-
| style="text-align: center;" | TO
+
| style="text-align: center;" | abac
| style="text-align: center;" | B
+
| style="text-align: center;" | a
| 27 || 011011
+
| style="text-align: center;" | c
| style="border-right: none;" | 36:
+
| 9 || 1001
| style="border-left: none;" | TOB ||
+
| style="border-right: none;" | 12:
 +
| style="border-left: none;" | abac
 
|-
 
|-
| style="text-align: center;" | BE
+
| style="text-align: center;" | ca
| style="text-align: center;" | O
+
| style="text-align: center;" | c
| 29 || 011101
+
| style="text-align: center;" | a
| style="border-right: none;" | 37:
+
| - || -
| style="border-left: none;" | BEO ||
+
| style="border-right: none;" | -
 +
| style="border-left: none;" | -
 
|-
 
|-
| style="text-align: center;" | OR
+
| style="text-align: center;" | cab
| style="text-align: center;" | T
+
| style="text-align: center;" | a
| 31 || 011111
+
| style="text-align: center;" | b
| style="border-right: none;" | 38:
+
| 8 || 1000
| style="border-left: none;" | ORT ||
+
| style="border-right: none;" | 13:
 +
| style="border-left: none;" | cab
 
|-
 
|-
| style="text-align: center;" | TOB
+
| style="text-align: center;" | ba
| style="text-align: center;" | E
+
| style="text-align: center;" | b
| 36 || 100100
+
| style="text-align: center;" | a
| style="border-right: none;" | 39:
+
| - || -
| style="border-left: none;" | TOBE ||
+
| style="border-right: none;" | -
 +
| style="border-left: none;" | -
 
|-
 
|-
| style="text-align: center;" | EO
+
| style="text-align: center;" | bae
| style="text-align: center;" | R
+
| style="text-align: center;" | a
| 30 || 011110
+
| style="text-align: center;" | e
| style="border-right: none;" | 40:
+
| 6 || 0110
| style="border-left: none;" | EOR ||
+
| style="border-right: none;" | 14:
 +
| style="border-left: none;" | bae
 
|-
 
|-
| style="text-align: center;" | RN
+
| style="text-align: center;" | e
| style="text-align: center;" | O
+
| style="text-align: center;" | e
| 32 || 100000
+
| style="text-align: center;" | -
| style="border-right: none;" | 41:
+
| 4 || 0100
| style="border-left: none;" | RNO ||
+
| style="border-right: none;" | -
|-
+
| style="border-left: none;" | -
| style="text-align: center;" | OT
 
| style="text-align: center;" | #
 
| 34 || 100010
 
| style="border-right: none;" |
 
| style="border-left: none;" |
 
| style="text-align: left;" | # останавливаем алгоритм; выводим текущую последовательность
 
|-
 
| || || 0 || 000000
 
| style="border-right: none;" |
 
| style="border-left: none;" |
 
| style="text-align: center;" | и останавливаем кодирование
 
 
|-
 
|-
 
|}
 
|}
  
Длина закодированного текста = 6  × 5 + 11 × 6 = 96 битов.
+
Итак, мы получаем закодированное сообщение <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> бит.
  
Таким образом, используя LZW мы сократили сообщение на 29 бит из 125 — это почти 22 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.
+
Закодированное же сообщение так же сначала кодировалось трехбитными группами, а при появлении в словаре восьмого слова — четырехбитными, итого длина сообщения составила <tex>4 \cdot 3 + 7 \cdot 4 = 40</tex> бит, что на <tex>8</tex> бит короче исходного.
  
 
=== Декодирование ===
 
=== Декодирование ===
Теперь представим что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей.
+
 
 +
Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.
 +
 
 +
Теперь представим, что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей. Кроме того, в процессе кодировании и декодировании коды в словарь добавляются во время обработки одного и того же символа, т.е. это происходит “синхронно”.  
  
  
Строка 187: Строка 222:
 
! scope="col" width="6em" rowspan="2" | На выходе
 
! scope="col" width="6em" rowspan="2" | На выходе
 
! colspan="4" | Новая запись
 
! colspan="4" | Новая запись
! rowspan="2" | Комментарии
 
 
|- bgcolor = #EEEEEE
 
|- bgcolor = #EEEEEE
 
! Биты !! Код
 
! Биты !! Код
Строка 193: Строка 227:
 
! scope="col" width="6em" colspan="2" | Частичная
 
! scope="col" width="6em" colspan="2" | Частичная
 
|-  
 
|-  
| 10100 || 20
+
| 000 || 0
| style="text-align: center;" | T
+
| style="text-align: center;" | a
| style="border-right: none;" |
+
| style="border-right: none;" | -
| style="border-left: none;" |
+
| style="border-left: none;" | -
| style="border-right: none;" | 27:
+
| style="border-right: none;" | 5:
| style="border-left: none;" | T? ||
+
| style="border-left: none;" | a?
 
|-
 
|-
| 01111 || 15
+
| 001 || 1
| style="text-align: center;" | O
+
| style="text-align: center;" | b
| style="border-right: none;" | 27:
+
| style="border-right: none;" | 5:
| style="border-left: none;" | TO
+
| style="border-left: none;" | ab
| style="border-right: none;" | 28:
+
| style="border-right: none;" | 6:
| style="border-left: none;" | O? ||
+
| style="border-left: none;" | b?
 
|-
 
|-
| 00010 || 2
+
| 000 || 0
| style="text-align: center;" | B
+
| style="text-align: center;" | a
| style="border-right: none;" | 28:
+
| style="border-right: none;" | 6:
| style="border-left: none;" | OB
+
| style="border-left: none;" | ba
| style="border-right: none;" | 29:
+
| style="border-right: none;" | 7:
| style="border-left: none;" | B? ||
+
| style="border-left: none;" | a?
 
|-
 
|-
| 00101 || 5
+
| 010 || 2
| style="text-align: center;" | E
+
| style="text-align: center;" | c
| style="border-right: none;" | 29:
+
| style="border-right: none;" | 7:
| style="border-left: none;" | BE
+
| style="border-left: none;" | ac
| style="border-right: none;" | 30:
+
| style="border-right: none;" | 8:
| style="border-left: none;" | E? ||
+
| style="border-left: none;" | c?
 
|-
 
|-
| 01111 || 15
+
| 0101 || 5
| style="text-align: center;" | O
+
| style="text-align: center;" | ab
| style="border-right: none;" | 30:
+
| style="border-right: none;" | 8:
| style="border-left: none;" | EO
+
| style="border-left: none;" | ca
| style="border-right: none;" | 31:
+
| style="border-right: none;" | 9:
| style="border-left: none;" | O? ||
+
| style="border-left: none;" | ab?
 
|-
 
|-
| 10010 || 18
+
| 0000 || 0
| style="text-align: center;" | R
+
| style="text-align: center;" | a
| style="border-right: none;" | 31:
+
| style="border-right: none;" | 9:
| style="border-left: none;" | OR
+
| style="border-left: none;" | aba
| style="border-right: none;" | 32:
+
| style="border-right: none;" | 10:
| style="border-left: none;" | R?
+
| style="border-left: none;" | a?
| style="text-align: left;" | создали код 31 (последний, содержащий 5 бит)
 
 
|-
 
|-
| 001110 || 14
+
| 0011 || 3
| style="text-align: center;" | N
+
| style="text-align: center;" | d
| style="border-right: none;" | 32:
+
| style="border-right: none;" | 10:
| style="border-left: none;" | RN
+
| style="border-left: none;" | ad
| style="border-right: none;" | 33:
+
| style="border-right: none;" | 11:
| style="border-left: none;" | N?
+
| style="border-left: none;" | d?
| style="text-align: left;" | начинаем  использовать 6 бит
 
 
|-
 
|-
| 001111 || 15
+
| 1001 || 9
| style="text-align: center;" | O
+
| style="text-align: center;" | aba
| style="border-right: none;" | 33:
+
| style="border-right: none;" | 11:
| style="border-left: none;" | NO
+
| style="border-left: none;" | da
| style="border-right: none;" | 34:
+
| style="border-right: none;" | 12:
| style="border-left: none;" | O? ||
+
| style="border-left: none;" | aba?
 
|-
 
|-
| 010100 || 20
+
| 1000 || 8
| style="text-align: center;" | T
+
| style="text-align: center;" | ca
| style="border-right: none;" | 34:
+
| style="border-right: none;" | 12:
| style="border-left: none;" | OT
+
| style="border-left: none;" | abac
| style="border-right: none;" | 35:
+
| style="border-right: none;" | 13:
| style="border-left: none;" | T? ||
+
| style="border-left: none;" | ca?
 
|-
 
|-
| 011011 || 27
+
| 0110 || 6
| style="text-align: center;" | TO
+
| style="text-align: center;" | ba
| style="border-right: none;" | 35:
+
| style="border-right: none;" | 13:
| style="border-left: none;" | TT
+
| style="border-left: none;" | cab
| style="border-right: none;" | 36:
+
| style="border-right: none;" | 14:
| style="border-left: none;" | TO? ||
+
| style="border-left: none;" | ba?
 
|-
 
|-
| 011101 || 29
+
| 0100 || 4
| style="text-align: center;" | BE
+
| style="text-align: center;" | e
| style="border-right: none;" | 36:
+
| style="border-right: none;" | 14:
| style="border-left: none;" | TOB
+
| style="border-left: none;" | bae
| style="border-right: none;" | 37:
+
| style="border-right: none;" | -
| style="border-left: none;" | BE?
+
| style="border-left: none;" | -
| style="text-align: left;" | 36 = TO + 1й символ (B)
 
 
|-
 
|-
| 011111 || 31
+
|}
| style="text-align: center;" | OR
+
 
| style="border-right: none;" | 37:
+
=== Примечание ===
| style="border-left: none;" | BEO
+
 
| style="border-right: none;" | 38:
+
Для повышения степени сжатия изображений данным методом часто используется одна “хитрость” реализации этого алгоритма. Некоторые файлы, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых символов, например <tex>aaaaaaaaaaaaa... </tex> или <tex>303030</tex> … и т. п. Их непосредственное сжатие будет генерировать выходной код <tex>005000600007...</tex>. Спрашивается, можно ли в этом частном случае повысить степень сжатия?
| style="border-left: none;" | OR?
+
 
| style="text-align: left;" | следующей полученной последовательности (BE)
+
Оказывается, это возможно, если оговорить некоторые действия:
 +
 
 +
Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.
 +
*''' ''' Пусть словарь состоит из слов : <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
 +
!  Код  || Биты
 
|-
 
|-
| 100100 || 36
+
| style="text-align: center;" | aa
| style="text-align: center;" | TOB
+
| style="text-align: center;" | a
| style="border-right: none;" | 38:
+
| style="text-align: center;" | a
| style="border-left: none;" | ORT
+
| 0 || 000
| style="border-right: none;" | 39:
+
| style="border-right: none;" | 5:
| style="border-left: none;" | TOB? ||
+
| style="border-left: none;" | aa
 
|-
 
|-
| 011110 || 30
+
| style="text-align: center;" | aa
| style="text-align: center;" | EO
+
| style="text-align: center;" | a
| style="border-right: none;" | 39:
+
| style="text-align: center;" | a
| style="border-left: none;" | TOBE
+
| - || -
| style="border-right: none;" | 40:
+
| style="border-right: none;" | -
| style="border-left: none;" | EO? ||
+
| style="border-left: none;" | -
 
|-
 
|-
| 100000 || 32
+
| style="text-align: center;" | aaa
| style="text-align: center;" | RN
+
| style="text-align: center;" | a
| style="border-right: none;" | 40:
+
| style="text-align: center;" | a
| style="border-left: none;" | EOR
+
| 5 || 101
| style="border-right: none;" | 41:
+
| style="border-right: none;" | 6:
| style="border-left: none;" | RN? ||
+
| style="border-left: none;" | aaa
 
|-
 
|-
| 100010 || 34
+
| style="text-align: center;" | a
| style="text-align: center;" | OT
+
| style="text-align: center;" | a
| style="border-right: none;" | 41:
+
| style="text-align: center;" | a
| style="border-left: none;" | RNO
+
| - || -
| style="border-right: none;" | 42:
+
| style="border-right: none;" | -
| style="border-left: none;" | OT? ||
+
| style="border-left: none;" | -
 
|-
 
|-
| 000000 || 0
+
| style="text-align: center;" | aa
| style="text-align: center;" | #
+
| style="text-align: center;" | a
| style="border-right: none;" |  
+
| style="text-align: center;" | a
| style="border-left: none;" |
+
| - || -
| style="border-right: none;" |
+
| style="border-right: none;" | -
| style="border-left: 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
 
|}
 
|}
  
Единственная небольшая трудность может возникнуть, если новое слово словаря пересылается немедленно. В приведённом выше примере декодирования, когда декодер встречает первый символ, '''T''', он знает, что слово 27 начинается с T, но чем оно заканчивается? Проиллюстрируем проблему следующим примером. Мы декодируем сообщение '''ABABA''':
+
В результате на выходе получаем последовательность <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 ===
011101 = 29    AB      46: (word)  47: AB?
+
 
101111 = 47    AB?  <--- что нам с этим делать?
+
* Алгоритм является однопроходным.
 +
 
 +
* Для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.
 +
 
 +
=== Недостатки алгоритма LZW ===
 +
 
 +
* Алгоритм не проводит анализ входных данных.
  
На первый взгляд, для декодера это неразрешимая ситуация. Мы знаем наперёд, что словом 47 должно быть '''ABA''', но как декодер узнает об этом?
+
==Источники информации==
Заметим, что слово 47 состоит из слова 29 плюс символ идущий следующим. Таким образом, слово 47 заканчивается на «символ идущий следующим». Но, поскольку это слово посылается немедленно, то оно должно начинаться с «символа идущего следующим», и поэтому оно заканчивается тем же символом что и начинается, в данном случае — '''A'''. Этот трюк позволяет декодеру определить, что слово 47 это '''ABA'''.
 
  
В общем случае, такая ситуация появляется, когда кодируется последовательность вида ''cScSc'', где ''c'' — это один символ, а ''S'' — строка, причём слово ''cS'' уже есть в словаре.
+
* [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]
На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странахК настоящему времени, сроки всех патентов истекли.
 
  
=== Unisys, GIF и PNG ===
+
* [http://compression.ru/download/articles/rev_univ/semenyuk_2001_econom_encoding.pdf Семенюк В.В. {{---}} Экономное кодирование дискретной информации]
При разработке формата GIF в CompuServe не знали о существовании патента. В декабре 1994 года, когда в Unisys стало известно об использовании LZW в широко используемом графическом формате, эта компания распространила информацию о своих планах по взысканию лицензионных отчислений с коммерческих программ, имеющих возможность по созданию GIF-файлов. В то время формат был уже настолько широко распространён, что большинство компаний-производителей ПО не имели другого выхода кроме как заплатить. Эта ситуация стала одной из причин разработки графического формата PNG (неофициальная расшифровка: «PNG’s Not GIF»), ставшего третьим по распространённости в Интеренете, после GIF и JPEG. В конце августа 1999 года Unisys прервала действие безвозмездных лицензий на LZW для бесплатного и некоммерческого ПО, а также для пользователей нелицензированных программ, призвав ''League for Programming Freedom'' развернуть кампанию «сожжём все GIF’ы» и информировать публику об имеющихся альтернативах. Многие эксперты в области патентного права отмечали, что патент не распространяется на устройства, которые могут лишь разжимать LZW-данные, но не сжимать их; по этой причине, популярная утилита gzip может читать .Z-файлы, но не записывать их.
 
  
20 июня 2003 года истёк срок оригинального американского патента, что означает, что Unisys не может больше собирать по нему лицензионные отчисления. Аналогичные патенты в Европе, Японии и Канаде истекли в 2004 году.
+
* [http://algolist.manual.ru/compress/standard/lzw.php Метод LZW {{---}} сжатия данных {{---}} алгоритмы и методы]
  
==Источники==
+
* [http://www.compression-pointers.ru/category_42.html Алгоритмы сжатия и компрессии]
  
* [http://ru.wikipedia.org/wiki/LZW Wikipedia | LZW]
+
* [http://www.algoritmy.info/picture5.html Алгоритм LZW {{---}} Понятие алгоритма]
  
* [http://en.wikipedia.org/wiki/LZW Wikipedia | LZW]
+
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Алгоритмы сжатия]]

Текущая версия на 19:17, 4 сентября 2022

Непосредственным предшественником LZW является алгоритм LZ78, опубликованный Абрахамом Лемпелем (Abraham Lempel) и Якобом Зивом (Jacob Ziv) в 1978 г. Этот алгоритм воспринимался как математическая абстракция до 1984 г., когда Терри Уэлч (Terry A. Welch) опубликовал свою работу с модифицированным алгоритмом, получившим в дальнейшем название LZW (Lempel—Ziv—Welch).

Применение

Опубликование алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода.

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

Описание

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

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

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

Алгоритм

Кодирование

  • Начало.
  • Шаг 1. Все возможные символы заносятся в словарь. Во входную фразу [math]X[/math] заносится первый символ сообщения.
  • Шаг 2. Считать очередной символ [math]Y[/math] из сообщения.
  • Шаг 3. Если [math]Y[/math] — это символ конца сообщения, то выдать код для [math]X[/math], иначе:
    • Если фраза [math]XY[/math] уже имеется в словаре, то присвоить входной фразе значение [math]XY[/math] и перейти к Шагу 2 ,
    • Иначе выдать код для входной фразы [math]X[/math], добавить [math]XY[/math] в словарь и присвоить входной фразе значение [math]Y[/math]. Перейти к Шагу 2.
  • Конец.

Декодирование

  • Начало.
  • Шаг 1. Все возможные символы заносятся в словарь. Во входную фразу [math]X[/math] заносится первый код декодируемого сообщения.
  • Шаг 2. Считать очередной код [math]Y[/math] из сообщения.
  • Шаг 3. Если [math]Y[/math] — это конец сообщения, то выдать символ, соответствующий коду [math]X[/math], иначе:
    • Если фразы под кодом [math]XY[/math] нет в словаре, вывести фразу, соответствующую коду [math]X[/math], а фразу с кодом [math]XY[/math] занести в словарь.
    • Иначе присвоить входной фразе код [math]XY[/math] и перейти к Шагу 2 .
  • Конец.

Пример

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

Символ Битовый код Код
a 000 0
b 001 1
c 010 2
d 011 3
e 100 4

Больше в таблице не будет других кодов, обладающих этим свойством.
По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. [math]8[/math]-битные группы дают [math]256[/math] возможных комбинации бит, поэтому, когда в словаре появится [math]256[/math]-е слово, алгоритм должен перейти к [math]9[/math]-битным группам. При появлении [math]512[/math]-ого слова произойдет переход к [math]10[/math]-битным группам, что дает возможность запоминать уже [math]1024[/math] слова и т.д.

В нашем примере алгоритму заранее известно о том, что будет использоваться всего [math]5[/math] различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть [math]3[/math] ([math]8[/math] различных комбинаций).

Кодирование

Пусть мы сжимаем последовательность [math]abacabadabacabae[/math].

  • Шаг 1: Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке [math]a[/math] и проверим, есть ли строка [math]a[/math] в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка [math]a[/math] есть в таблице.
  • Шаг 2: Далее мы читаем следующий символ [math]b[/math] из входного потока и проверяем, есть ли строка [math]ab[/math] в таблице. Такой строки в таблице пока нет.

Добавляем в таблицу [math]\langle5\rangle[/math] [math]ab[/math]. В поток: [math]\langle0\rangle[/math];

  • Шаг 3: [math]ba[/math] — нет. В таблицу: [math]\langle6\rangle[/math] [math]ba[/math]. В поток: [math]\langle1\rangle[/math];
  • Шаг 4: [math]ac[/math] — нет. В таблицу: [math]\langle7\rangle[/math] [math]ac[/math]. В поток: [math]\langle0\rangle[/math];
  • Шаг 5: [math]ca[/math] — нет. В таблицу: [math]\langle8\rangle[/math] [math]ca[/math]. В поток: [math]\langle2\rangle[/math];
  • Шаг 6: [math]ab[/math] — есть в таблице; [math]aba[/math] — нет. В таблицу: [math]\langle9\rangle[/math] [math]aba[/math]. В поток: [math]\langle5\rangle[/math];
  • Шаг 7: [math]ad[/math] — нет. В таблицу: [math]\langle10\rangle[/math] [math]ad[/math]. В поток: [math]\langle0\rangle[/math];
  • Шаг 8: [math]da[/math] — нет. В таблицу: [math]\langle11\rangle[/math] [math]da[/math]. В поток: [math]\langle3\rangle[/math];
  • Шаг 9: [math]aba[/math] — есть в таблице; [math]abac[/math] — нет. В таблицу: [math]\langle12\rangle[/math] [math]abac[/math]. В поток: [math]\langle9\rangle[/math];
  • Шаг 10: [math]ca[/math] — есть в таблице; [math]cab[/math] — нет. В таблицу: [math]\langle13\rangle[/math] [math]cab[/math]. В поток: [math]\langle8\rangle[/math];
  • Шаг 11: [math]ba[/math] — есть в таблице; [math]bae[/math] — нет. В таблицу: [math]\langle14\rangle[/math] [math]bae[/math]. В поток: [math]\langle6\rangle[/math];
  • Шаг 12: И, наконец последняя строка [math]e[/math], за ней идет конец сообщения, поэтому мы просто выводим в поток [math]\langle4\rangle[/math].
Текущая строка Текущий символ Следующий символ Вывод Словарь
Код Биты
ab a b 0 000 5: ab
ba b a 1 001 6: ba
ac a c 0 000 7: ac
ca c a 2 010 8: ca
ab a b - - - -
aba b a 5 0101 9: aba
ad a d 0 0000 10: ad
da d a 3 0011 11: da
ab a b - - - -
aba b a - - - -
abac a c 9 1001 12: abac
ca c a - - - -
cab a b 8 1000 13: cab
ba b a - - - -
bae a e 6 0110 14: bae
e e - 4 0100 - -

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

Закодированное же сообщение так же сначала кодировалось трехбитными группами, а при появлении в словаре восьмого слова — четырехбитными, итого длина сообщения составила [math]4 \cdot 3 + 7 \cdot 4 = 40[/math] бит, что на [math]8[/math] бит короче исходного.

Декодирование

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

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


Данные На выходе Новая запись
Биты Код Полная Частичная
000 0 a - - 5: a?
001 1 b 5: ab 6: b?
000 0 a 6: ba 7: a?
010 2 c 7: ac 8: c?
0101 5 ab 8: ca 9: ab?
0000 0 a 9: aba 10: a?
0011 3 d 10: ad 11: d?
1001 9 aba 11: da 12: aba?
1000 8 ca 12: abac 13: ca?
0110 6 ba 13: cab 14: ba?
0100 4 e 14: bae - -

Примечание

Для повышения степени сжатия изображений данным методом часто используется одна “хитрость” реализации этого алгоритма. Некоторые файлы, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых символов, например [math]aaaaaaaaaaaaa... [/math] или [math]303030[/math] … и т. п. Их непосредственное сжатие будет генерировать выходной код [math]005000600007...[/math]. Спрашивается, можно ли в этом частном случае повысить степень сжатия?

Оказывается, это возможно, если оговорить некоторые действия:

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

  • Пусть словарь состоит из слов : [math]a, b, c, d, e[/math]. Будем кодировать строку [math] aaaaaaaaaa [/math]
  • Итак, кодировщик заносит первую [math]a[/math] в строку, ищет и находит [math]a[/math] в словаре под номером [math]\langle0\rangle[/math]. Добавляет в строку следующую [math]a[/math], находит, что [math]aa[/math] нет в словаре. Тогда он добавляет запись [math]\langle5\rangle[/math]: [math]aa[/math] в словарь и выводит метку [math]\langle0\rangle[/math] ([math]a[/math]) в выходной поток.
  • Далее строка инициализируется второй [math]a[/math], то есть принимает вид [math]a?[/math] вводится третья [math]a[/math], строка вновь равна [math]aa[/math], которая теперь имеется в словаре.
  • Если появляется четвертая [math]a[/math], то строка [math]aa?[/math] равна [math]aaa[/math], которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка [math]\langle5\rangle[/math] ([math]aa[/math]).
  • После этого строка инициализируется третьей [math]a[/math], и т.д. и т.п. Дальнейший процесс вполне ясен.
Работа алгоритма LZW
Слово Номер в словаре
a [math]\langle0\rangle[/math]
b [math]\langle1\rangle[/math]
c [math]\langle2\rangle[/math]
d [math]\langle3\rangle[/math]
e [math]\langle4\rangle[/math]
Текущая строка Текущий символ Следующий символ Вывод Словарь
Код Биты
aa a a 0 000 5: aa
aa a a - - - -
aaa a a 5 101 6: aaa
a a a - - - -
aa a a - - - -
aaa a a - - - -
aaaa a a 6 110 7: aaaa
a a a - - - -
aa a a - - - -
aaa a a - - - -
aaaa a a 7 111 8: aaaaa

В результате на выходе получаем последовательность [math]0567[/math]. При кодировании использовались только трехбитные группы. Длина закодированного сообщения составила [math] 4 \cdot 3 = 12 [/math] бит, что на [math] 7 \cdot 3 - 12 = 9[/math] бит короче кодирования стандартным методом LZW. Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это [math]\langle0\rangle[/math], которому соответствует символ [math]a[/math]. Затем читает код [math]\langle5\rangle[/math], но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть [math]a[/math]. Поэтому он добавит в свою таблицу строку [math]aa[/math] с кодом [math]\langle5\rangle[/math], а в выходной поток поместит [math]aa[/math]. И так может быть раскодирована вся цепочка кодов.

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

Преимущества алгоритма LZW

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

Недостатки алгоритма LZW

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

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