LZW

Алгоритмы и методы сжатия данных

Здесь описаны основные современные методы сжатия: метод Хаффмана, арифметическое кодирование, LZ77, BWT, LZW,LPC, PPM. Описываются алгоритмы, которые используются в архиваторах Zip, 7-Zip НА, CabArc(это *.саЬ-файлы), RAR, BZIP2, RK.

Алгоритм LZW

Название алгоритм получил по первым буквам фамилий его разработчи­ков - Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байтов. Алгоритм LZW является самым из­вестным представителем семейства словарных методов LZ78 (см. гл. 3 под-разд. 1).

Алгоритм LZ

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

Критерии сравнения алгоритмов

Заметим, что характеристики алгоритма относительно некоторых требо­ваний приложений, сформулированные выше, зависят от конкретных усло­вий, в которые будет поставлен алгоритм. Так, степень компрессии зависит от того, на каком классе изображений алгоритм тестируется. Аналогично скорость компрессии нередко зависит от того, на какой платформе реализо­ван алгоритм. Преимущество одному алгоритму перед другим может дать, например, возможность использования в вычислениях алгоритма техноло­гий нижнего уровня, типа ММХ, а это возможно далеко не для всех алго­ритмов. Так, JPEG ...

LZW в практических приложениях

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

Структура словаря LZW

До этого момента считалось, что словарем LZW служит массив из строк переменной длины. Чтобы понять, почему специальное дерево будет являться лучшей структурой для словаря, следует напомнить работу кодера. Он считывает символы и добавляет их в строку I до тех пор, пока I находится в словаре. В некоторый момент строка 1х в словаре не обнаруживается, и тогда строка 1х помещается в словарь. Значит, при добавлении новых строк в словарь поступает всего один новый символ х. Это предложение можно перефразировать еще так: для каждой словарной строки в словаре найдется «родительская» строка, ...

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

Для того, чтобы понять как работает декодер метода LZW, прежде всего еще раз напомним основные три шага, которые выполняет кодер каждый раз, делая очередную запись в выходной файл: (1) он заносит туда словарный указатель на строку I, (2) сохраняет строку 1х в следующей свободной позиции словаря и (3) инициализирует строку I символом х.

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

LZW

Это весьма популярный вариант алгоритма LZ78, который был разработан Терри Уэлчем (Terry Welch) в 1984 ([Welch 84] и [Phillips 92]). Его главной особенностью является удаление второго поля из метки. Метка LZW состоит только из указателя на место в словаре. Для лучшего понимания алгоритма LZW мы временно забудем, что словарь является деревом и будем предполагать, что словарь - это просто массив, состоящий из строк разной длины. Метод LZW начинается инициализацией словаря всеми символами исходного алфавита. В общем случае 8-битного алфавита, первые 256 записей (отдельные символы с ...

Другие алгоритмы LZ

В табл. 3.4 приведены несколько достаточно характерных алгоритмов LZ. Указанный список далеко не полон, реально существует в несколько раз больше алгоритмов, основанных либо на LZ77, либо на LZ78. Известны и гибридные схемы, сочетающие оба подхода к построению словаря.

Таблица 3.4

№

Названия

Авторы, год

Тип ...

Карта групп методов сжатия

Статистические

Преобразующие

Поточные

Блочные1''

" Поточные

Блочные

Для "слов", модель "Источник с ...