Просмотр кода страницы PAQ

{{плохой перевод|дата=2019-09-04|en|PAQ}}
[[Файл:Paq8o Sample Session.png|альт=PAQ8O|граница|мини|500px|Пример сеанса работы с PAQ8O]]
'''PAQ''' — это семейство [[Сжатие без потерь|алгоритмов сжатия данных]] с [[Текстовый интерфейс пользователя|текстовым интерфейсом]], которые завоевали популярность благодаря своим выдающимся результатам в тестах сжатия, несмотря на высокие требования к [[Ресурс|вычислительным ресурсам]].

Наивысшие оценки среди алгоритмов PAQ получает PAQ8JD, созданный группой исследователей, включая Мэтта Махони, Александра Ратушняка, Сергея Оснача, Пшемыслава Скибиньского и Билла Петтиса. Этот алгоритм был выпущен 30 декабря 2006 года. Однако в некоторых тестах PAQ8JD уступает алгоритму WinRK, разработанному Малькомом Тейлором в январе 2005 года в режиме PWCM. PWCM представляет собой стороннюю коммерческую реализацию алгоритма PAQ.

Специальные версии алгоритма PAQ, оптимизированные для конкретных задач, были отмечены наградами на конкурсах «[https://mailcom.com/challenge/ Приз Хаттера]» и «[http://prize.hutter1.net/ Калгари Корпус Челлендж]».

== Алгоритм ==
В основе алгоритма лежит идея '''контекстного моделирования'''. Контекст — это, говоря доступным языком, история появления символа, то есть информация о символах, предшествующих текущему в сжимаемом потоке. При этом процесс компрессии разбивается на две фазы: моделирование и [[Энтропийное кодирование|кодирование]]. PAQ использует алгоритм ''смешивания контекстов''. Смешивание контекстов ({{iw|Context mixing}}) — это техника, тесно связанная с алгоритмом [[Алгоритм сжатия PPM|PPM]], но отличие состоит в том, что [[вероятность]] появления следующего символа вычисляется на основе взвешенной комбинации большого числа моделей, зависящих от разных контекстов, '''не обязательно''' следующих друг за другом.
В PAQ-семействе для сбора [[Статистика|статистики]] и предсказания вероятности следующего символа используются в основном следующие модели:

* n-граммы — контекст; предыдущие n байт (как в PPM).
* словарные n-граммы, игнорирующие регистр и не алфавитные символы (полезны в текстовых данных).
* «разрежённые» контексты, например, второй и четвёртый символы перед кодируемым (полезны в некоторых бинарных [[Формат файла|форматах]]).
* «аналоговые» контексты, состоящие из верхней половины двоичного представления 8- или 16-битных [[Машинное слово|слов]] (полезны в мультимедийных форматах данных).
* двумерные контексты (полезны для изображений, табличных данных). Длина ряда определяется шагом повторяющихся байтовых [[паттерн]]ов.
* специализированные модели, такие, как [[x86]]-[[Исполняемый файл|исполняемые файлы]] или [[Windows Bitmap]], [[TIFF]], [[JPEG]] - изображения. Эти модели активируются только тогда, когда определен файл конкретного типа.

Все версии PAQ предсказывают и сжимают за раз один [[бит]], но различаются в деталях реализации того, как предсказания комбинируются и обрабатываются после. Как только по предсказаниям была определена вероятность появления следующего бита, бит сжимается [[арифметическое кодирование|арифметическим кодировщиком]]. Существует три способа для комбинирования предсказаний моделей в зависимости от версии PAQ.

* от PAQ1 до PAQ3 каждое предсказание представлено парой битовых счётчиков <math>(n_0,n_1)</math>. Эти счётчики комбинировались взвешенным суммированием, таким, что больший вес определяется более длинным контекстом.
* в PAQ4 до PAQ6 предсказания комбинировались, как и в первом случае, но веса, принадлежащие каждой модели, назначались так, чтобы более точные модели получали преимущество.
* в PAQ7 и более поздних версиях выход каждой модели есть вероятность <math>[0;4095]</math>, в отличие от пары счётчиков, вероятности суммируются при помощи [[Искусственная нейронная сеть|искусственных нейронных сетей]].

PAQ1SSE и позднейшие версии использовали постобработку предсказания методом вторичной оценки символа ({{lang-en2|SSE}} — {{lang-en2|Secondary Symbol Estimation}}), то есть комбинированное предсказание и небольшой контекст использовались для выбора следующего предсказания по таблице. После того, как символ был закодирован, данные в таблице корректировались для уменьшения ошибки предсказания. Вторичная оценка символа может быть объединена в один процесс с разными контекстами либо может выполняться параллельно, усредняясь с выходами моделей.

=== Арифметическое кодирование ===
Строка ''s'' сжимается в байтовую строку, представляющую число ''x'' в 256-значной системе исчисления [[порядок байтов|big endian]] в интервале [0;1), такое, что P(r < s) ≤ x < P(r ≤ s), где P(r < s) — вероятность, что случайная [[Строковый тип|строка]] ''r'' такой же длины, как ''s'', [[лексикографический порядок|лексикографически]] меньше, чем ''s''. Всегда возможно найти такую строку ''x'', что длина её хотя бы на один байт превосходит лимит [[Шеннон, Клод Элвуд|Шеннона]]: -log<sub>2</sub> P(r = s) бит. Длина ''s'' сохраняется в заголовке архива.

Арифметический кодировщик в PAQ реализован путём хранения верхней и нижней границ ''x'' для каждого шага предсказания, начально [0;1]. После каждого предсказания текущий интервал делится пропорционально вероятностям того, что следующий бит будет 0 и следующий бит будет 1, на основании предыдущих битов ''s''. Следующий бит кодируется, выбирая соответствующий подынтервал как новый интервал.

Число ''x'' декомпрессируется в строку ''s'' идентичной серией битовых предсказаний (так как предыдущие биты ''s'' известны). Интервал делится как при сжатии. Часть, содержащая ''x'', становится новым интервалом, и соответствующий бит добавляется к ''s''.

В PAQ верхняя и нижняя границы интервала представляются тремя частями. Наиболее значимые разряды по [[система счисления|основанию]] 256 идентичны, так они могут быть записаны как старшие байты ''x''. Следующие 4 байта хранятся в памяти так, что старший байт различается. Младшие биты все подразумеваются нулями для нижней границы и все - единицами для верхней границы. Кодирование завершается записью ещё одного байта из нижней границы.

=== Адаптивное взвешивание моделей ===
В PAQ версиях до PAQ6 каждая модель отображала множество различных контекстов на пару счётчиков: <math>n_0</math> — количество нулевых битов и <math>n_1</math> — количество единичных битов. Для увеличения значимости более поздней истории битов счётчик уменьшался почти вдвое, когда противоположный бит встречался. Например, текущее состояние модели, ассоциированное с контекстом <math>(n_0,n_1) = (12,3)</math> и бит 1 наблюдается на входе — счётчик обновляется до состояния (7,4).

Бит сжимается арифметическим кодировщиком соответственно его вероятности либо P(1), либо P(0)=1-P(1). Вероятности вычисляются взвешенным суммированием счётчиков нулей и единиц:

* <math>S_0 = \Sigma_1 w_i n_{0i}</math>
* <math>S_1 = \Sigma_1 w_i n_{1i}</math>
* <math>S = S_0 + S_1</math>
* <math>P(0) = \frac{S_0}{S}</math>
* <math>P(1) = \frac{S_1}{S}</math>,

где <math>w_i</math> вес i-той модели. До PAQ3 веса были фиксированными и устанавливались в случайном порядке (контексты порядка ''n'' имели вес n²). Начиная с PAQ4 веса выбирались адаптивно в направлении уменьшения ошибки предсказания в одинаковых наборах контекстов. Если требуется закодировать бит ''y'', то веса назначаются следующим образом:

* n<sub>i</sub> = n<sub>0i</sub> + n<sub>1i</sub>
* ошибка = y − P(1)
* <math>w_i \gets w_i + \frac{S\,n_{1i} - S_1 n_i}{S_0 S_1}</math> ошибка

=== Нейронные сети для смешивания ===
Начиная с PAQ7 выходом каждой модели является предсказание (вместо пары счётчиков). Предсказания усредняются в логистическом домене по формуле:

* x<sub>i</sub> = сжать(P<sub>i</sub>(1))
* P(1) = размыть(Σ<sub>i</sub> w<sub>i</sub> x<sub>i</sub>),

где P(1) — вероятность того, что следующий бит будет единицей, а P<sub>i</sub>(1) — вероятность, оцененная ''i''-й моделью и

* сжать(x) = ln(x / (1 — x))
* размыть(x) = 1 / (1 + e<sup>-x</sup>) (операция, обратная операции «сжать»).

После каждого предсказания модель обновляется выравниванием весов для уменьшения цены сжатия.

* w<sub>i</sub> ← η x<sub>i</sub> (y — P(1)),

где η — коэффициент обучения (обычно от 0,002 до 0,01), ''y'' — предсказанный бит и (y — P(1)) — ошибка предсказания. Алгоритм обновления весов отличается от привычного в нейронных сетях обучающего [[Метод обратного распространения ошибки|метода обратного распространения ошибки]] в том, что произведение P(0)P(1) не учитывается, потому что цель нейронной сети — минимизация стоимости кодирования, а не [[Стандартное отклонение|среднеквадратичной ошибки]].

Большинство версий PAQ используют небольшой контекст при выборе набора весов для нейронной сети. Некоторые версии используют двух и трёх-шаговые предсказатели, состоящие из соответственно двух или трёх множеств нейронных сетей, выход каждой предыдущей является входом для следующего [[Множество|множества]] сетей, [[Мощность множества|мощность]] которого меньше, и затем следует '''вторичная оценка символа'''. Более того, для каждого входящего предсказания может быть несколько входов, являющихся [[линейная функция|нелинейными функциями]] P<sub>i</sub>(1) в дополнение к ''сжать(P(1))''.

=== Контекстное моделирование ===
Каждая модель разделяет входящий поток бит ''s'' на множество контекстов и отображает каждый контекст на состояние истории битов, представленное 8 битами. В версиях до PAQ6 состояние было представлено парой счётчиков ''(n<sub>0</sub>, n<sub>1</sub>)''. В PAQ7 и более поздних состояние содержало при определённых условиях также последний бит или целую последовательность. Значения состояний отображаются в вероятности, используя 256-значную таблицу. После табличного предсказания значение в таблице немного выравнивалось (обычно до 0,4 %) для уменьшения [[Погрешность|погрешности]] предсказания.

Во всех PAQ8-версиях состояния истории битов содержат следующую информацию:

* Точная последовательность до 4 битов.
* Пара счётчиков и индикатор для последнего бита для последовательностей от 5 до 15 бит.
* Пара счётчиков для последовательностей от 16 до 41 бита.

Чтобы сохранить количество состояний равным 256, следующие ограничения были наложены на счётчики: (41, 0), (40, 1), (12, 2), (5, 3), (4, 4), (3, 5), (2, 12), (1, 40), (0, 41). Если счётчик превышает лимит, следующее состояние выбирается с подобным [[соотношение]]м n<sub>0</sub> / n<sub>1</sub>. Таким образом, если текущее состояние (n<sub>0</sub> = 4, n<sub>1</sub> = 4, последний бит = 0) и 1 получена на входе, тогда новое состояние не (n<sub>0</sub> = 4, n<sub>1</sub> = 5, последний бит = 1), а (n<sub>0</sub> = 3, n<sub>1</sub> = 4, последний бит = 1).

Большинство контекстных моделей реализованы как [[Хеш-таблица|хеш-таблицы]]. Некоторые небольшие контексты реализованы как [[Индексный массив|индексные массивы]].

=== Предварительная обработка текста ===
Некоторые версии PAQ, в особенности PAsQDAa, PAQAR (обе произошли от PAQ6), и от PAQ8HP1 до PAQ8HP8 (потомки PAQ8 и одержавшие верх в [[Приз Хаттера|Призе Хаттера]][http://prize.hutter1.net]) обрабатывают текст, просматривая его и заменяя слова из текста, содержащиеся во внешнем словаре, одно- и трёхбайтными кодами. Дополнительно слова в верхнем регистре кодируются специальным символом и переводом слова в нижний регистр. В PAQ8HP-серии словарь организован группировкой [[синтаксис|синтаксически]] и [[семантика|семантически]] похожих слов вместе. Это позволяет использовать модели, которые используют только верхние биты словарных кодов в качестве контекстов.

== История ==
Далее представлен список наиболее значимых изменений к алгоритму PAQ. В дополнение более мелкие множественные улучшения опущены.

* '''PAQ1''' был выпущен [[6 января]] [[2002 год]]а Мэттом Махони. Он использовал фиксированные веса и не включал разрежённые и аналоговые модели. Всего использовалось 5 моделей<ref>[http://compression.ru/download/articles/cm/shelwien_2002_paq1b.txt PAQ1: Описание модели] {{Wayback|url=http://compression.ru/download/articles/cm/shelwien_2002_paq1b.txt |date=20161027084931 }}, 2002, Matt Mahoney, v1.02</ref>.
* '''PAQ1SSE/PAQ2''' был выпущен [[11 мая]] [[2003 год]]а Сергеем Осначем. Он значительно улучшил сжатие добавлением ''Вторичной оценки символа'' между предсказателем и кодировщиком. ''Вторичная оценка символа'' подавала на вход небольшой контекст и текущее предсказание, и на выходе получалось новое предсказание из таблицы. Табличное значение затем обновлялось для отражения текущего бита.
* '''PAQ3N''' был выпущен [[9 октября]] [[2003]]. Была добавлена разрежённая модель.
* '''PAQ4''', выпущенный [[15 ноября]] [[2003]] Мэттом Махони, использовал адаптивное взвешивание. '''PAQ5''' ([[18 декабря]] 2003) и '''PAQ6''' ([[30 декабря]] 2003) были незначительными улучшениями, включающими аналоговую модель. К этому времени PAQ конкурировал с лучшими PPM-компрессорами и привлёк внимание сообщества людей, занимающихся сжатием данных, что привело к многочисленным улучшениям до [[Апрель|апреля]] [[2004 год]]а. Берто Дестасио доводил модели и поправил последовательность обхода счётчиков. Йохан де Бок (Johan de Bock) внёс улучшения в [[интерфейс командной строки|интерфейс пользователя]]. Дэвид А. Скотт улучшил арифметический кодер. Фабио Буффони ускорил программу.
* В период с [[20 мая]] [[2004]] по [[27 июля]] [[2004]] Александр Ратушняк выпустил семь версий архиватора '''PAQAR''', в котором степень сжатия была значительно повышена путём добавления многих новых моделей, многочисленных миксеров с выбором весов по контексту, добавлением ''Вторичной оценки символа'' на выход каждого миксера и, наконец, добавлением предварительной обработки исполняемых файлов архитектуры процессоров [[Intel]]. '''PAQAR''' оставался на вершине программ сжатия данных без потерь до конца 2004 года, но был гораздо медленнее своих предшественников.
* С [[18 января]] по [[7 февраля]] [[2005 год]]а Пшемыслав Скибиньский выпустил четыре версии '''PAsQDa''', базировавшиеся на '''PAQ6''' и '''PAQAR''' и дополненные английским словарным препроцессором. Он достиг наилучшего результата на Калгари Корпусе, но не на большинстве других тестов.
* Модифицированная Мэттом Махони версия '''PAQ6''' взяла приз на [http://mailcom.com/challenge Калгари Корпус Челлендж] [[10 января]] [[2004]]. Это достижение было перекрыто десятью последовательными версиями '''PAQAR''' Александра Ратушняка. Наиболее поздняя увидела свет [[5 июня]] [[2006 год]]а, она состояла из сжатых вместе данных и текста программы и занимала 589 862 байта.
* '''PAQ7''' был выпущен в [[Декабрь|декабре]] [[2005 год]]а Мэттом Махони. '''PAQ7''' — это полностью переписанный '''PAQ6''' и его варианты ('''PAQAR''', '''PAsQDa'''). Степень сжатия была схожа с '''PAQAR''', но время выполнения — в 3 раза меньше. Но ему не хватало x86 и словаря, поэтому он был не так хорош для сжатия исполняемых модулей [[Microsoft Windows]] и английских текстов, как '''PAsQDa'''. Хотя он включал модели для цветных [[BMP]], [[TIFF]] и [[JPEG]]-файлов, поэтому сжимал их лучше. Главное отличие '''PAQ7''' было в том, что он использовал нейронную сеть для комбинирования моделей, в отличие от уменьшающего градиент миксера. Другой чертой '''PAQ7''' была возможность сжимать встроенные в файлы [[Excel]], [[Word]] и [[Portable Document Format|PDF]] изображения Bitmap и JPEG.
* '''PAQ8A''' был выпущен [[27 января]] [[2006]] и '''PAQ8C''' [[13 февраля]]. Это был экспериментальный предвыпуск ожидавшегося PAQ8. Он исправлял некоторые компромиссные решения в PAQ7, в частности, слабое сжатие в некоторых случаях. PAQ8A также включал в себя модели для x86-исполняемых файлов.
* '''PAQ8F''' был выпущен [[28 февраля]] [[2006 год]]а. PAQ8F содержал три улучшения по сравнению с PAQ8A: более эффективное использование памяти в контекстной модели, новую непрямую контекстную модель и новый интерфейс пользователя для поддержки технологии drag-n-drop под Windows. Он не содержал английского словаря, как PAQ8B/C/D/E варианты.
* '''PAQ8G''' был выпущен [[3 марта]] [[2006 год]]а Пшемыславом Скибиньским. PAQ8G — это PAQ8F, но со словарями и переработанной моделью препроцессора текстовых данных, которая не улучшала сжатия на нетекстовых файлах.
* '''PAQ8H''' появился [[22 марта]] [[2006 год]]а благодаря Александру Ратушняку и был обновлён [[24 марта]] [[2006 год]]а. PAQ8H был улучшением PAQ8G в некоторых моделях.
* Павел Л. Голобородько выпустил '''PAQ8I''' [[18 августа]] [[2006 год]]а, с исправлением ошибок [[24 августа]], [[4 сентября]], и [[13 сентября]]. Он содержал добавление модели полутоновых чёрно-белых изображений для [[portable graymap (формат файлов)|PGM]]-файлов.
* Билл Петтис выпустил '''PAQ8J''' [[13 ноября]] [[2006 год]]а. Программа базировалась на '''PAQ8F''' с некоторыми улучшениями текстовой модели, заимствованными из PAQ8HP5. Хотя она не включала в себя словари из '''PAQ8G''' или PGM-модели из '''PAQ8I'''.
* Серж Оснач выпустил серию улучшений модели : '''PAQ8JA''' — [[16 ноября]] [[2006 год]]а, '''PAQ8JB''' — [[21 ноября]] и '''PAQ8JC''' — [[28 ноября]].
* '''PAQ8JD''' увидел свет [[30 декабря]] [[2006 год]]а стараниями Билла Петтиса. Программа была портирована на [[Microsoft Win32|Win32]] и 32-битную, 64-битную платформу [[Linux]].
* Билл Петтис произвёл '''PAQ8K''' [[13 февраля]] [[2007 год]]а. В него были добавлены дополнительные модели для бинарных файлов.
* '''PAQ8L''' появился [[13 марта]] [[2007 год]]а. Модель для [[Цепь Маркова|Динамического марковского сжатия]] была добавлена к существующему набору моделей Мэттом Махони.
* '''PAQ8O''' был выпущен [[24 августа]] [[2007 год]]а Андреасом Морфисом (Andreas Morphis). Он содержит улучшенные BMP- и JPG-модели по отношению к PAQ8L. Опционально может быть откомпилирован с поддержкой [[SSE2]] и для 64-битных Linux. На 64-битном ядре алгоритм даёт заметный рост производительности.
* '''PAQ8P''' был выпущен [[25 августа]] [[2008 год]]а Андреасом Морфисом (Andreas Morphis). Содержит улучшенную BMP-модель и добавляет WAV-модель.
* '''PAQ8PX''' появился [[25 апреля]] [[2009 год]]а благодаря Яну Ондрусу (Jan Ondrus). Он содержит различные усовершенствования, такие, как лучшее сжатие WAV- и EXE-файлов.
* '''PAQ9A''' был выпущен [[31 декабря]] [[2007 год]]а Мэттом Махони. Новая экспериментальная версия. Не включает моделей для специфичных типов файлов и имеет LZP-препроцессор.

=== Приз Хаттера ===
Серия архиваторов '''PAQ8HP1'''-'''PAQ8HP8''' была написана Александром Ратушняком с [[21 августа]] [[2006 год]]а по [[18 января]] [[2007 год]]а в качестве претендентов на [[:en:Hutter Prize|Приз Хаттера]]. Приз Хаттера — это сжатие текстовых данных размером 100 MB английского текста в формате XML и кодировке UTF-8 (фрагмент [https://dumps.wikimedia.org/ дампа Википедии]). PAQ8HP-серия произошла от PAQ8H. Программы включали в себя словари для предварительной обработки текста и специализированную настройку моделей для теста. Не текстовые модели были удалены из программ. Словарь был сгруппирован из синтаксически и семантически близких слов с общими суффиксами. Синтаксическая группировка позволяла сжимать текстовые данные потому, что близкие по написанию слова часто появлялись вместе, и их словарные коды легко моделировались на старших битах. Семантическая группировка позволяла легче сжимать словарь. В тесте учитывался размер программы вместе со сжатым словарём.

[[27 октября]] [[2006 год]]а Приз Хаттера был анонсирован Джейсом Боуери<ref>[http://groups.google.com/group/Hutter-Prize/browse_frm/thread/3f3f80c76dd14513/ Александр Ратушняк получил первую выплату Приза Хаттера] {{Wayback|url=http://groups.google.com/group/Hutter-Prize/browse_frm/thread/3f3f80c76dd14513/ |date=20070908080313 }}{{ref-en}}</ref>.
Приз получен [[30 октября]] [[2006 год]]а после выхода '''PAQ8HP5''' в размере 3416 [[евро]].

[[23 мая]] [[2009 год]]а Александр Ратушняк стал третьим победителем Приза Хаттера с модификацией '''PAQ8HP12'''.

== Результаты тестов ==
=== Максимальное сжатие ===
Тест [https://web.archive.org/web/20080724035204/http://maximumcompression.com/ Максимальное сжатие] поддерживается Вернером Бергмэнсом. Он использует два набора тестовых данных — один публичный и один приватный. Публичный набор состоит из около 55 мегабайт в 10 файлах различных типов: тексты разного формата, исполняемые файлы и изображения. Программы тестируются в режиме максимального сжатия за счёт использования оперативной памяти и процессорного времени в ущерб скорости. Тест использует два учитываемых критерия: система учёта сжатия каждого файла и общий размер сжатых данных. ПО состоянию на [[10 февраля]] [[2007 год]]а, в тесте участвовало 169 компрессоров. По первому критерию '''PAQ8JD''' шёл вторым после WinRK 3.0.3. По общему размеру сжатых данных '''PAQ8JD''' был первым.

Второй набор данных — [[Приватность|приватный]]. Он состоит из 316 355 757 байт в 510 файлах различных типов. Программы выстраиваются по трём критериям: общему размеру, времени сжатия и формуле, учитывающей размер и время сжатия. Было проведено 200 тестовых запусков, которые включали некоторые старшие версии; некоторые программы были запущены с различными опциями для одного компрессора. По общему размеру WinRK 3.0.3 был признал первым, за ним шли '''PAQ8JC''' и '''PAQ8JD'''. '''PAQ''' отмечен в конце списка по времени сжатия. '''PAQ8JD''' выполнялся 47 558 секунд (196-е место) — сравнительно медленно по сравнению с наиболее быстрой программой (4 секунды), но неплохо по сравнению с самой медленной (70 444 секунды).

=== Чарт (диаграмма) сжатия ===
[http://www.squeezechart.com Диаграмма сжатия] Стефена Буша ранжирует программы по общему размеру сжатых данных 16 неопубликованных наборов данных общим размером 3 271 105 873 байта. По состоянию на [[20 февраля]] [[2007 год]]а PAQ8JC был первым в тесте 201 программы сжатия. PAQ8JD протестирован не был.

=== Тест Чёрная Лиса ===

[http://blackfox.wz.cz/pcman/benchmark.htm Тест Чёрная Лиса] ранжировал 111 версий 69 компрессоров на 12 неопубликованных файлах общим размером 30 309 194 байта на [[4 февраля]] [[2007 год]]а. PAQ8JD вышел первым.

=== Большой текстовый тест ===
[http://www.cs.fit.edu/~mmahoney/compression/text.html Большой текстовый тест] ({{lang-en2|Large Text Compression Benchmark}}, {{lang-en2|LTCB}}) Мэтта Махони ранжирует программы по сжатому размеру доступного публично файла размером 10<sup>9</sup> байт английского текста [[:en:Wikipedia|Википедии]]. В отличие от других тестов, он включает в размер сжатого файла размер декомпрессора и любых необходимых для сжатия файлов в качестве [[ZIP|zip]]-архива. По состоянию на [[9 февраля]] [[2007 год]]а PAQ8HP8 был первым из 62 программ.

PAQ очень требователен к ресурсам памяти и процессорного времени. Следующая таблица сравнивает время сжатия и распаковки на машине Athlon-64 2,2 гигагерца, а также расход памяти в мегабайтах для некоторых популярных программ из этого теста.
{| class="wikitable"
|-
! Ранг
! Программа
! Размер сжатого файла
! Время сжатия
! Память
|-
| 1
| PAQ8HP8
| 133 423 109
| 64 639 секунд
| 1849 МБ
|-
| 18
| PPMd
| 183 976 014
| 880 секунд
| 256 МБ
|-
| 44
| bzip2
| 254 007 875
| 379 секунд
| 8 МБ
|-
| 49
| InfoZIP
| 322 649 703
| 104 секунды
| 0,1 МБ
|}

=== Наследники PAQ ===
PAQ — это [[свободное программное обеспечение]], распространяющееся на условиях [[GNU General Public License]]. Это позволяет другим авторам сделать форк PAQ и вносить такие изменения, как [[Графический интерфейс пользователя]], либо улучшить скорость сжатия за счёт коэффициента компрессии. Наиболее известные PAQ-клоны:
* '''WinUDA 0.291''', базируется на PAQ6, но быстрее [https://geolog.mydns.jp/www.geocities.co.jp/dwingj/mycomp.htm]
* '''UDA 0.301''' основывается на алгоритме PAQ8I [https://web.archive.org/web/20070224151023/http://wex.cn/dwing/mycomp.htm]
* '''[[KGB Archiver]]''' в основном PAQ6v2 с графическим интерфейсом (бета-версия поддерживает PAQ7-алгоритм сжатия)
* '''Emilcont''' на основе PAQ6 [https://web.archive.org/web/20100910070903/http://www.freewebs.com/emilcont/]
* '''[[PeaZip]]''' — графическая оболочка (для Microsoft Windows и [[GNU/Linux]]) для PAQ8F, PAQ8JD и PAQ8L [http://sourceforge.net/projects/peazip/]

== См. также ==

* [[Сжатие без потерь]]
* [[Алгоритм сжатия PPM]]

== Примечания ==
{{примечания}}

== Литература ==
* Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин ''Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео'' Диалог-МИФИ, 2002 г., 384 с. ISBN 5-86404-170-X. 3000 экз. Книга, без понимания которой невозможен был бы перевод данной статьи.<!-- это тут к чему? -->

== Ссылки ==
* [http://mattmahoney.net/dc/index.html Сайт проекта]{{ref-en}}{{V|16|10|2010}}
* [http://sourceforge.net/project/platformdownload.php?group_id=204510&sel_platform=4162 PAQ Linux Binaries]{{ref-en}}{{V|7|6|2009}} — скомпилированные исполняемые файлы PAQ для Linux
* [https://web.archive.org/web/20080724035204/http://maximumcompression.com/ MaximumCompression.com]{{ref-en}}{{V|7|6|2009}} — сайт, проводящий тестирование и предоставляющий данные о компрессорах на основе различных программных средств.
* [http://www.compression.ru/ Крупнейший в России ресурс по сжатию данных]{{ref-ru}}{{V|7|6|2009}}
* [http://www.compression-links.info/ Крупнейший каталог ресурсов по сжатию] {{Wayback|url=http://www.compression-links.info/ |date=20060716191738 }}{{ref-en}}{{V|7|6|2009}}

{{Архиваторы}}
{{Форматы архивов}}

[[Категория:Алгоритмы сжатия без потерь]]