Изменения

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

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

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

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

Данный Для декодирования на вход подается только закодированный текст, поскольку алгоритм при сжатии (кодировании) динамически создаёт LZW может воссоздать соответствующую таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные)непосредственно по закодированному тексту. Таблица инициализируется всеми 1-символьными строками (Алгоритм генерирует однозначно декодируемый код за счет того, что каждый раз, когда генерируется новый код, новая строка добавляется в случае 8-битных символов — это 256 записей)таблицу строк. По мере кодированияLZW постоянно проверяет, алгоритм просматривает текст символ за символомявляется ли строка уже известной, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символесли так, где выводит существующий код ссылается на соответствующий первый символбез генерации нового. После того как новая 2-символьная Таким образом, каждая строка сохранена будет храниться в таблице, на выход передаётся код первого символаединственном экземпляре и иметь свой уникальный номер. Когда на входе читается очередной символСледовательно, для него по таблице находится уже встречавшаяся при декодировании во время получения нового кода генерируется новая строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строкиа при получении уже известного, а следующий символ используется в качестве начала следующей строкистрока извлекается из словаря.

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

Данный Рассмотрим пример показывает алгоритм LZW сжатия и декодирования сообщения. Сначала создадим начальный словарь единичных символов. В стандартной кодировке 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;" TOBEORNOTTOBEORTOBEORNOT|- bgcolor=#EEEEEE! Символ !! Битовый код !! Код |-| a || 000 || 0|-| b || 001 || 1Маркер '''#''' используется для обозначения конца сообщения. Тем самым, |-| c || 010 || 2|-| d || 011 || 3|-| e || 100 || 4|} Больше в нашем алфавите 27 символов (26 заглавных букв от A до Z и #). Компьютер представляет это в виде групп биттаблице не будет других кодов, для представления каждого символа алфавита нам достаточно группы из 5 бит на символобладающих этим свойством. <br>По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 5<tex>8</tex>-битные группы дают 2<suptex>5256</suptex> = 32 возможных комбинации бит, поэтому, когда в словаре появится 33<tex>256</tex>-е слово, алгоритм должен перейти к 6<tex>9</tex>-битным группам. ЗаметимПри появлении <tex>512</tex>-ого слова произойдет переход к <tex>10</tex>-битным группам, что, поскольку используется группа из всех нолей 00000, то 33-я группа имеет код '''32'''дает возможность запоминать уже <tex>1024</tex> слова и т.д. Начальный словарь будет содержать:

В нашем примере алгоритму заранее известно о том, что будет использоваться всего <tex>5</tex> различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть <tex>3</tex> (<tex>8</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: rightcenter; 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| 00000 style="text-align: center;" |a| style="text-align: center;" | b| 0|| 000| style="border-right: none;" | 5:| style="border-left: none;" | ab

| A style="text-align: center;" |ba| 00001 style="text-align: center;" |b| style="text-align: center;" | a| 1|| 001| style="border-right: none;" | 6:| style="border-left: none;" | ba

| B style="text-align: center;" |ac| 00010 style="text-align: center;" |a| 2style="text-align: center;" | c| 0 || 000| style="border-right: none;" | 7:| style="border-left: none;" | ac

| C style="text-align: center;" |ca| 00011 style="text-align: center;" |c| 3style="text-align: center;" | a| 2 || 010| style="border-right: none;" | 8:| style="border-left: none;" | ca

| D style="text-align: center;" |ab| 00100 style="text-align: center;" |a| 4style="text-align: center;" | b| - || -| style="border-right: none;" | -| style="border-left: none;" | -

| E style="text-align: center;" |aba| 00101 style="text-align: center;" |b| style="text-align: center;" | a| 5|| 0101| style="border-right: none;" | 9:| style="border-left: none;" | aba

| F style="text-align: center;" |ad| 00110 style="text-align: center;" |a| 6style="text-align: center;" | d| 0 || 0000| style="border-right: none;" | 10:| style="border-left: none;" | ad

| G style="text-align: center;" |da| 00111 style="text-align: center;" |d| 7style="text-align: center;" | a| 3 || 0011| style="border-right: none;" | 11:| style="border-left: none;" | da

| H style="text-align: center;" |ab| 01000 style="text-align: center;" |a| 8style="text-align: center;" | b| - || -| style="border-right: none;" | -| style="border-left: none;" | -

| I style="text-align: center;" |aba| 01001 style="text-align: center;" |b| 9style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -

| J style="text-align: center;" |abac| 01010 style="text-align: center;" |a| 10style="text-align: center;" | c| 9 || 1001| style="border-right: none;" | 12:| style="border-left: none;" | abac

| K style="text-align: center;" |ca| 01011 style="text-align: center;" |c| 11style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -

| L style="text-align: center;" |cab| 01100 style="text-align: center;" |a| 12style="text-align: center;" | b| 8 || 1000| style="border-right: none;" | 13:| style="border-left: none;" | cab

| M style="text-align: center;" |ba| 01101 style="text-align: center;" |b| 13style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -

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

| O style="text-align: center;" |e| 01111 style="text-align: center;" |e| 15style="text-align: center;" | -| 4 || 0100| style="border-right: none;" | -| style="border-left: none;" | -

| P } Итак, мы получаем закодированное сообщение <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" | 10000 На выходе! colspan="4" |Новая запись| 16- 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?

| Q 001 || 10001 1|style="text-align: center;" | 17b| style="border-right: none;" | 5:| style="border-left: none;" | ab| style="border-right: none;" | 6:| style="border-left: none;" | b?

| R 000 || 10010 0|style="text-align: center;" | 18a| style="border-right: none;" | 6:| style="border-left: none;" | ba| style="border-right: none;" | 7:| style="border-left: none;" | a?

| S 010 || 10011 2|style="text-align: center;" | 19c| style="border-right: none;" | 7:| style="border-left: none;" | ac| style="border-right: none;" | 8:| style="border-left: none;" | c?

| T 0101 || 10100 5|style="text-align: center;" | 20ab| style="border-right: none;" | 8:| style="border-left: none;" | ca| style="border-right: none;" | 9:| style="border-left: none;" | ab?

| U 0000 || 10101 0|style="text-align: center;" | 21a| style="border-right: none;" | 9:| style="border-left: none;" | aba| style="border-right: none;" | 10:| style="border-left: none;" | a?

| V 0011 || 10110 3|style="text-align: center;" | 22d| style="border-right: none;" | 10:| style="border-left: none;" | ad| style="border-right: none;" | 11:| style="border-left: none;" | d?

| W 1001 || 10111 9|style="text-align: center;" | 23aba| style="border-right: none;" | 11:| style="border-left: none;" | da| style="border-right: none;" | 12:| style="border-left: none;" | aba?

| X 1000 || 11000 8|style="text-align: center;" | 24ca| style="border-right: none;" | 12:| style="border-left: none;" | abac| style="border-right: none;" | 13:| style="border-left: none;" | ca?

| Y 0110 || 11001 6|style="text-align: center;" | 25ba| style="border-right: none;" | 13:| style="border-left: none;" | cab| style="border-right: none;" | 14:| style="border-left: none;" | ba?

| Z 0100 || 11010 4|style="text-align: center;" | 26e| style="border-right: none;" | 14:| style="border-left: none;" | bae| style="border-right: none;" | -| style="border-left: none;" | -

=== Кодирование Примечание ===Без использования Для повышения степени сжатия изображений данным методом часто используется одна “хитрость” реализации этого алгоритма . Некоторые файлы, подвергаемые сжатию с помощью LZW, при передаче сообщения как оно есть — 25 имеют часто встречающиеся цепочки одинаковых символов по 5 бит на каждый — оно займёт 125 бит, например <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>|}

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

| style="text-align: center;" | Taa| style="text-align: center;" | O| 20 || 10100a| style="bordertext-rightalign: nonecenter;" | 27:a| 0 || 000| style="border-leftright: none;" | TO5:| style="textborder-alignleft: leftnone;" | aa

| style="text-align: center;" | Oaa| style="text-align: center;" | Ba| 15 style="text-align: center;" |a| 01111- || -| style="border-right: none;" | 28:-| style="border-left: none;" | OB ||-

| style="text-align: center;" | Baaa| style="text-align: center;" | Ea| 2 style="text-align: center;" | a|5 | 00010| 101| style="border-right: none;" | 296:| style="border-left: none;" | BE ||aaa

| style="text-align: center;" | Ea| style="text-align: center;" | Oa| 5 style="text-align: center;" |a| 00101- || -| style="border-right: none;" | 30:-| style="border-left: none;" | EO ||-

| style="text-align: center;" | Oaa| style="text-align: center;" | Ra| 15 style="text-align: center;" |a| 01111- || -| style="border-right: none;" | 31:-| style="border-left: none;" | OR ||-

| style="text-align: center;" | Raaa| style="text-align: center;" | N| 18 || 10010a| style="bordertext-rightalign: nonecenter;" | 32:a| - || -| style="border-leftright: none;" | RN-| style="textborder-alignleft: leftnone;" | -

| style="text-align: center;" | Naaaa| style="text-align: center;" | Oa| 14 style="text-align: center;" | a| 6 || 001110110| style="border-right: none;" | 337:| style="border-left: none;" | NO || начинаем использовать 6 битовaaaa

| style="text-align: center;" | Oa| style="text-align: center;" | Ta| 15 style="text-align: center;" |a| 001111- || -| style="border-right: none;" | 34:-| style="border-left: none;" | OT ||-

| style="text-align: center;" | Taa| style="text-align: center;" | T| 20 || 010100| style="border-right: none;" | 35:| style="border-left: none;" | TT |||-a| style="text-align: center;" | TOa| style="text-align: center;" | B| 27 || 011011-| style="border-right: none;" | 36:-| style="border-left: none;" | TOB |||-| style="text-align: center;" | BE| style="text-align: center;" | O| 29 || 011101| style="border-right: none;" | 37:| style="border-left: none;" | BEO ||

| style="text-align: center;" | ORaaa| style="text-align: center;" | T| 31 || 011111| style="border-right: none;" | 38:| style="border-left: none;" | ORT |||-| style="text-align: center;" | TOBa| style="text-align: center;" | E| 36 || 100100| style="border-right: none;" | 39:| style="border-left: none;" | TOBE ||a|-| style="text-align: center;" | EO| style="text-align: center;" | R| 30 || 011110| style="border-right: none;" | 40:| style="border-left: none;" | EOR |||-| style="text-align: center;" | RN| style="text-align: center;" | O| 32 || 100000| style="border-right: none;" | 41:| style="border-left: none;" | RNO |||-| 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: left;" | и останавливаем кодирование

Таким образом, используя LZW мы сократили сообщение на 29 бит из 125 — это почти 22 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более [[Категория: Дискретная математика и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.алгоритмы]][[Категория: Алгоритмы сжатия]]