Открыть сервис
Главная → Блог → PPMd

PPMd

PPMd — это алгоритм сжатия данных без потерь, основанный на методе предсказания по частичному совпадению (Prediction by Partial Matching, PPM). Алгоритм относится к классу статистических методов сжатия, которые моделируют вероятность появления следующего символа в последовательности на основе анализа контекста — уже обработанной части данных. PPMd известен высокой степенью сжатия, особенно на текстовых данных, но требует значительных вычислительных ресурсов и оперативной памяти.

История

Метод PPM был впервые предложен Джоном Клири (John Cleary) и Иэном Виттеном (Ian Witten) в 1984 году. Идея заключалась в использовании контекстного моделирования для предсказания вероятности следующего символа. В 1990-х годах алгоритм был усовершенствован, и появились его варианты, такие как PPMa, PPMb, PPMc и PPMd. Последний, PPMd, был разработан Дмитрием Шкариным (Dmitry Shkarin) в 2002 году. Шкарин оптимизировал структуру данных и алгоритм обновления контекстов, что позволило значительно увеличить скорость сжатия и распаковки, а также улучшить степень сжатия по сравнению с предшественниками. PPMd стал популярным выбором для сжатия текстов, особенно в архиваторах, таких как RAR и 7-Zip.

Принцип работы

PPMd, как и другие PPM-алгоритмы, строит контекстную модель данных. Модель представляет собой дерево контекстов, где каждый узел соответствует определённой последовательности символов (контексту). Для каждого контекста хранится статистика встречаемости следующих за ним символов. При сжатии алгоритм последовательно обрабатывает символы входного потока. Для каждого символа он ищет наиболее длинный контекст, в котором этот символ уже встречался. Если такой контекст найден, вероятность символа вычисляется на основе статистики этого контекста. Если контекст не найден, алгоритм переходит к более короткому контексту (уменьшая порядок модели) и повторяет поиск. В случае, когда символ не встречался ни в одном контексте, используется escape-символ, который сигнализирует о переходе к контексту нулевого порядка (частота символов в целом по файлу). Вероятности, полученные из модели, передаются арифметическому кодеру, который генерирует выходной битовый поток.

Арифметическое кодирование

PPMd использует арифметическое кодирование для представления последовательности символов в виде одного числа из интервала [0, 1). Это позволяет кодировать символы с дробным числом битов, что близко к теоретическому пределу энтропии. Арифметический кодер в PPMd адаптирован для работы с PPM-моделью, что обеспечивает эффективное сжатие.

Параметры и настройки

PPMd имеет несколько ключевых параметров, влияющих на его работу:

Применение

PPMd нашёл применение в различных областях, где требуется высокая степень сжатия без потерь:

Сравнение с другими алгоритмами

PPMd обычно превосходит по степени сжатия такие алгоритмы, как Deflate (используемый в ZIP, gzip), LZMA (используемый в 7-Zip) и BWT (Burrows-Wheeler Transform, используемый в bzip2), особенно на текстовых данных. Однако он уступает им по скорости сжатия и распаковки, а также по требованиям к памяти. Например, для сжатия текстового файла размером 1 МБ PPMd может потребовать до 256 МБ оперативной памяти, в то время как Deflate обходится несколькими мегабайтами. С другой стороны, PPMd может сжимать тексты на 10-20% сильнее, чем LZMA, и на 30-40% сильнее, чем Deflate.

Реализации

PPMd реализован в нескольких библиотеках и программах:

Критика

Основные недостатки PPMd связаны с его вычислительной сложностью и требованиями к памяти. Алгоритм может быть медленным на больших файлах, особенно при высоких порядках модели. Кроме того, PPMd чувствителен к типу данных: на бинарных данных (например, изображения, видео) его эффективность значительно ниже, чем на текстовых. Также алгоритм не поддерживает многопоточность в стандартных реализациях, что ограничивает его производительность на современных многоядерных процессорах.

Источники

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы