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 семействе для сбора статистики и предсказания вероятности следующего символа используются в основном следующие модели:
Все версии PAQ предсказывают и сжимают за раз один бит, но различаются в деталях реализации того, как предсказания комбинируются и обрабатываются после. Как только предсказательно была определена вероятность появления следующего бита, бит сжимается арифметическим кодером. Существует три способа для комбинирования предсказаний моделей в зависимости от версии PAQ.
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, что длина её хотя бы на один байт превосходит лимит Шеннона: -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, то веса назначаются следующим образом:
Начиная с PAQ7 выходом каждой модели является предсказание (вместо пары счётчиков). Предсказания усредняются в логистическом домене по формуле:
где P(1) — вероятность того, что следующий бит будет единицей, а Pi(1) — вероятность, оцененная i-той моделью и
После каждого предсказания модель обновляется выравниванием весов для уменьшения цены сжатия.
где η — коэффициент обучения (обычно от 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-версиях состояния истории битов содержат следующую информацию:
Чтобы сохранить количество состояний равным 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. В дополнение более мелкие множественные улучшения опущены.
Серия архиваторов PAQ8HP1-PAQ8HP8 была написана Александром Ратушняком с 21 августа 2006 года по 18 января 2007 года в качестве претендентов на Приз Хаттера. Приз Хаттера — это сжатие текстовых данных размером 100 MB английского текста в формате xml и кодировке UTF-8 (фрагмент дампа Википедии). PAQ8HP-серия произошла от PAQ8H. Программы включали в себя словари для предварительной обработки текста и специализированный тюнинг моделей для теста. Нетекстовые модели были удалены из программ. Словарь был сгруппирован из синтаксически и семантически близких слов с общими суффиксами. Синтаксическая группировка позволяла сжимать текстовые данные потому, что близкие по написанию слова часто появлялись вместе, и их словарные коды легко моделировались на старших битах. Семантическая группировка позволяла легче сжимать словарь. В тесте учитывался размер программы вместе со сжатым словарём.
27 октября 2006 года Приз Хаттера был аносирован Джейсом Боуери[2]. Приз получен 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 выполнялся 47558 секунд (196-е место) — сравнительно медленно по сравнению с наиболее быстрой программой (4 секунды), но неплохо по сравнению с самой медленной (70444 секунды).
Диаграмма сжатия Стефена Буша ранжирует программы по общему размеру сжатых данных 16 неопубликованных наборов данных общим размером 3 271 105 873 байт. По состоянию на 20 февраля 2007 года, PAQ8JC был первым в тесте 201 программы сжатия. PAQ8JD протестирован не был.
Тест Чёрная Лиса ранжировал 111 версий 69 компрессоров на 12 неопубликованных файлах общим размером 30 309 194 байт на 4 февраля 2007 года. PAQ8JD вышел первым.
Большой Текстовый тест Мэтта Махони ранжирует программы по сжатому размеру доступного публично файла размером 109 байт английского текста Википедии. В отличие от других тестов, он включает в размер сжатого файла размер декомпрессора и любых необходимых для сжатия файлов в качестве 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 — это Свободное программное обеспечение и распространяется на условиях GNU General Public License. Это позволяет другим авторам сделать форк PAQ, и вносить такие изменения, как Графический интерфейс пользователя, либо улучшить скорость сжатия за счёт коэффициента компрессии. Наиболее известные PAQ-клоны:
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .