Изменения

← Предыдущая правка

Алгоритм LZW

21 866 байт добавлено, 19:17, 4 сентября 2022

м

rollbackEdits.php mass rollback

~~'''Алгори́тм Ле́мпеля — Зи́ва — Ве́лча''' ('''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).

== Описание ==

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

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

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

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

~~Алгоритм был реализован~~ === Кодирование ===* Начало.* ''' Шаг 1. ''' Все возможные символы заносятся в ~~программе compress~~словарь. Во входную фразу <tex>X</tex> заносится первый символ сообщения.* ''' Шаг 2. ''' Считать очередной символ <tex>Y</tex> из сообщения.* ''' Шаг 3. ''' Если <tex>Y</tex> {{---}} это символ конца сообщения, ~~которая стала более или менее стандартной утилитой Unix-систем приблизительно~~ то выдать код для <tex>X</tex>, иначе: ** Если фраза <tex>XY</tex> уже имеется в словаре, то присвоить входной фразе значение <tex>XY</tex> и перейти к ''' Шагу 2 ''', ** Иначе выдать код для входной фразы <tex>X</tex>, добавить <tex>XY</tex> в ~~1986 году~~словарь и присвоить входной фразе значение <tex>Y</tex>. ~~Несколько других популярных утилит-архиваторов также используют этот метод или близкие~~ Перейти к ~~нему~~''' Шагу 2. '''* Конец.

~~В 1987 году алгоритм стал частью стандарта на формат изображений GIF~~=== Декодирование ===* Начало. ~~Он также может (опционально) использоваться~~ * ''' Шаг 1. ''' Все возможные символы заносятся в словарь. Во входную фразу <tex>X</tex> заносится первый код декодируемого сообщения.* ''' Шаг 2. ''' Считать очередной код <tex>Y</tex> из сообщения.* ''' Шаг 3. ''' Если <tex>Y</tex> {{---}} это конец сообщения, то выдать символ, соответствующий коду <tex>X</tex>, иначе: ** Если фразы под кодом <tex>XY</tex> нет в ~~формате TIFF~~словаре, вывести фразу, соответствующую коду <tex>X</tex>, а фразу с кодом <tex>XY</tex> занести в словарь. ** Иначе присвоить входной фразе код <tex>XY</tex> и перейти к ''' Шагу 2 '''.* Конец.

~~В настоящее время, алгоритм содержится в стандарте PDF.~~== Пример ==

Рассмотрим пример сжатия и декодирования сообщения. Сначала создадим начальный словарь единичных символов. В стандартной кодировке 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> возможных комбинации бит, поэтому, когда в словаре появится <tex>256</tex>-е слово, алгоритм должен перейти к <tex>9</tex>-битным группам. При появлении <tex>512</tex>-ого слова произойдет переход к <tex>10</tex>-битным группам, что дает возможность запоминать уже <tex>1024</tex> слова и т.д. В нашем примере алгоритму заранее известно о том, что будет использоваться всего <tex>5</tex> различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть <tex>3</tex> (<tex>8</tex> различных комбинаций).

# Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы ω первым символом сообщения.~~# Считать очередной символ K из кодируемого сообщения.# Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для ω, иначе~~# Если фраза ωK уже есть в словаре, присвоить входной фразе значение ωK и перейти к Шагу 2, иначе выдать код ω, добавить ωK в словарь, присвоить входной фразе значение K и перейти к Шагу 2.~~Конец~~=== Кодирование ===

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

~~Данный пример показывает алгоритм LZW в действии~~* '''Шаг 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>; ~~TOBEORNOTTOBEORTOBEORNOT#~~* '''Шаг 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> — есть в ~~нашем алфавите 27 символов (26 заглавных букв от A до Z и #)~~таблице; <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> — есть в ~~виде групп бит, для представления каждого символа алфавита нам достаточно группы из 5 бит на символ~~таблице; <tex>abac</tex> — нет. ~~По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы~~В таблицу: <tex>\langle12\rangle</tex> <tex>abac</tex>. ~~5-битные группы дают 2~~В поток: <tex>\langle9\rangle</tex>;* '''Шаг 10: '''<~~sup~~tex>5ca</~~sup~~tex> ~~= 32 возможных комбинации бит, поэтому, когда~~ — есть в ~~словаре появится 33-е слово, алгоритм должен перейти к 6-битным группам~~таблице; <tex>cab</tex> — нет. В таблицу: <tex>\langle13\rangle</tex> <tex>cab</tex>. ~~Заметим, что, поскольку используется группа из всех нолей 00000, то 33-я группа имеет код~~ В поток: <tex>\langle8\rangle</tex>;* '''32Шаг 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: ~~right~~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| ~~00000~~ style="text-align: center;" |b| 0style="text-align: center;" | a| 1 || 001| style="border-right: none;" | 6:| style="border-left: none;" | ba

|-

| A style="text-align: center;" |ac| ~~00001~~ style="text-align: center;" |a| 1style="text-align: center;" | c| 0 || 000| style="border-right: none;" | 7:| style="border-left: none;" | ac

|-

| B style="text-align: center;" |ca| ~~00010~~ style="text-align: center;" |c| style="text-align: center;" | a| 2|| 010| style="border-right: none;" | 8:| style="border-left: none;" | ca

|-

| C style="text-align: center;" |ab| ~~00011~~ style="text-align: center;" |a| 3style="text-align: center;" | b| - || -| style="border-right: none;" | -| style="border-left: none;" | -

|-

| D style="text-align: center;" |aba| ~~00100~~ style="text-align: center;" |b| 4style="text-align: center;" | a| 5 || 0101| style="border-right: none;" | 9:| style="border-left: none;" | aba

|-

| E style="text-align: center;" |ad| ~~00101~~ style="text-align: center;" |a| 5style="text-align: center;" | d| 0 || 0000| style="border-right: none;" | 10:| style="border-left: none;" | ad

|-

| F style="text-align: center;" |da| ~~00110~~ style="text-align: center;" |d| 6style="text-align: center;" | a| 3 || 0011| style="border-right: none;" | 11:| style="border-left: none;" | da

|-

| G style="text-align: center;" |ab| ~~00111~~ style="text-align: center;" |a| 7style="text-align: center;" | b| - || -| style="border-right: none;" | -| style="border-left: none;" | -

|-

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

|-

| I style="text-align: center;" |abac| ~~01001~~ style="text-align: center;" |a| style="text-align: center;" | c| 9|| 1001| style="border-right: none;" | 12:| style="border-left: none;" | abac

|-

| J style="text-align: center;" |ca| ~~01010~~ style="text-align: center;" |c| 10style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -

|-

| K style="text-align: center;" |cab| ~~01011~~ style="text-align: center;" |a| 11style="text-align: center;" | b| 8 || 1000| style="border-right: none;" | 13:| style="border-left: none;" | cab

|-

| L style="text-align: center;" |ba| ~~01100~~ style="text-align: center;" |b| 12style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -

|-

| M style="text-align: center;" |bae| ~~01101~~ style="text-align: center;" |a| 13style="text-align: center;" | e| 6 || 0110| style="border-right: none;" | 14:| style="border-left: none;" | bae

|-

| N style="text-align: center;" |e| ~~01110~~ style="text-align: center;" |e| 14style="text-align: center;" | -| 4 || 0100| style="border-right: none;" | -| style="border-left: none;" | -

|-

| O } Итак, мы получаем закодированное сообщение <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;"| ~~01111~~ - bgcolor = #EEEEEE! colspan="2" |Данные! scope="col" width="6em" rowspan="2" | 15На выходе! 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?

|-

| P 000 || ~~10000~~ 0|style="text-align: center;" | 16a| style="border-right: none;" | 6:| style="border-left: none;" | ba| style="border-right: none;" | 7:| style="border-left: none;" | a?

|-

| Q 010 || ~~10001~~ 2|style="text-align: center;" | 17c| style="border-right: none;" | 7:| style="border-left: none;" | ac| style="border-right: none;" | 8:| style="border-left: none;" | c?

|-

| R 0101 || ~~10010~~ 5|style="text-align: center;" | 18ab| style="border-right: none;" | 8:| style="border-left: none;" | ca| style="border-right: none;" | 9:| style="border-left: none;" | ab?

|-

| S 0000 || ~~10011~~ 0|style="text-align: center;" | 19a| style="border-right: none;" | 9:| style="border-left: none;" | aba| style="border-right: none;" | 10:| style="border-left: none;" | a?

|-

| T 0011 || ~~10100~~ 3|style="text-align: center;" | 20d| style="border-right: none;" | 10:| style="border-left: none;" | ad| style="border-right: none;" | 11:| style="border-left: none;" | d?

|-

| U 1001 || ~~10101~~ 9|style="text-align: center;" | 21aba| style="border-right: none;" | 11:| style="border-left: none;" | da| style="border-right: none;" | 12:| style="border-left: none;" | aba?

|-

| V 1000 || ~~10110~~ 8|style="text-align: center;" | 22ca| style="border-right: none;" | 12:| style="border-left: none;" | abac| style="border-right: none;" | 13:| style="border-left: none;" | ca?

|-

| W 0110 || ~~10111~~ 6|style="text-align: center;" | 23ba| style="border-right: none;" | 13:| style="border-left: none;" | cab| style="border-right: none;" | 14:| style="border-left: none;" | ba?

|-

| X 0100 || ~~11000~~ 4|style="text-align: center;" | 24e| style="border-right: none;" | 14:| style="border-left: none;" | bae| style="border-right: none;" | -| style="border-left: none;" | -

|-

| Y } === Примечание === Для повышения степени сжатия изображений данным методом часто используется одна “хитрость” реализации этого алгоритма. Некоторые файлы, подвергаемые сжатию с помощью 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| ~~11001~~ Работа алгоритма LZW]] {|class="wikitable" border = 1, style="text-align: center; margin-left: auto; margin-right: auto;"| 25- bgcolor=#EEEEEE! Слово !! Номер в словаре

|-

| Z a || ~~11010 || 26~~<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