LZ77

Выбор метода сжатия

В заключение разд. скажем несколько слов о процедуре выбора метода сжатия.

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

Прежде всего, следует учитывать, ...

Препроцессинг нетекстовых данных

Было замечено, что многие файлы содержат данные, записанные не в самом удобном виде для сжатия традиционными универсальными компрессорами. И если изменить форму представления этих данных, то эффективность сжатия файлов заметно увеличится. Многие компрессоры уже оснащены препроцессо­рами регулярных структур и исполнимых файлов. Среди них можно отметить 7-Zip, АСЕ, CABARC, DC, IMP, PPMN, SBC, UHARC, YBS.

Преобразование относительных адресов

Как известно, в системе команд процессоров Intel адреса меток в ряде случаев записываются в виде смещения от адреса текущей ...

Препроцессинг текстов

В последние несколько лет приобрели популярность и были существен­но развиты методы предварительной обработки текстовой информации. В настоящее время специализированный препроцессинг текстов, позво­ляющий заметно улучшить сжатие, используется в таких архиваторах, как ARHANGEL, JAR, RK, SBC, UHARC, в компрессорах DC, PPMN.

Использование словарей

Идея преобразования данных с помощью словаря заключается в замене каких-то строк текста на коды фраз словаря, соответствующих этим стро­кам. Часто указывается просто номер фразы в словаре. Пожалуй, метод сло­варной замены ...

Достоинства и недостатки РРМ

Вот уже в течение полутора десятков лет представители семейства РРМ остаются наиболее мощными практическими алгоритмами с точки зрения степени сжатия. По-видимому, добиться лучших результатов смогут только более изощренные контекстные (в широком смысле) методы, которые, не­сомненно, будут появляться, так как производятся все более быстрые про­цессоры, а объем оперативной памяти ЭВМ становится все больше.

Наилучшие результаты алгоритмы РРМ показывают на текстах: отлич­ный коэффициент сжатия при высокой скорости, чему наглядным примером являются компрессоры PPMd и PPMonstr. Кроме ...

Недостатки

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

Вопросы для самоконтроля

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

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

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

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

LZSS

Эта версия LZ77 была разработана Сторером (Storer) и Сжимански (Szymanski) в 1982 [Storer 82]. Базовый алгоритм был улучшен по трем направлениям: (1) упреждающий буфер сохранялся в циклической очереди, (2) буфер поиска (словарь) хранился в виде дерева двоичного поиска и (3) метки имели два поля, а не три.

Двоичное дерево поиска - это двоичное дерево, в котором левое поддерево каждого узла А содержит узлы, меньшие чем Л, а узлы правого поддерева все больше А Поскольку узлы нашего двоичного дерева состоят из строк (или слов), прежде всего необходимо определиться, как эти ...

Пути улучшения сжатия для методов LZ

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

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

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

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

LZ77 (скользящее окно)

Основная идея этого метода (его еще часто называют методом LZ1, см. [Ziv 77]) состоит в использовании ранее прочитанной части входного файла в качестве словаря. Кодер создает окно для входного файла и двигает его справа налево в виде строки символов, требующих сжатие. Таким образом, метод основан на скользящем окне. Окно разбивается на две части. Часть слева называется буфером поиска. Она будет служить текущим словарем, и в ней всегда содержатся символы, которые недавно поступили и были закодированы. Правая часть окна называется упреждающим буфером, содержащим ...

Формат Deflate

Формат словарного сжатия Deflate, предложенный Кацем (Katz), исполь­зуется популярным архиватором PKZIP [3]. Сжатие осуществляется с по­мощью алгоритма типа LZH, иначе говоря, указатели и литералы кодируют­ся по методу Хаффмана. Формат специфицирует только работу декодера, т. е. определяет алгоритм декодирования, и не налагает серьезных ограни чений на реализацию кодера. В принципе в качестве алгоритма сжатия мо­жет применяться любой работающий со скользящим окном, лишь бы он ис­ходил из стандартной процедуры обновления словаря для алгоритмов се­мейства LZ77 и использовал задаваемые ...