Интернет магазин китайских планшетных компьютеров

Компьютеры - PAQ

серия свободных архиваторов с текстовым интерфейсом, которые общими усилиями разработчиков поднялись в первые места рейтингов многих тестов сжатия данных. Лучший результат в этой серии на большинстве тестов был получен архиватором PAQ8JD, созданным совместными усилиями Мэтта Махони, Александра Ратушняка, Сергея Оснача, Пшемыслава Скибиньского и Билла Петтиса, и выпущенным 30 декабря 2006 года. Однако, в некоторых тестах он отстаёт от WinRK в режиме PWCM. PWCM — сторонняя проприетарная реализация алгоритма PAQ. Специально настроенные версии алгоритма PAQ выиграли призы в Приз Хаттера и Калгари Корпус Челлендж.

Алгоритм

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

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

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

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

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

Арифметическое кодирование

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

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

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

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

Адаптивное Взвешивание Моделей

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

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

• S₀ = Σ₁w_in_0i
• S₁ = Σ₁w_in_1i
• S = S₀ + S₁
• 
• 

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

• n_i = n_0i + n_1i
• ошибка = y − P
• ошибка

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

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

• x_i = сжать)
• P = размыть

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

• сжать = ln
• размыть = 1 /.

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

• w_i ← η x_i)

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

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

Контекстное моделирование

Каждая модель разделяет входящий поток бит s на множество контекстов и отображает каждый контекст на состояние истории битов, представленное 8 битами. В версиях до PAQ6 состояние было представлено парой счётчиков. В PAQ7 и более поздних состояние содержало при определённых условиях также последний бит или целую последовательность. Значения состояний отображаются в вероятности, используя 256-значную таблицу. После табличного предсказания значение в таблице немного выравнивалось для уменьшения погрешности предсказания.

Во всех PAQ8 версиях состояния истории битов содержат следующую информацию:

• Точная последовательность до 4 битов.
• Пара счётчиков и индикатор для последнего бита для последовательностей от 5 до 15 бит.
• Пара счётчиков для последовательностей от 16 до 41 бита.

Чтобы сохранить количество состояний равным 256, следующие ограничения были наложены на счётчики:,,,,,,,,. Если счётчик превышает лимит, следующее состояние выбирается с подобным соотношением n₀ / n₁. Таким образом, если текущее состояние и 1 получена на входе, тогда новое состояние не, а.

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

Предварительная обработка текста

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