21-07-2023
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 и одержавшие верх в [1]) обрабатывают текст, просматривая его и заменяя слова из текста, содержащиеся во внешнем словаре одно- трёх-байтными кодами. Дополнительно слова в верхнем регистре кодируются специальным символом и переводом слова в нижний регистр. В PAQ8HP серии словарь организован группировкой синтаксически и семантически похожих слов вместе. Это позволяет использовать модели, которые используют только верхние биты словарных кодов в качестве контекстов.
Далее представлен список наиболее значимых изменений к алгоритму PAQ. В дополнение более мелкие множественные улучшения опущены.
Серия архиваторов PAQ8HP1-PAQ8HP8 была написана Александром Ратушняком с 21 августа 2006 года по 18 января 2007 года в качестве претендентов на Приз Хаттера. Приз Хаттера — это сжатие текстовых данных размером 100 MB Английского текста. PAQ8HP серия произошла от PAQ8H. Программы включали в себя словари для предварительной обработки текста и специализированный тюнинг моделей для теста. Нетекстовые модели были удалены из программ. Словарь был сгруппирован из синтаксически и семантически близких слов с общими суффиксами. Синтаксическая группировка позволяла сжимать текстовые данные потому, что близкие по написанию слова часто появлялись вместе, и их словарные коды легко моделировались на старших битах. Семантическая группировка позволяла легче сжимать словарь. В тесте учитывался размер программы вместе со сжатым словарём.
27 октября 2006 года Приз Хаттера был анносирован Джейсом Боуери[1]. Приз получен 30 октября 2006 года после выхода PAQ8HP5 в размере 3416 евро.
23 мая 2009 года Александр Ратушняк стал третьим победителем Приза Хаттера с модификацией PAQ8HP12.
Тест Максимальное сжатие поддерживается Вернером Бергмэнсом. Он использует два набора тестовых данных — один публичный и один приватный. Публичный набор состоит из около 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 вышел первым.
Большой Текстовый Тест Мэтта Махони ранжирует программы по сжатому размеру доступного публично файла размером 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-клоны:
Архиваторы и компрессоры (сравнение) | |
---|---|
Открытые и свободные |
7-Zip • Ark • File Roller • FreeArc • Info-ZIP • KGB Archiver • PeaZip • The Unarchiver |
Бесплатные | |
Коммерческие |
ALZip • Archive Utility • MacBinary • PowerArchiver • Squeez • StuffIt • WinAce • WinRAR • WinZip |
Командная строка |
Форматы архивов (сравнение по типу) | |
---|---|
Только архивирование | |
Только сжатие | |
Архивирование и сжатие | |
Упаковка и распространение ПО |
PAQ.