libppmd

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

История

Алгоритмы семейства PPM были разработаны в 1980-х годах как развитие идей энтропийного кодирования и контекстного моделирования. В 1990-х годах Дмитрий Шкарин создал одну из наиболее эффективных реализаций — PPMd, которая легла в основу многих архиваторов, включая RAR и 7-Zip. Библиотека libppmd была выделена из исходного кода архиватора RAR (разработчик — компания Eugene Roshal) для использования в сторонних проектах. Она представляет собой стабильную, независимую реализацию алгоритма PPMd, оптимизированную для встраивания в различное программное обеспечение.

Первые версии libppmd появились в начале 2000-х годов. Библиотека распространяется под лицензией, совместимой с GNU LGPL, что позволяет использовать её как в открытых, так и в коммерческих проектах. Впоследствии libppmd была включена в состав многих открытых проектов, таких как файловый менеджер Far Manager, а также в библиотеки сжатия, используемые в операционных системах семейства Linux.

Алгоритм работы

Основы PPM-моделирования

Алгоритм PPM основан на предсказании следующего символа в последовательности на основе контекста — фиксированного числа предыдущих символов (порядка модели). Модель хранит статистику встречаемости символов для каждого возможного контекста. При сжатии алгоритм выбирает наиболее вероятный символ и кодирует его с помощью арифметического кодирования. Если символ не встречался в данном контексте, происходит переход к контексту меньшего порядка (механизм «escape»). В случае, когда символ не найден ни в одном контексте, используется контекст нулевого порядка, где все символы считаются равновероятными.

Особенности реализации PPMd

Реализация PPMd, используемая в libppmd, включает несколько ключевых оптимизаций:

• Адаптивное обновление модели: после кодирования каждого символа статистика модели обновляется, что позволяет адаптироваться к изменяющимся характеристикам данных.
• Управление памятью: библиотека использует динамическое выделение памяти для хранения контекстной модели, что позволяет обрабатывать данные произвольного размера без фиксированных ограничений.
• Оптимизация escape-механизма: применяется метод «метод PPMd» (вариант PPM с методом escape, основанным на оценке вероятности появления новых символов), что повышает точность предсказания.

Параметры сжатия

libppmd позволяет задавать несколько параметров, влияющих на эффективность и скорость сжатия:

• Порядок модели (Order): от 2 до 16 (обычно 6-8 для текстов). Более высокий порядок увеличивает степень сжатия, но требует больше памяти и времени.
• Размер памяти (Memory): от 1 МБ до 256 МБ. Больший объём памяти позволяет хранить более детальную модель, что улучшает сжатие на больших объёмах данных.
• Режим сжатия: может быть выбран один из нескольких режимов, оптимизированных для разных типов данных (текст, исполняемые файлы, изображения).

Применение

В архиваторах

Основное применение libppmd — в составе архиваторов, где она используется как один из методов сжатия. Наиболее известные программы, использующие libppmd:

• RAR (разработчик — Eugene Roshal) — использует PPMd как один из алгоритмов сжатия для текстовых и слабоструктурированных данных.
• 7-Zip (разработчик — Игорь Павлов) — поддерживает PPMd через реализацию libppmd, доступную в составе пакета LZMA SDK.
• WinRAR (разработчик — компания Eugene Roshal) — включает PPMd как опциональный метод сжатия для пользовательских профилей.

В программном обеспечении для обработки данных

Библиотека используется в проектах, требующих эффективного сжатия текстовой информации:

• Файловые менеджеры (Far Manager, Total Commander) — для сжатия и распаковки архивов.
• Системы резервного копирования — для уменьшения объёма хранимых данных.
• Научные и инженерные приложения — для сжатия больших текстовых массивов (логи, дампы, результаты моделирования).

В операционных системах

libppmd входит в состав многих дистрибутивов Linux как часть пакетов, обеспечивающих поддержку архивов RAR и 7-Zip. В Windows библиотека может быть включена в состав сторонних утилит или использоваться через интерфейс DLL.

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

Преимущества

• Высокая степень сжатия текстовых данных: на типичных текстовых файлах (например, HTML, XML, исходные коды) PPMd часто превосходит алгоритмы LZ77 (Deflate, LZMA) на 10-30% по степени сжатия.
• Адаптивность: алгоритм быстро подстраивается под структуру данных, что позволяет эффективно сжимать смешанные потоки.
• Открытость реализации: libppmd распространяется с открытым исходным кодом, что позволяет использовать её в любых проектах без лицензионных ограничений.

Недостатки

• Высокое потребление памяти: для достижения высокой степени сжатия требуется значительный объём оперативной памяти (до 256 МБ и более).
• Низкая скорость сжатия: по сравнению с алгоритмами LZ77, PPMd работает медленнее, особенно на больших файлах.
• Чувствительность к типу данных: на бинарных данных (исполняемые файлы, мультимедиа) эффективность PPMd значительно ниже, чем у специализированных алгоритмов (например, LZMA или BWT).

Технические детали

Интерфейс библиотеки

libppmd предоставляет простой API на языке C, включающий функции:

• PPMd_Compress() — сжатие блока данных.
• PPMd_Decompress() — распаковка блока данных.
• PPMd_Init() — инициализация модели с заданными параметрами.
• PPMd_Free() — освобождение выделенной памяти.

Данные передаются в виде буферов, что позволяет использовать библиотеку в потоковых приложениях.

Формат сжатых данных

libppmd не определяет собственный формат архива. Она используется как часть более крупных систем, где сжатые данные упаковываются в контейнеры (например, RAR, 7z). Внутри контейнера данные могут быть разделены на блоки, каждый из которых сжимается независимо, что позволяет реализовать произвольный доступ к частям архива.

Интересные факты

• Алгоритм PPMd был разработан Дмитрием Шкариным в 1998 году и первоначально использовался в архиваторе RAR версии 2.0.
• libppmd является одной из немногих библиотек, реализующих PPM-сжатие на языке C с открытым исходным кодом.
• В тестах на сжатие текстовых файлов (например, корпус Calgary Corpus) PPMd показывает результаты, сопоставимые с современными нейросетевыми методами сжатия, но при значительно меньших вычислительных затратах.
• Библиотека используется в проекте «libarchive» — популярной кроссплатформенной библиотеке для работы с архивами.

Источники

• Документация к библиотеке libppmd (исходный код, файл README).
• Описание алгоритма PPMd в книге: Salomon D. Data Compression: The Complete Reference. — Springer, 2007.
• Исходный код архиватора RAR (версия 2.0 и выше) — комментарии к реализации PPMd.
• Техническая документация к LZMA SDK (раздел о методах сжатия).
• Статья «PPM Compression» на сайте «Data Compression Reference».