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

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

Таблица 3.4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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