Опрос

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

Новички

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

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

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

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

Если выйти за рамки частной проблемы сжатия данных, то несомненным достоинством РРМ является возможность получения хорошей статистиче­ской модели обработанной последовательности качественных данных (или сгенерировавшего ее источника). Действительно, модель, позволяющую эф­фективно предсказывать неизвестные символы сообщения, можно приме­нять не только для сжатия, но и для решения задач коррекции текста в сис­темах OCR, распознавания речи, классификации типа текста, семантическо­го анализа текста, шифрования [18].

Недостатки реализаций подхода РРМ заключаются в следующем:

■ медленное декодирование (обычно на 5-10% медленнее кодирования);

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

■ медленная обработка малоизбыточных данных (скорость может падать в разы);

■ наилучшее сжатие различных файлов достигается при порядках модели РРМ в районе 4-12 для моделей, не применяющих технику наследования информации и/или LOE, и при порядках 16-32 в противном случае; по­этому при выборе какого-то фиксированного порядка модели мы можем терять либо в степени сжатия, либо использовать чересчур много ресур­сов ЭВМ;

■ в общем случае недостаточно хорошее сжатие файлов, статистические характеристики которых подвержены частым изменениям такого типа, что оценки распределений вероятностей в контекстных моделях быстро устаревают (так называемая нестабильность статистик контекстов); с точки зрения такой адаптации обычные алгоритмы РРМ уступают алго­ритмам типа LZ77, хотя известны способы ослабления или вообще уст­ранения этого неприятного эффекта при помощи вторичной оценки сим­вола (см. "Общий случай применения вторичной оценки символа" в под-разд. "Различные способы повышения точности предсказания");

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

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

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

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

Степени сжатия: определяются данными, для текстов обычно 3-4, ; | для объектных файлов 2-3.

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

Симметричность: близка к единице; обычно декодер немного медленнее кодера.

Характерные особенности: медленная обработка малоизбыточных данных.