Опрос

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

Новички

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

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

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

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

Прежде всего, следует учитывать, что каждый из рассмотренных в раз­деле универсальных методов сжатия данных источников с памятью допус­кает модификации, позволяющие существенно изменить параметры ком­прессора. Так, увеличение порядка модели РРМ приводит к заметному уси­лению сжатия ценой замедления работы и увеличения расхода памяти. К аналогичному результату приводит увеличение размера словаря 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 и РРМ. Но последние при этом требуют значительного расхода памяти и скорость их работы заметно падает.

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

Параметр

Метод

Однородные

данные

(типичный

текст)

Однородные дан­ные с большой из­быточностью (ис­ходные тексты про­грамм)

Неодно­родные данные

Дан­ные с малой избы­точно­стью

Степень сжатия

РРМ

Высокая

Высокая

Высокая

Невы­сокая

BWT

Близкая к РРМ

Близкая к РРМ

Без фраг-ментиро-вания -

худшая

м

LZ77

Заметно худ­шая

При большом ко­личестве длинных повторов довольно высокая

Близкая к РРМ

м

Параметр

Метод

Однородные данные (ти­пичный текст)

Однородные дан­ные с большой из­быточностью (ис­ходные тексты про­грамм)

Неодно­родные данные

Дан­ные с малой избы­точно­стью.

Скорость кодиро­вания

BWT

Высокая

Средняя

Высокая

Высо­кая

РРМ

При большом порядке мо­дели - самая низкая; при небольшом -немного бы­стрее BWT

Если не использо­вать сложное мо­делирование - вы­сокая

Средняя

Низкая

LZ77

Средняя, а при малом словаре - са­мая высокая

Средняя, при ма­лом словаре - вы­сокая

Высокая

Высо­кая

Скорость декодиро­вания

LZ77

Примерно в 10 раз выше скорости кодирования; разница еще больше на избыточных данных

РРМ

Обычно на 5-10% медленнее кодирования

BWT

В 2-4 раза выше скорости кодирования

Требуе­мый объ­ем памяти при сжа­тии

BWT

Постоянный при сжатии данных любого типа

РРМ

Варьируется в широких пределах, в зависимости от слож­ности моделирования и порядка модели; вырастает для очень неоднородных данных; в зависимости от структуры хранения контекстной информации может увеличиваться для малоизбыточных данных

LZ77

Пропорционален размеру словаря

Тре­буемый объем памяти при разжатии

LZ77

Минимальный

РРМ

Максимальный; если процесс моделирования симметри­чен, то примерно равен расходу памяти при сжатии

BWT

Средний