ZPAQ

ZPAQ — это свободная программа для сжатия данных без потерь, разработанная Мэттом Махони (Matt Mahoney) и распространяемая под лицензией GPL. ZPAQ реализует собственный алгоритм сжатия, основанный на контекстном моделировании и предсказании, и отличается высокой степенью сжатия, особенно на текстовых и структурированных данных, при относительно низкой скорости работы. Программа поддерживает сжатие в архивный формат с собственным расширением .zpaq, а также может работать в режиме сжатия отдельных файлов.

История

Первая версия ZPAQ была выпущена Мэттом Махони в 2009 году. Махони, известный своими работами в области сжатия данных (в частности, он является автором алгоритма PAQ и участником конкурсов по сжатию), создал ZPAQ как экспериментальную платформу для тестирования новых методов контекстного моделирования и предсказания. В отличие от PAQ, который был ориентирован на максимальное сжатие при любых затратах времени, ZPAQ изначально проектировался как более практичный инструмент, способный работать с большими объёмами данных и поддерживать многопоточность. В 2010 году была выпущена версия 1.00, которая стала первой стабильной. С тех пор ZPAQ развивается как открытый проект, с периодическими обновлениями, улучшающими производительность и добавляющими новые возможности, такие как сжатие с использованием словарей и поддержка шифрования.

Алгоритм сжатия

ZPAQ использует метод сжатия, основанный на контекстном моделировании (context modeling) и арифметическом кодировании. В отличие от популярных алгоритмов, таких как LZ77 (используемый в ZIP, GZIP) или LZMA (7-Zip), ZPAQ не полагается на поиск повторяющихся строк, а строит вероятностную модель данных, предсказывая вероятность появления каждого следующего байта на основе предыдущих. Этот подход позволяет достигать очень высокой степени сжатия, особенно на данных с высокой избыточностью, таких как тексты, базы данных, исполняемые файлы и архивы.

Контекстное моделирование

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

• N-граммы (последовательности из N байтов) — для учета локальных закономерностей.
• Контексты на основе порядка — учитывают позицию байта в строке или файле.
• Смешанные контексты — комбинации различных типов контекстов, например, порядок байтов в слове и порядок слов в предложении.

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

Для каждого контекста ZPAQ хранит статистику (частоту появления символов). На основе этой статистики вычисляется вероятность для каждого возможного значения следующего байта. Затем эти вероятности передаются в арифметический кодер, который кодирует данные с использованием дробной длины, что позволяет достигать сжатия, близкого к теоретическому пределу (энтропии). Арифметическое кодирование в ZPAQ реализовано с использованием алгоритма рангового арифметического кодирования (range arithmetic coding), который обеспечивает высокую точность и скорость.

Многопоточность и оптимизация

ZPAQ поддерживает многопоточное сжатие и распаковку. При сжатии файл разбивается на блоки, каждый из которых обрабатывается отдельным потоком. Это позволяет эффективно использовать многоядерные процессоры. Однако из-за сложности моделирования и необходимости обработки большого количества контекстов, ZPAQ значительно медленнее, чем LZ77-подобные алгоритмы, особенно на этапе сжатия.

Формат архива

ZPAQ использует собственный формат архива с расширением .zpaq. Архив представляет собой последовательность блоков (blocks), каждый из которых содержит:

• Заголовок — метаданные о блоке (размер, тип сжатия, контрольная сумма).
• Сжатые данные — результат работы арифметического кодера.
• Информация о модели — описание использованных контекстов и статистик, необходимое для распаковки.

Формат является самодостаточным — для распаковки не требуется внешняя информация о модели, так как все параметры хранятся внутри архива. Это позволяет распаковывать архивы, созданные разными версиями ZPAQ, при условии, что алгоритм моделирования совместим. Формат поддерживает несколько режимов сжатия, включая:

• Сжатие с максимальной степенью (режим -m или --max) — использует все доступные контексты и максимальное количество итераций.
• Сжатие с балансом скорости и степени (режим -s или --standard) — стандартный режим, рекомендуемый для большинства задач.
• Сжатие с минимальным временем (режим -f или --fast) — использует упрощённые модели, что снижает степень сжатия, но ускоряет работу.

Применение

ZPAQ находит применение в областях, где требуется максимальное сжатие данных без потерь, и где время сжатия не является критическим фактором. Основные сценарии использования:

• Архивирование больших объёмов текстовых данных — научные публикации, базы данных, исходные коды программ.
• Сжатие резервных копий — особенно для данных, которые редко изменяются, но требуют минимального объёма хранения.
• Сжатие в исследовательских целях — для тестирования новых алгоритмов сжатия и сравнения их с другими методами.
• Сжатие встроенных систем — в некоторых случаях, когда доступ к ресурсам ограничен, ZPAQ может использоваться для сжатия прошивок или конфигурационных файлов.

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

ZPAQ обычно показывает более высокую степень сжатия, чем популярные архиваторы, такие как 7-Zip (с алгоритмом LZMA) или WinRAR (с алгоритмом RAR). Однако это достигается за счёт значительно более низкой скорости работы. Например, при сжатии текстового файла размером 100 МБ, ZPAQ может сжать его до 10-15 МБ, в то время как 7-Zip — до 15-20 МБ, но ZPAQ будет работать в 10-20 раз дольше. На бинарных файлах (изображения, видео) разница в степени сжатия менее заметна, так как они уже сжаты с помощью специализированных кодеков.

Критика

Основные недостатки ZPAQ:

• Низкая скорость сжатия — особенно на больших файлах, время сжатия может измеряться часами.
• Высокое потребление оперативной памяти — для хранения контекстов и статистик может требоваться несколько гигабайт RAM.
• Отсутствие поддержки некоторых популярных функций — например, шифрования (хотя в некоторых версиях есть экспериментальная поддержка) или разбиения на тома.
• Меньшая распространённость — по сравнению с ZIP, RAR или 7z, формат ZPAQ менее известен, что может затруднить обмен архивами.

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

• ZPAQ является одним из немногих архиваторов, который способен сжимать данные до уровня, близкого к теоретическому пределу, установленному энтропией Шеннона.
• Алгоритм ZPAQ используется в некоторых научных проектах, связанных с обработкой больших данных и биоинформатикой.
• Исходный код ZPAQ написан на C++ и доступен для свободного скачивания и модификации.

Источники

• Matt Mahoney. «The PAQ and ZPAQ Compression Algorithms». 2010.
• Документация к программе ZPAQ (README, man-страницы).
• Статья «ZPAQ: A New Compression Algorithm» на сайте Dr. Dobb's Journal (2010).
• Сравнительный анализ архиваторов на сайте «Maximum Compression».