PAQ

PAQ — это семейство алгоритмов сжатия данных без потерь, основанных на предсказательном моделировании и арифметическом кодировании. Разработка PAQ ведётся с 2002 года программистом Мэттом Махони (Matt Mahoney) и сообществом энтузиастов. Алгоритмы PAQ известны тем, что на момент своего появления достигали наивысшей степени сжатия среди всех доступных программ, однако ценой крайне низкой скорости работы и высоких требований к оперативной памяти. PAQ используется преимущественно в исследовательских целях, для архивирования резервных копий и в соревнованиях по сжатию данных.

История

Первая версия PAQ была выпущена Мэттом Махони в 2002 году. Махони, профессор компьютерных наук Флоридского технологического института, занимался исследованиями в области сжатия данных и машинного обучения. PAQ1 представлял собой простой контекстно-смешивающий предсказатель, который использовал арифметическое кодирование. С каждым последующим выпуском (PAQ2, PAQ3 и т. д.) алгоритм усложнялся: добавлялись новые модели, улучшались методы смешивания контекстов и оптимизировалось управление памятью.

Ключевым этапом стало появление PAQ8 в 2006 году, который ввёл поддержку сжатия изображений, исполняемых файлов и других типов данных с помощью специализированных моделей. Версия PAQ8HP (High Performance) была специально оптимизирована для достижения рекордных показателей сжатия на тестовых наборах данных, таких как Calgary Corpus и Canterbury Corpus.

В 2010-х годах развитие PAQ замедлилось, так как алгоритм достиг практических пределов сжатия для многих типов данных. Однако отдельные ответвления (форки), такие как PAQ8PX, PAQ8F и PAQ9A, продолжали совершенствоваться, добавляя поддержку новых форматов файлов (например, .zip, .7z, .exe) и улучшая обработку мультимедиа.

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

PAQ относится к классу контекстно-смешивающих предсказателей. В отличие от классических алгоритмов LZ77 (Deflate, ZIP) или BWT (bzip2), PAQ не ищет повторяющиеся строки, а пытается предсказать следующий байт данных на основе уже обработанного контекста.

Основные компоненты

1. Контекстные модели: PAQ использует множество (от нескольких десятков до тысяч) моделей, каждая из которых анализирует свой тип контекста. Например:

• n-граммы: последовательности последних 1, 2, 3, ... 16 байт.
• Контекст высокого порядка: слова, строки, битовые маски.
• Специализированные модели: для изображений (анализ пикселей), для текста (анализ слов), для исполняемых файлов (анализ инструкций процессора).
• Модели на основе расстояния: учитывают, как давно встречалась данная последовательность.

1. Смешивание контекстов (Context Mixing): Каждая модель выдаёт свою оценку вероятности появления следующего байта (например, «0» или «1»). PAQ использует нейросетевой алгоритм (обычно однослойный перцептрон с обратным распространением ошибки) для взвешивания этих предсказаний. Веса моделей динамически подстраиваются в процессе сжатия, чтобы минимизировать ошибку предсказания. Это ключевое отличие от статических методов (например, PPM), где веса фиксированы.

1. Арифметическое кодирование: Взвешенная вероятность используется арифметическим кодером для кодирования следующего бита данных. Арифметическое кодирование позволяет приблизиться к теоретическому пределу сжатия (энтропии) с произвольной точностью.

Отличие от других алгоритмов

• LZ77 (Deflate, ZIP): PAQ не использует словарь и поиск повторов. Он предсказывает вероятности, что позволяет сжимать данные, где нет прямых повторений (например, шумоподобные данные, изображения с плавными переходами).
• BWT (bzip2): PAQ не требует предварительной сортировки блоков. Он работает последовательно, что делает его крайне медленным, но потенциально более точным.
• PPM (Prediction by Partial Matching): PAQ использует смешивание сотен моделей, а не одну модель с фиксированным порядком. Это даёт лучшую адаптацию к различным типам данных.

Версии и модификации

Семейство PAQ включает несколько десятков версий, которые условно делятся на три поколения:

Производительность

Степень сжатия

PAQ стабильно занимает верхние строчки в рейтингах сжатия (например, на конкурсе Large Text Compression Benchmark (LTCB)). На текстовых данных (например, enwik8 — 100 МБ текста Википедии) PAQ8HP сжимает до 16–18 МБ, в то время как gzip (максимальная степень) — до 30–35 МБ, а bzip2 — до 25–28 МБ. На изображениях (например, тестовое изображение Lena) PAQ может сжать файл .bmp в 2–3 раза сильнее, чем PNG.

Скорость

Главный недостаток PAQ — крайне низкая скорость. Сжатие 1 МБ данных может занимать от нескольких минут до нескольких часов, в зависимости от версии и объёма используемой памяти. Распаковка обычно происходит в 2–5 раз быстрее сжатия, но всё равно остаётся медленной по сравнению с современными архиваторами. Например, PAQ8HP сжимает со скоростью около 1–5 КБ/с на процессоре 2020 года, в то время как 7-Zip (LZMA) — 5–10 МБ/с.

Потребление памяти

PAQ требует значительного объёма оперативной памяти. Минимальные версии (PAQ1) используют 4–8 МБ, но PAQ8HP может потреблять от 256 МБ до 2 ГБ и более. Для работы с большими файлами (например, 1 ГБ) может потребоваться 4–8 ГБ ОЗУ.

Применение

Из-за низкой скорости и высоких требований к ресурсам PAQ не используется в повседневном архивировании (архиваторы WinRAR, 7-Zip, ZIP). Основные области применения:

1. Научные исследования: PAQ служит эталоном для сравнения новых алгоритмов сжатия. Исследователи изучают его методы смешивания контекстов для применения в машинном обучении (например, в задачах предсказания последовательностей).
2. Сжатие резервных копий: Для архивов, которые создаются один раз и хранятся годами (например, резервные копии баз данных, научных данных), PAQ может быть оправдан, если важна максимальная экономия места при неограниченном времени сжатия.
3. Соревнования по сжатию: PAQ является основным инструментом участников конкурсов Hutter Prize (сжатие 1 ГБ текста Википедии) и Large Text Compression Benchmark. Победители этих конкурсов часто используют модификации PAQ.
4. Криптоанализ и стеганография: Методы предсказательного моделирования, используемые в PAQ, применяются для анализа случайности данных и обнаружения скрытых сообщений.

Критика и ограничения

• Непрактичность: Для большинства пользователей PAQ непригоден из-за катастрофически низкой скорости. Сжатие файла размером 100 МБ может занять несколько часов, в то время как 7-Zip справится за 10–20 секунд.
• Отсутствие поддержки: Многие версии PAQ не поддерживают многопоточность, что делает их бесполезными на современных многоядерных процессорах. Форки (PAQ8PX) частично решают эту проблему, но всё равно остаются медленными.
• Неустойчивость к ошибкам: Повреждение одного бита в архиве PAQ может сделать нечитаемым весь файл, так как арифметическое кодирование крайне чувствительно к ошибкам. В отличие от ZIP или RAR, PAQ не имеет встроенных механизмов восстановления.
• Предел сжатия: PAQ приближается к теоретической энтропии для многих типов данных, но не может сжать случайные данные (например, криптографические ключи). Для таких данных сжатие не только бесполезно, но и может увеличить размер.

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

• Мэтт Махони, создатель PAQ, также является автором тестового набора данных Large Text Compression Benchmark (LTCB), который используется для оценки алгоритмов сжатия.
• В 2006 году PAQ8HP выиграл приз в размере 50 000 долларов на конкурсе Hutter Prize, сжав 100 МБ текста Википедии до 16,4 МБ.
• Алгоритм PAQ лёг в основу некоторых коммерческих продуктов, например, архиватора WinRK (частично использовал методы PAQ).
• Исходный код PAQ распространяется под лицензией GPL, что способствовало появлению множества форков и модификаций.

Источники

1. Mahoney, M. (2002). The PAQ1 Data Compression Program. Florida Institute of Technology.
2. Mahoney, M. (2005). Adaptive Weighing of Context Models for Lossless Data Compression. Florida Institute of Technology.
3. Документация к PAQ8PX (версия 8.0 и выше).
4. Результаты Large Text Compression Benchmark (LTCB) — официальный сайт Мэтта Махони.
5. Статья «Context Mixing» в журнале Dr. Dobb's Journal (2006).