84
правки
Изменения
м
<br>
<br>
<br>
<br><br><br>
<br><br>
<br><br>
<br>
Нет описания правки
== Применение ==
Опубликование алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода. <br>
Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. В настоящее время испольуется в файлах формата TIFF, PDF, GIF, PostScript и других, а также отчасти во многих популярных программах сжатия данных (ZIP, ARJ, LHA).
По мере роста словаря, размер групп должен расти, с тем, чтобы учесть новые элементы. 8-битные группы дают 256 возможных комбинации бит, поэтому, когда в словаре появится 256-е слово, алгоритм должен перейти к 9-битным группам. При появлении 512-ого слова произойдет переход к 10-битным группам, что дает возможность запоминать уже 1024 слова и т.д.
В нашем примере алгоритму заранее известно о том, что будет использоваться всего 5 различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть 3 ( 8 различных комбинаций ).
Пусть мы сжимаем последовательность "abacabadabacabae".
Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке “a” и проверим, есть ли строка “a” в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “a” есть в таблице. <br>Далее мы читаем следующий символ "b" из входного потока и проверяем, есть ли строка “ab” в таблице. Такой строки в таблице пока нет. <br>Добавляем в таблицу <5> “ab”. В поток: <0>; <br>“ba” — нет. В таблицу: <6> “ba”. В поток: <1>; <br>“ac” — нет. В таблицу: <7> “ac”. В поток: <0>; <br>“ca” — нет. В таблицу: <8> “ca”. В поток: <2>; <br>“ab” — есть в таблице; “aba” — нет. В таблицу: <9> “aba”. В поток: <5>;<br>“ad” — нет. В таблицу: <10> “ad”. В поток: <0>; <br>“da” — нет. В таблицу: <11> “da”. В поток: <3>; <br>“aba” — есть в таблице; “abac” — нет. В таблицу: <12> “abac”. В поток: <9>;<br>“ca” — есть в таблице; “cab” — нет. В таблицу: <13> “cab”. В поток: <8>;<br>“ba” — есть в таблице; “bae” — нет. В таблицу: <14> “bae”. В поток: <6>;<br>
И, наконец последняя строка “e”, за ней идет конец сообщения, поэтому мы просто выводим в поток <4>.
=== Декодирование ===
Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов. <br>
Теперь представим ,что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей.
=== Примечание ===
Для повышения степени сжатия изображений данным методом часто используется одна «хитрость» реализации этого алгоритма. Некоторые файлы, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых символов, например aaaaaa … или 30, 30, 30 … и т. п. Их непосредственное сжатие будет генерировать выходной код 0, 0, 5 и т.д. Спрашивается, можно ли в этом частном случае повысить степень сжатия? <br>
Оказывается, это возможно, если оговорить некоторые действия:
[[Файл:Image001.gif|left|Работа алгоритма LZW]]
Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.
Итак, кодер заносит первую «а» в строку, ищет и находит "а" в словаре. Добавляет в строку следующую "а", находит, что "аа" нет в словаре. Тогда он добавляет запись <5>: "аа" в словарь и выводит метку <0> ("а") в выходной поток. Далее строка инициализируется второй «а», то есть принимает вид "a?" вводится третья «а», строка вновь равна "аа", которая теперь имеется в словаре. Если появляется четвертая «а», то строка "aa?" равна "ааа", которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка <5> ("aa"). После этого строка инициализируется третьей «а», и т.д. и т.п. Дальнейший процесс вполне ясен. <br>
В результате на выходе получаем последовательность 0, 5, 6 …, которая короче прямого кодирования стандартным методом LZW.
Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это <0>, которому соответствует символ "a". Затем читает код <5>, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть "a". Поэтому он добавит в свою таблицу строку "aa" с кодом <5>, а в выходной поток поместит "aa". И так может быть раскодирована вся цепочка кодов.
Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым символам, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.
== Достоинства и недостатки ==
+ Не требует вычисления вероятностей встречаемости символов или кодов. <br>+ Для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.<br>+ Данный тип компрессии не вносит искажений в исходный графический файл, и подходит для сжатия растровых данных любого типа. <br>- Алгоритм не проводит анализ входных данных поэтому не оптимален. <br>
На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах.
Среди обладателей патентов была компания Unisys. Поэтому использование формата GIF, в котором он используется, было раскритиковано из-за лицензионных отчислений. Был предложен альтернативный формат PNG (PNG not GIF).
