Опрос

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

Новички

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

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

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

Таблица 3.4

Названия

Авторы, год

Тип алгоритма

1

LZMW

Миллер (Miller) и Уэгнам (Wegman), 1984

Алгоритм семейства LZ78

2

LZW

Уэлч (Welch), 1984

Модификация LZ78

3

LZB

Белл (Bell), 1987

Модификация LZSS

4

LZH

Брент (Brent), 1987

Модификация LZSS

5

LZFG

Файэлэ (Fiala) и Грини (Greene), 1989

Модификация LZ77

6

LZBW

Бендер (Bender) и Вулф (Wolf). 1991

Способ модификация ал­горитмов семейства LZ77

7

LZRW1

У илльямс (Williams), 1991

Модификация LZSS

8

LZCB

Блум (Bloom), 1995

Модификация LZ77

9

LZP

Блум (Bloom), 1995

Основан на LZ77

10

LZ77-PM, LZFG-PM, LZW-PM

Хоанг (Hoang), Лонг (Long) и Виттер (Vitter), 1995

Модификации алгоритмов LZ

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

Среднее по времени равно среднему по числу реализаций; иначе говоря, дл оценки свойств источника достаточно только одной длинной сгенерированной по следовательности.

1. LZMW. Алгоритм семейства LZ78. Интересен способом построения словаря: новая фраза создается с помощью конкатенации двух послед­них использованных фраз, а не конкатенации фразы и символа, т. е. сло­варь наполняется "агрессивнее". Практические реализации LZMW в про­граммах универсального сжатия неизвестны. Причина, по-видимому, со­стоит в том, что усложнение алгоритма не приводит к адекватному улучшению сжатия по сравнению с исходным LZW. С другой стороны, выгода от быстрого заполнения и обновления словаря проявляется глав­ным образом при обработке неоднородных данных. Но для сжатия дан­ных такого типа заведомо лучше подходит метод скользящего словаря (семейство LZ77).

2. LZW. Модификация LZ78. За счет предварительного занесения в сло­варь всех символов алфавита входной последовательности результат ра­боты LZW состоит только из последовательности индексов фраз слова­ря. Из-за устранения необходимости регулярной передачи одного сим­вола в явном виде LZW обеспечивает лучшее сжатие, чем LZ78. Подробнее об LZW см. в разд. 2, а также в [11].

3. LZB. Модификация LZSS. Изменения затрагивают кодирование указа­телей. Смещение задается переменным количеством битов в зависимо­сти от реального размера словаря (в начале сжатия он мал). Длина сов­падения записывается у-кодами Элиаса. И первый и второй механизм часто применяются при разработке простых и обеспечивающих высокую скорость алгоритмов семейства LZ77.

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

5. LZFG. Модификация LZ77. На самом деле представляет собой несколь­ко алгоритмов. Идея самого сложного (С2 в обозначении авторов LZFG) заключается в кодировании фразы не парой <длина, смещение>, а ин­дексом соответствующего фразе узла дерева цифрового поиска. Одина­ковые фразы словаря имеют один и тот же индекс, что и обеспечивает более экономное кодирование строк. Алгоритмы LZFG не получили рас­пространения на практике. В значительной степени этому способствова­ли патентные ограничения.

6. LZBW. Способ модификации алгоритмов семейства LZ77. За счет учета имеющихся в словаре одинаковых фраз позволяет уменьшить количест­во битов, требуемых для кодирования длины совпадения. Подробнее см. в подразд. "Пути улучшения сжатия алгоритмов LZ".

7. LZRW1. Алгоритм является модификацией LZSS, точнее, алгоритма А1 группы LZFG и разработан с целью обеспечения максимальной скорости сжатия и разжатия. Коды фраз состоят из 16 бит: 12 бит указывают сме­щение i и 4 бита задают длину совпадения у, а символы s передаются как байты (требуют 8 бит). Флаги /задаются сразу для последовательности из 16 кодов и литералов, т. е. сначала выдается 2-байтовое слово значе­ний флагов, затем группа из 16 кодов и/или литералов. Для поиска в сло­варе при сжатии используется хеш-таблица со смешиванием по трем символам. Хеш-цепочки как таковые отсутствуют, т. е. каждая новая фраза заменяет в таблице старую с таким же значением хеш-функции. За счет устранения побитового ввода-вывода и использования словаря ма­лого размера достигается высокая скорость кодирования и декодирова­ния. Степень сжатия LZRW1 равна примерно 1.5-2.

8. LZCB. По сути, целая группа алгоритмов, являющихся той или иной модификацией LZ77. Основная идея заключается во введении достаточ­но сильного ограничения на минимальную длину совпадения - от четы­рех символов и более. Если фраза удовлетворяющей длины не найдена, то кодируется один символ (литерал). Характер типичных данных таков, что литералы и успешно закодированные с помощью словаря строки имеют тенденцию объединяться в группы с себе подобными, т. е., на­пример, на выходе LZCB могут появиться 10 литералов подряд, затем 5 закодированных строк, затем опять несколько литералов и т. д. Эта осо­бенность позволяет реализовать достаточно эффективное статистическое кодирование потоков литералов и указателей фраз. Тем не менее, расте­ряв преимущество в скорости, LZCB уступает современным алгоритмам РРМ по коэффициенту сжатия.

9. LZP. Основан на LZ77. Для каждого входного символа строка из пред­шествующих L символов рассматривается как контекст С длины N. С помощью хеш-функции в словаре находится одна из совпадающих с контекстом С фраз, назовем эту фразу С: С'= С. Строка S буфера срав­нивается с фразой, непосредственно следующей за С". Если длина совпа­дения L > 0, то выдается флаг успеха/= 1 и S кодируется через длину L. Так как С находится детерминированным образом, то смещение коди­ровать не надо. Если 1 = 0 или С не была найдена, то выдается/= 0 и первый символ S кодируется непосредственно. Декодер должен исполь­зовать такой же механизм для поиска С. Изложенный алгоритм справедлив для алгоритма LZP1, достоинством которого является высокая скорость. В более сложных модификациях процесс поиска С повторяет­ся для контекста длины ЛМ и т. д. В LZP1 литералы просто копируются, а для кодирования флагов и длин используются коды переменной длины. В LZP3 применяется достаточно сложная схема кодирования потоков флагов, длин и литералов на основе алгоритма Хаффмана. В сочетании с РРМ техника LZP обеспечивает высокую степень сжатия при неплохих скоростных характеристиках. 10.LZ77-PM, LZFG-PM, LZW-PM. Модификации алгоритмов LZ. Исполь­зуется несколько контекстнозависимых словарей, а не один словарь. В контекстнозависимый словарь порядка L с номером / попадают только строки, встречаемые после контекста' С,- длины L. Кодирование строки буфера S производится с помощью одного или нескольких словарей, но­мера которых определяются последними закодированными перед S сим­волами. Учет контекста позволяет существенно улучшить сжатие исход­ных словарных схем. Подробнее см. в подразд. "Пути улучшения сжатия алгоритмов LZ".

В табл. 3.5 приведены результаты сравнения нескольких алгоритмов по
степени сжатия на наборе CalgCC. \

Таблица 3.5

LZP1

LZSS

LZW

LZB

LZW-PM

LZFG

LZFG-PM

LZP3

Bib

1.98

2.81

2.48

2.52

3.07

2.76

3.28

3.32

Bookl

1.42

2.33

2.52

2.07

2.92

2.21

2.44

2.50

Book2

1.76

2.68

2.61

2.44

3.14

2.62

2.88

3.01

Geo

1.19

1.19

1.38

1.30

1.23

1.40

1.42

1.51

News

1.76

2.28

2.21

2.25

2.52

2.33

2.46

2.78

Objl

1.55

1.57

1.58

1.88

1.56

1.99

1.85

1.83

Obj2

2.21

2.28

1.96

2.55

2.34

2.70

2.63

2.79

Paperl

1.72

2.47

2.21

2.48

2.60

2.64

2.92

2.73

Paper2

1.62

2.50

2.37

2.33

2.72

2.53

2.86

2.72

Pic

6.30

3.98

8.51

7.92

8.16

9.20

8.60

9.30

Progc

1.86

2.44

2.15

2.60

2.52

2.77

2.92

2.73

Progl

2.66

3.28

2.71

3.79

3.38

4.06

4.44

4.19

Progp

2.82

3.31

2.67

3.85

3.33

4.21

4.42

3.98

Trans

3.27

3.46

2.53

3.77

3.46

4.55

4.79

4.79

Итого

2.29

2.61

2.71

2.98

3.07

3.28

3.42

3.44

Контекст - это в данном случае конечная последовательность символов. См. также главу "Сжатие данных с помощью контекстных методов моделирования ".

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

Приведенные ниже характеристики степени сжатия и скорости алгорит­мов семейств LZ77 и LZ78 относятся к типичным представителям се­мейств - LZH и LZW соответственно.

Характеристики алгоритмов семейства LZ77:

Степени сжатия: определяются данными, обычно 2-4.

Типы данных: алгоритмы универсальны, но лучше всего подходят \ для сжатия разнородных данных, например файлов ресурсов.

Симметричность по скорости: примерно 10:1; если алгоритм обес-I печивает хорошее сжатие, то декодер обычно гораздо быстрее кодера.

Характерные особенности: обычно медленно сжимают высокоизбы-| точные данные; из-за высокой скорости разжатия идеально подходят для I создания дистрибутивов программного обеспечения.

Характеристики алгоритмов семейства LZ78:

Степени сжатия: определяются данными, обычно 2-3.

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

Симметричность по скорости: примерно 3:2, декодер обычно в пол-! тора раза быстрее кодера.

цены обслуживание компьютеров

Характерные особенности: из-за относительно небольшой степени \ сжатия и невысокой скорости декодирования уступают по распростра-j ненности алгоритмам семейства LZ77.