PAQ

PAQ — серия консольных архиваторов с открытым кодом, которые общими усилиями разработчиков поднялись в первые места рейтингов многих тестов сжатия данных (хотя и ценой процессорного времени и объёма памяти). Лучшего результата в этой серии на большинстве тестов был получен PAQ8JD, созданный совместными усилиями Matt Mahoney, Александра Ратушняка, Сергея Оснача, Przemyslaw Skibinski и Bill Pettis, и выпущенный 30 декабря 2006 года. Однако он в некоторых тестах отстаёт от WinRK (созданного Малькомом Тейлором в январе 2005 года) в режиме PWCM. PWCM — это проприетарный алгоритм сжатия данных, который относится к семейству PAQ и трактуется как PAQ взвешенное смешивание контекстов. Специально оттюнигованные версии алгоритма PAQ выиграли призы в Приз Хаттера и Калгари Корпус Челлендж.

Алгоритм

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

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

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

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

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

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

• S₀ = Σ_i w_i n_0i
• S₁ = Σ_i w_i n_1i
• S = S₀ + S₁
• P(0) = S₀ / S
• P(1) = S₁ / S

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

• n_i = n_0i + n_1i
• ошибка = y − P(1)
• w_i ← w_i + [(S n_1i − S₁ n_i) / (S₀ S₁)] ошибка

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

Начиная с 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 и одержавшие верх в Призе Хаттера) обрабатывают текст, просматривая его и заменяя слова из текста, содержащиеся во внешнем словаре одно-трёх байтными кодами. Дополнительно слова в верхнем регистре кодируются специальным символом и переводом слова в нижний регистр. В PAQ8HP серии словарь организован группировкой синтаксически и семантически похожих слов вместе. Это позволяет использовать модели, которые используют только верхние биты словарных кодов в качестве контекстов.

История

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

• PAQ1 был выпущен 6 января, 2002 года Маттом Махонеем. Он использовал фиксированные веса и не включал разрежённые и аналоговые модели.

• PAQ1SSE/PAQ2 был выпущен 11 мая, 2003 года Сергеем Осначем. Он значительно улучшил сжатие добавлением Вторичной Оценки Символа между предсказателем и кодировщиком.Вторичная Оценка Символа подавала на вход небольшой контекст и текущее предсказание и на выходе получалось новое предсказание из таблицы. Табличное значение затем обновлялось для отражения текущего бита.

• PAQ3N был выпущен 9 октября, 2003. Была добавлена разрежённая модель.

• PAQ4 выпущенный 15 ноября, 2003 Маттом Махонеем использовал адаптивное взвешивание. PAQ5(18 декабря,2003) и PAQ6(30 декабря,2003) были незначительными улучшениями, включающими аналоговую модель. К этому времени PAQ конкурировал с лучшими PPM-компрессорами и привлёк внимание сообщества людей, занимающихся сжатием данных, которое вылилось в многочисленных улучшениях до апреля 2004. Берто Дестасио доводил модели и поправил последовательность обхода счётчиков. Джоган де Бок внёс улучшения в интерфейс пользователя. Дэвид А. Скотт улучшил арифметический кодер. Фабио Буффони ускорил программу.

• В период с 20 мая,2004 по 27 июля,2004 Александр Ратушняк выпустил семь версий PAQAR, который был значительным совершенствованием сжатия путём добавления многих новых моделей, многочисленных миксеров с выбором весов по контексту, добавлением Вторичной Оценки Символа на выход каждого миксера и наконец добавлением предварительной обработки исполянемых файлов архитектуры процессоров Intel. PAQAR оставался на вершине программ сжатия данных без потерь до конца 2004 года, но был гораздо медленнее своих предшественников.

• С 18 января по 7 февраля 2005 года Przemyslaw Skibinski выпустил четыре версии PAsQDa, базировавшиеся на PAQ6 и PAQAR и дополненные Английским словарным препроцессором. Он достил наилучшего результата на Калгари Корпусе, но не на большинстве других тестов.

• Модифицированная Маттом Махонеем, версия PAQ6 взяла приз на Калгари Корпус Челлендж 10 января ,2004.Это событие перекрылось десятью последовательными версиями PAQAR Александра Ратушняка. Наиболее поздняя увидела свет 5 июня,2006года, она состояла из сжатых вместе данных и текста программы и занимала 589 862 байта.

• PAQ7 был выпущен в декабре 2005 Маттом Махонеем.PAQ7 — это полностью переписанный PAQ6 и его варианты(PAQAR,PAsQDa). Степень сжатия была схожа с PAQAR, но время выполнения в 3 раза меньше. Но ему не хватало x86 и словаря, поэтому он был не так хорош на Windows-ских исполняемых модулях и английских текстах как PAsQDa. Хотя он включал модели для цветных .bmp,.tiff и .jpeg файлов, поэтому сжимал их лучше. Главное отличие PAQ7 было в том, что он использован нейронную сеть для комбинирования моделей в отличии от уменьшающего градиент миксера. Другой чертой PAQ7 была возможность сжимать встроенные в Exel-, 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 года Przemyslaw Skibinski. 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 года стараниями Билла Петтиса. Он был портирован на 32-битную Windows для нескольких процессоров, и 32- и 64- битный Linux.

• Билл Петтис произвёл PAQ8K 13 февраля 2007 года. В него были добавлены дополнительные модели для бинарных файлов.

• PAQ8L был издан 13 марта 2007 года.Модель для Динамическиого Марковского Сжатия была добавлена к существующему набору моделей Мэттом Махони.

Приз Хаттера

Серия архиваторов PAQ8HP1-PAQ8HP8 была написана Александром Ратушняком с 21 августа 2006 года по 18 января 2007 года в качестве претендентов на Приз Хаттера. Приз Хаттера — это сжатие текстовых данных размером 100MB Английского текста. PAQ8HP серия произошла от PAQ8H. Программы включали в себя словари для предварительной обработки текста и специализированный тюнинг моделей для теста. Не текстовые модели были удалены из программ. Словарь был сгруппирован из синтаксически и семантически близких слов с общими суффиксами. Синтаксическая группировка позволяла сжимать текстовые данные потому, что близкие по написанию слова часто появлялись вместе, и их словарные коды легко моделировались на старших битах. Семантическая группировка позволяла легче сжимать словарь. В тесте учитывался размер программы вместе со сжатым словарём.

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

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

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

Тест Максимальное сжатие поддерживается Вернером Бергмэнсом. Он использует два набора тестовых данных - один публичный и один приватный. Публичный набор состоит из около 55-ти Мегабайт в 10 файлах различных типов: тексты разного формата, исполняемые файлы и изображения. Программы тестируются в режиме максимального сжатия за счёт использования оперативной памяти и процессорного времени в ущерб скорости. Тест использует два учитываемых критерия: система учёта сжатия каждого файла и общий размер сжатых данных. На состояние 10 февраля 2007 года в тесте учавстовало 169 компрессоров. По первому критерию PAQ8JD шел вторым после WinRK 3.0.3. По общему размеру сжатых данных PAQ8JD был первым.

Второй набор данных приватный. Он состоит из 316355757 байт в 510 файлах различных типов. Программы ранжируются по трём критериям: общему размеру, времени сжатия и формуле, учитывающей размер и время сжатия. Было проведено 200 тестовых запусков, которые включали некоторые старшие версии и некоторые программы были запущены с различными опциями для одного компрессора. По общему размеру WinRK 3.0.3 был признал первым, за ним шли PAQ8JC и PAQ8JD. PAQ отмечен в конце списка по времени сжатия. PAQ8JD выполнялся 47558 секунд (196 место) сравнительно медленно с наибыстрейшей программой( 4 секунды) и еще неплохо для медленейшей (70444 секунды).

Чарт(Диаграмма) Сжатия

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

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

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

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

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

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

Ранг	Программа	Размер сжатого файла	Время сжатия	Память
1	PAQ8HP8	133423109	64639 секунд	1849 МБ
18	PPMd	183976014	880 секунд	256 МБ
44	bzip2	254007875	379 секунд	8 МБ
49	InfoZIP	322649703	104 секунд	0.1 МБ

Наследники PAQ

PAQ - это Свободное Программное Обеспечение и распространяется на условиях Открытого лицензионного соглашения GNU. Это позволяет другим авторам расщепить ядро PAQ и вносить такие изменения, как Графический интерфейс пользователя либо улучшить скорость сжатия за счёт коэффициента компрессии. Наиболее известные PAQ-клоны:

• WinUDA 0.291, базируется на PAQ6, но быстрее [1]
• UDA 0.301 основывается на алгоритме PAQ8I [2]
• KGB Архиватор в основном PAQ6v2 с графическим интерфейсом [3] (бэта версия поддерживает PAQ7 алгоритм сжатия)
• Emilcont на основе PAQ6 [4]
• Peazip - графическая оболочка (под Windows и Линукс ) для PAQ8F,PAQ8JD и PAQ8L [5]

Смотреть также

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

Внешние ссылки

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