Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

LZW

Здесь описаны основные современные методы сжатия: метод Хаффмана, арифметическое кодирование, LZ77, BWT, LZW,LPC, PPM. Описываются алгоритмы, которые используются в архиваторах Zip, 7-Zip НА, CabArc(это *.саЬ-файлы), RAR, BZIP2, RK. Отдельный раздел посвящен алгоритмам сжатия изображений, использующимся в форматах JPEG, JPEG2000, GIF, TIFF, PCX, TGA, CCITT G-3. Рассмотрено вэйвлет-сжатие, фрактальное сжатие. А также рассказано о принципах компрессии видеоданных по стандартам MPEG, MPEG-2, MPEG-4, H.261 и Н.263.

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

Алгоритм LZ

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

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

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

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

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

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

LZW

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

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

Таблица 3.4

Названия

Авторы, год

Тип ...


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

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

Поточные

Блочные1''

" Поточные

Блочные

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