Опрос

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

Новички

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

РРМ и РРМ*

При фиксировании максимального порядка контекстов в районе 5-6 РРМ даже без наследования информации дает отличные результаты на текстах, но не очень хорошо работает на высокоизбыточных данных с большим количеством длинных повторяющихся строк. В середине 90-х гт. был предложен метод борьбы с этим недостатком [6]. Предложенный алго­ритм, РРМ* (произносится как "пи-пи-эм ста"), был основан на использова­нии контекстов неограниченной длины. Авторы алгоритма предложили следующую стратегию выбора максимального порядка на каждом шаге: максимальный порядок соответствует порядку самого короткого детерми­нированного контекста. Под детерминированным понимается контекст, в котором до данного момента встречался только один символ (любое число раз). Если детерминированных контекстов нет, то выбирается самый длин­ный среди имеющихся. После выбора максимального порядка процедура оценки вероятности символа в алгоритме РРМ* ничем не отличается от применяемой в алгоритмах обычного РРМ, т. е. РРМ-моделирования огра­ниченного порядка.

Реализация РРМ*, описанная в [6], имела невпечатляющие характеристики: сжатие на уровне РРМС порядка пяти, скорость кодирования, как утверждает­ся, также сопоставима, но памяти расходуется значительно больше. Судя по всему, авторам очень хотелось доказать превосходство их схемы над другими методами РРМ, и стандартным РРМС в частности. Читатель может самостоя­тельно сравнить степень сжатия РРМ* с другими алгоритмами РРМ, пользуясь табл. 4.8 и 4.9.

В принципе расходы памяти для РРМ и РРМ* могут быть одинаковы, что показано в [4].

Вывод. Преимущество подхода РРМ* над обычным РРМ не очевидно.