13.1 Описание алгоритма сжатия LZW.

Привет, сегодня поговорим про lzw , обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое lzw , настоятельно рекомендую прочитать все из категории Теория информации и кодирования.

13.1 Описание алгоритма сжатия LZW.

В методе сжатия LZW используется начальный словарь ВСЕХ различных символов кодируемого текста. Он может строиться путем анализа всего текста. Но чаще в качестве начального словаря используется готовая и всем известная стандартная табличка символов ASCII+.

Процесс сжатия выглядит следующим образом.

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

-Если такая строка существует, считывается следующий символ,

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

Например, если сжимают байтовые данные (текст), то строк в начальной таблице(ASCII+) словаре окажется 256 (от «0» до «255»). Если используется 10-битный код, то под коды для новых строк остаются значения в диапазоне от 256 до 1023. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом.

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

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

Пример 13.1 Сжимаем текст "abacabadabacabae"

Сначала создадим начальный словарь единичных символов. В стандартной кодировке ASCII имеется 256 различных символов, поэтомуначальный размер кода для кодирования одного символа будет равен 8 битам. Если нам заранее известно, что в исходном файле будет меньшее количество различных символов, то вполне разумно уменьшить количество бит для кодирования символа.

Чтобы инициализировать таблицу, мы установим соответствие кода 0 соответствующему символу с байтом 00000000, тогда 1 соответствует символу с байтом 00000001, 7 –соответствует 00000111 и т.д., до кода 255.

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

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

Кодирование

Итак, пусть мы сжимаем последовательность «abacabadabacabae».

 ·                     Шаг 1: Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке “a” и проверим, есть ли строка “a” в таблице. Об этом говорит сайт https://intellect.icu . Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “a” есть в таблице.

  ·                       Шаг 2: Далее мы читаем следующий символ «b» из входного потока и проверяем, есть ли строка “ab” в таблице. Такой строки в таблице пока нет.

  ·                      Добавляем в таблицу <5> “ab”. В выход: <0>;

 ·                      Шаг 3: “ba” — нет. В словарь: <6> “ba”. В выход: <1>;

 ·                       Шаг 4: “ac” — нет. В словарь: <7> “ac”. В выход: <0>;

 ·                       Шаг 5: “ca” — нет. В словарь: <8> “ca”. В выход: <2>;

  ·                  Шаг 6: “ab” — есть в словаре; “aba” — нет. В словарь: <9> “aba”. В выход: <5>;

 ·                       Шаг 7: “ad” — нет. В словарь: <10> “ad”. В выход: <0>;

 ·                       Шаг 8: “da” — нет. В словарь: <11> “da”. В выход: <3>;

 ·                       Шаг 9: “aba” — есть в словаре; “abac” — нет. В словарь: <12> “abac”. В выход: <9>;

 ·            Шаг 10: “ca” — есть в таблице; “cab” — нет. В словарь: <13> “cab”. В выход: <8>;

 ·                    Шаг 11: “ba” — есть в таблице; “bae” — нет. В словарь: <14> “bae”. В выход: <6>;

 ·                      Шаг 12: И, наконец последняя строка “e”, за ней идет конец сообщения, поэтому мы просто выводим<4>.

Итак, мы получаем закодированное сообщение «0 1 0 2 5 0 3 9 8 6 4», что на 11 бит короче. При этом для расшифровки необходимо дополнительно хранить начальный словарь : 0-a, 1-b, 2-c, 3-d, 4-e.

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

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

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

Итак, декодирование.

Достоинства и недостатки LZW

Достоинства

- Не требует вычисления вероятностей встречаемости символов или кодов.

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

- Данный тип компрессии не вносит искажений в исходный файл, и подходит для сжатия данных любого типа.

Недостатки

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

13.2ПрименениеLZ-алгоритмовупаковкиданных.

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

Если коды алгоритмов типа LZ передать для кодирования (адаптивному) алгоритму Хаффмена , то полученный двухшаговый (конвейерный, а не двухпроходный) алгоритм даст результаты сжатия подобные широко известным программам: GZIP, ARJ, PKZIP,

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

Большинство программ-архиваторов сжимает каждый файл по отдельности, но некоторые сжимают файлы в общем потоке, что дает увеличение степени сжатия, но одновременно усложняет способы работы с полученным архивом, . Примером программы, имеющей возможность сжимать файлы в общем потоке, является RAR. Архиваторы ОС Unix (gzip, bzip2, ...) сжимают файлы в общем потоке практически всегда.

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

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

Таблица 13.1

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

13.3Контрольныевопросы.

1. Почему метод кодирования LZW может кодировать сообщения короче, чем методы LZ77 или LZ78?

2. Возможно ли декодирование кода LZW без точного знания начального словаря исходного сообщения?

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

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.