PAQ

PAQ — серия свободных архиваторов с текстовым интерфейсом, которые общими усилиями разработчиков поднялись в первые места рейтингов многих тестов сжатия данных (хотя и ценой процессорного времени и объёма памяти). Лучший результат в этой серии на большинстве тестов был получен архиватором PAQ8JD, созданным совместными усилиями Мэтта Махони (Matt Mahoney), Александра Ратушняка, Сергея Оснача, Пшемыслава Скибиньского (Przemysław Skibiński) и Билла Петтиса (Bill Pettis), и выпущенным 30 декабря 2006 года. Однако в некоторых тестах он отстаёт от WinRK (созданного Малькомом Тейлором в январе 2005 года) в режиме PWCM. PWCM (англ. PAQ weighted context mixing, «PAQ взвешенное смешивание контекстов») — сторонняя проприетарная реализация алгоритма PAQ. Специально настроенные версии алгоритма PAQ выиграли призы в конкурсах Приз Хаттера и Калгари Корпус Челлендж.

Алгоритм

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

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

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

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

PAQ1SSE и позднейшие версии использовали постобработку предсказания методом вторичной оценки символа (SSE — 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₂ P(r = s) бит. Длина s сохраняется в заголовке архива.

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

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

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

Адаптивное взвешивание моделей

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

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

• [math]\displaystyle{ S_0 = \Sigma_1 w_i n_{0i} }[/math]
• [math]\displaystyle{ S_1 = \Sigma_1 w_i n_{1i} }[/math]
• [math]\displaystyle{ S = S_0 + S_1 }[/math]
• [math]\displaystyle{ P(0) = \frac{S_0}{S} }[/math]
• [math]\displaystyle{ P(1) = \frac{S_1}{S} }[/math],

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

• n_i = n_0i + n_1i
• ошибка = y − P(1)
• [math]\displaystyle{ w_i \gets w_i + \frac{S\,n_{1i} - S_1 n_i}{S_0 S_1} }[/math] ошибка

Нейронные сети для смешивания

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

• x_i = сжать(P_i(1))
• P(1) = размыть(Σ_i w_i x_i),

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

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

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

• w_i ← η x_i (y — P(1)),

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

Большинство версий PAQ используют небольшой контекст при выборе набора весов для нейронной сети. Некоторые версии используют двух- и трёхшаговые предсказатели, состоящие из соответственно двух или трёх множеств нейронных сетей, выход каждой предыдущей является входом для следующего множества сетей, мощность которого меньше, и затем следует вторичная оценка символа. Более того, для каждого входящего предсказания может быть несколько входов, являющихся нелинейными функциями P_i(1) в дополнение к сжать(P(1)).

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

Каждая модель разделяет входящий поток бит s на множество контекстов и отображает каждый контекст на состояние истории битов, представленное 8 битами. В версиях до PAQ6 состояние было представлено парой счётчиков (n₀, n₁). В 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₀ / n₁. Таким образом, если текущее состояние (n₀ = 4, n₁ = 4, последний бит = 0) и 1 получена на входе, тогда новое состояние не (n₀ = 4, n₁ = 5, последний бит = 1), а (n₀ = 3, n₁ = 4, последний бит = 1).

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

Предварительная обработка текста

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

История

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

• PAQ1 был выпущен 6 января 2002 года Мэттом Махони. Он использовал фиксированные веса и не включал разрежённые и аналоговые модели. Всего использовалось 5 моделей.
• 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 взяла приз на Калгари Корпус Челлендж 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 и 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 сентября. Он содержал добавление модели полутоновых чёрно-белых изображений для PGM-файлов.
• Билл Петтис выпустил PAQ8J 13 ноября 2006 года. Программа базировалась на PAQ8F с некоторыми улучшениями текстовой модели, заимствованными из PAQ8HP5. Хотя она не включала в себя словари из PAQ8G или PGM-модели из PAQ8I.
• Серж Оснач выпустил серию улучшений модели : PAQ8JA — 16 ноября 2006 года, PAQ8JB — 21 ноября и PAQ8JC — 28 ноября.
• PAQ8JD увидел свет 30 декабря 2006 года стараниями Билла Петтиса. Программа была портирована на 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 года в качестве претендентов на Приз Хаттера. Приз Хаттера — это сжатие текстовых данных размером 100 MB английского текста в формате xml и кодировке UTF-8 (фрагмент дампа Википедии). PAQ8HP-серия произошла от PAQ8H. Программы включали в себя словари для предварительной обработки текста и специализированный тюнинг моделей для теста. Нетекстовые модели были удалены из программ. Словарь был сгруппирован из синтаксически и семантически близких слов с общими суффиксами. Синтаксическая группировка позволяла сжимать текстовые данные потому, что близкие по написанию слова часто появлялись вместе, и их словарные коды легко моделировались на старших битах. Семантическая группировка позволяла легче сжимать словарь. В тесте учитывался размер программы вместе со сжатым словарём.

27 октября 2006 года Приз Хаттера был анонсирован Джейсом Боуери. Приз получен 30 октября 2006 года после выхода PAQ8HP5 в размере 3416 евро.

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

Результаты тестов

Максимальное сжатие

Тест Максимальное сжатие поддерживается Вернером Бергмэнсом. Он использует два набора тестовых данных — один публичный и один приватный. Публичный набор состоит из около 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 секунды).

Чарт (диаграмма) сжатия

Диаграмма сжатия Стефена Буша ранжирует программы по общему размеру сжатых данных 16 неопубликованных наборов данных общим размером 3 271 105 873 байта. По состоянию на 20 февраля 2007 года PAQ8JC был первым в тесте 201 программы сжатия. PAQ8JD протестирован не был.

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

Тест Чёрная Лиса ранжировал 111 версий 69 компрессоров на 12 неопубликованных файлах общим размером 30 309 194 байта на 4 февраля 2007 года. PAQ8JD вышел первым.

Большой текстовый тест

Большой текстовый тест (Large Text Compression Benchmark, LTCB) Мэтта Махони ранжирует программы по сжатому размеру доступного публично файла размером 10⁹ байт английского текста Википедии. В отличие от других тестов, он включает в размер сжатого файла размер декомпрессора и любых необходимых для сжатия файлов в качестве zip-архива. По состоянию на 9 февраля 2007 года PAQ8HP8 был первым из 62 программ.

PAQ очень требователен к ресурсам памяти и процессорного времени. Следующая таблица сравнивает время сжатия и распаковки на машине Athlon-64 2,2 гигагерца, а также расход памяти в мегабайтах для некоторых популярных программ из этого теста.

Ранг	Программа	Размер сжатого файла	Время сжатия	Память
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, но быстрее [2]
• UDA 0.301 основывается на алгоритме PAQ8I [3]
• KGB Archiver в основном PAQ6v2 с графическим интерфейсом (бета-версия поддерживает PAQ7-алгоритм сжатия)
• Emilcont на основе PAQ6 [4]
• PeaZip — графическая оболочка (для Microsoft Windows и GNU/Linux) для PAQ8F, PAQ8JD и PAQ8L [5]

См. также

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

Литература

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

Ссылки

• Сайт проекта (англ.) (Дата обращения: 16 октября 2010)
• PAQ Linux Binaries (англ.) (Дата обращения: 7 июня 2009) — скомпилированные исполняемые файлы PAQ для Linux
• MaximumCompression.com (англ.) (Дата обращения: 7 июня 2009) — сайт, проводящий тестирование и предоставляющий данные о компрессорах на основе различных программных средств.
• Крупнейший в России ресурс по сжатию данных (рус.) (Дата обращения: 7 июня 2009)
• Крупнейший каталог ресурсов по сжатию Архивная копия от 16 июля 2006 на Wayback Machine (англ.) (Дата обращения: 7 июня 2009)