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

Алгоритм

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

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

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

• от PAQ1 до PAQ3 каждое предсказание представлено парой битовых счётчиков ${\displaystyle (n_{0},n_{1})}$ . Эти счётчики комбинировались взвешенным суммированием, таким, что больший вес определяется более длинным контекстом.
• в PAQ4 до PAQ6 предсказания комбинировались, как и в первом случае, но веса, принадлежащие каждой модели, назначались так, чтобы более точные модели получали преимущество.
• в PAQ7 и более поздних версиях выход каждой модели есть вероятность ${\displaystyle [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 каждая модель отображала множество различных контекстов на пару счётчиков: ${\displaystyle n_{0}}$ — количество нулевых битов и ${\displaystyle n_{1}}$ — количество единичных битов. Для увеличения значимости более поздней истории битов счётчик уменьшался почти вдвое, когда противоположный бит встречался. Например, текущее состояние модели, ассоциированное с контекстом ${\displaystyle (n_{0},n_{1})=(12,3)}$ и бит 1 наблюдается на входе — счётчик обновляется до состояния (7,4).

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

• ${\displaystyle S_{0}=\Sigma _{1}w_{i}n_{0i}}$
• ${\displaystyle S_{1}=\Sigma _{1}w_{i}n_{1i}}$
• ${\displaystyle S=S_{0}+S_{1}}$
• ${\displaystyle P(0)={\frac {S_{0}}{S}}}$
• ${\displaystyle P(1)={\frac {S_{1}}{S}}}$ ,

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

• n _i = n _0i + n _1i
• ошибка = y − P(1)
• ${\displaystyle w_{i}\gets w_{i}+{\frac {S\,n_{1i}-S_{1}n_{i}}{S_{0}S_{1}}}}$ ошибка

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

Начиная с 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 года Мэттом Махони. Он использовал фиксированные веса и не включал разрежённые и аналоговые модели. Всего использовалось 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, но быстрее
• UDA 0.301 основывается на алгоритме PAQ8I
• KGB Archiver в основном PAQ6v2 с графическим интерфейсом (бета-версия поддерживает PAQ7-алгоритм сжатия)
• Emilcont на основе PAQ6
• PeaZip — графическая оболочка (для Microsoft Windows и GNU/Linux ) для PAQ8F, PAQ8JD и PAQ8L

См. также

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

Примечания

Литература

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

Ссылки

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