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

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

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

Прежде всего, следует учитывать, что каждый из рассмотренных в раз­деле универсальных методов сжатия данных источников с памятью допус­кает модификации, позволяющие существенно изменить параметры ком­прессора. Так, увеличение порядка модели РРМ приводит к заметному уси­лению сжатия ценой замедления работы и увеличения расхода памяти. К аналогичному результату приводит увеличение размера словаря LZ77-Meтодов, но при этом время разжатия остается практически неизменным. Свойства компрессоров на основе BWT варьируются в меньшей степени.

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

Методы семейства LZ77 обладают наибольшей скоростью декомпрес­сии. Превышение над скоростью сжатия при использовании метода Хаффмана для кодирования результатов работы Ь277-метода - десятикратное. Меньшая разница у методов на основе BWT - в среднем скорость разжатия в 2-4 раза выше скорости сжатия. Декодирование при использовании РРМ на 5-10% медленнее кодирования. Компрессоры на базе частичных сорти­рующих преобразований малого порядка характеризуются еще большим от­ставанием разжатия - на некоторых файлах оно в несколько раз медленнее сжатия.

Похожая картина наблюдается, если сравнивать использование памяти при декодировании. В случае применения LZ77 расходы памяти минималь­ны. Архиваторы на основе РРМ наиболее требовательны - им необходимо столько же памяти, сколько и при кодировании. Следует отметить, что при сжатии требования к памяти у программ-представителей разных методов примерно близки, хотя и могут изменяться для разных типов сжимаемых данных.

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

Типичные данные качественного характера можно условно разделить на 4 типа:

1) однородные данные (например, типичные тексты);

2) однородные данные с большой избыточностью в виде длинных по­вторяющихся строк (например, набор исходных текстов);

3) неоднородные данные, в которых имеется выраженная нестабиль­ность контекстно-зависимой статистики (например, исполнимые файлы);

4) данные с малой избыточностью (например, файлы, содержащие уже сжатые блоки).

Рассмотрим, как ведут себя различные методы при сжатии данных раз­ных типов. При анализе будем ориентироваться на наилучших представите­лей методов.

Для сжатия таких однородных данных, как тексты на естественных язы­ках, наиболее подходящими являются РРМ-методы и методы на основе BWT. Первые позволяют достичь большей степени сжатия, вторые облада­ют большей скоростью декодирования. Программы, использующие методы семейства LZ77, сжимают указанные данные заметно хуже и, при увеличе­нии длины словаря, существенно медленнее.

Если в однородных данных есть длинные повторяющиеся строки, у про­грамм на основе LZ77 есть шанс себя реабилитировать. Впрочем, в этом случае наиболее выгодным будет использовать гибрид LZ77 и любого из двух его конкурентов или применять LZ77-npenpoueccHHr.

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

На данных с малой избыточностью все методы выступают не лучшим образом. Некоторое преимущество в степени сжатия имеют архиваторы на основе LZ77 и РРМ. Но последние при этом требуют значительного расхода памяти и скорость их работы заметно падает.

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