Опрос

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

Новички

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

LZ78

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

Алгоритм LZ

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

LZW

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

Метод LZ78 (иногда его называют LZ2, см. [Ziv 78]) не использует буфер поиск, упреждающий буфер и скользящее окно. Вместо этого имеется словарь встретившихся ранее строк. В начале этот словарь пуст (или почти пуст), и размер этого словаря ограничен только объемом доступной памяти. На выход кодера поступает последовательность меток, состоящих из двух полей. Первое поле -это указатель на строку в словаре, а второе - код символа. Метка не содержит длины строки, поскольку строка берется из словаря. Каждая метка соответствует последовательности во входном файле, и эта последовательность ...

Перед тем, как обсуждать алгоритм LZ78, остановимся на недостатках метода LZ77 и его вариантов. Было уже отмечено, что этот алгоритм основывается на предположении, что похожие образцы сжимаемых данных находятся близко друг от друга. Если содержимое файла не удовлетворяет этому условию, то он будет сжиматься плохо. Простой пример - это текст, в котором слово «economy» встречается часто и равномерно распределено по всему тексту. Может случиться, что когда это слово попадает в упреждающий буфер, его предыдущая копия уже вышла из буфера просмотра. Более лучший алгоритм мог бы сохранять ...

1. Какие свойства данных определяют принципиальную возможность их сжатия с помощью LZ-методов?

2. В чем основная разница между алгоритмами семейства LZ77 и семейст­ва LZ78?

3. Какие особенности строения словаря LZ77 позволяют создавать для од­ного и того же входного файла несколько различных архивных, которые затем можно разжать без потерь информации с помощью одного и того же декодера LZ77? Возможно ли это в случае алгоритма LZ78?

4. Почему в алгоритмах семейства LZ77 короткие строки часто выгоднее сжимать не с помощью словарной замены, а через кодирование как ...

Улучшать сжатие алгоритмов семейства Зивц - Лемпела можно двумя путями:

1) уменьшением количества указателей при неизменной или большей общей длине закодированных фраз за счет более эффективного раз­биения входной последовательности на фразы словаря;

2) увеличением эффективности кодирования индексов фраз словаря и литералов, т. е. уменьшением количества битов, в среднем требуемых для кодирования индекса или литерала.

Идея приемов, относящихся к первому пути, была продемонстрирована на примере ленивого сравнения при описании Deflate. Действительно, для одного и того ...

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

Таблица 3.4

Названия

Авторы, год

Тип ...

Алгоритмы словарного сжатия Зива-Лемпела появились во второй поло­вине 70-х гг. Это были так называемые алгоритмы LZ77 и LZ78, разрабо­танные совместно Зивом (Ziv) и Лемпелом (Lempel). В дальнейшем перво­начальные схемы подвергались множественным изменениям, в результате чего мы сегодня имеем десятки достаточно самостоятельных алгоритмов и бессчетное количество модификаций.

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