PAQ

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

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

Специальные версии алгоритма PAQ, оптимизированные для конкретных задач, были отмечены наградами на конкурсах «Приз Хаттера» и «Калгари Корпус Челлендж».

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

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

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

от PAQ1 до PAQ3 каждое предсказание представлено парой битовых счётчиков . Эти счётчики комбинировались взвешенным суммированием, таким, что больший вес определяется более длинным контекстом. в PAQ4 до PAQ6 предсказания комбинировались, как и в первом случае, но веса, принадлежащие каждой модели, назначались так, чтобы более точные модели получали преимущество. в PAQ7 и более поздних версиях выход каждой модели есть вероятность , в отличие от пары счётчиков, вероятности суммируются при помощи искусственных нейронных сетей.

PAQ1SSE и позднейшие версии использовали постобработку предсказания методом вторичной оценки символа ( — ), то есть комбинированное предсказание и небольшой контекст использовались для выбора следующего предсказания по таблице. После того, как символ был закодирован, данные в таблице корректировались для уменьшения ошибки предсказания. Вторичная оценка символа может быть объединена в один процесс с разными контекстами либо может выполняться параллельно, усредняясь с выходами моделей.

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

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

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

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

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

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

,

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

ni = n0i + n1i ошибка = y − P(1) ошибка

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

xi = сжать(Pi(1)) P(1) = размыть(Σi wi xi),

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

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

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

wi ← η xi (y — P(1)),

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

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

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

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

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

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

PAQ1 был выпущен 6 января 2002 года Мэттом Махони. Он использовал фиксированные веса и не включал разрежённые и аналоговые модели. Всего использовалось 5 моделейPAQ1: Описание модели , 2002, Matt Mahoney, v1.02. 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 и дополненные английским словарным препроцессором. Он достиг наилучшего результата на Калгари корпусе, но не на большинстве других тестов.