PAQ

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

PAQ — серия консольных архиваторов с открытым кодом, которые общими усилиями разработчиков поднялись в первые места рейтингов многих тестов сжатия данных (хотя и ценой процессорного времени и объёма памяти). Лучшего результата в этой серии на большинстве тестов был получен PAQ8JD, созданный совместными усилиями Matt Mahoney, Александра Ратушняка, Сергея Оснача, Przemyslaw Skibinski и Bill Pettis, и выпущенный 30 декабря 2006 года. Однако он в некоторых тестах отстаёт от WinRK (созданного Малькомом Тейлором в январе 2005 года) в режиме PWCM. PWCM — это проприетарный алгоритм сжатия данных, который относится к семейству PAQ и трактуется как PAQ взвешенное смешивание контекстов. Специально оттюнигованные версии алгоритма PAQ выиграли призы в Приз Хаттера и Калгари Корпус Челлендж.

Алгоритм[править]

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

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

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

  • от PAQ1 до PAQ3 каждое предсказание представлено парой битовых счётчиков \((n_0,n_1)\).Эти счётчики комбинировались взвешенным суммированием, таким что больший вес определяется более длиным контекстом.
  • в PAQ4 до PAQ6 предсказания комбинировались как и в первом случае, но веса принадлежащие каждой модели назначались так, чтобы более точные модели получали преимущество.
  • в PAQ7 и более поздних версиях выход каждой модели есть вероятность \([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, что длина её хотя бы на один байт превосходит лимит Шеннона: -log2 P(r = s) бит. Длина s сохраняется в заголовке архива.

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

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

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

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

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

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

  • S0 = Σi wi n0i
  • S1 = Σi wi n1i
  • S = S0 + S1
  • P(0) = S0 / S
  • P(1) = S1 / S

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

  • ni = n0i + n1i
  • ошибка = y − P(1)
  • wi ← wi + [(S n1i − S1 ni) / (S0 S1)] ошибка

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

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

  • xi = сжать(P_i(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 года Маттом Махонеем. Он использовал фиксированные веса и не включал разрежённые и аналоговые модели.
  • PAQ1SSE/PAQ2 был выпущен 11 мая, 2003 года Сергеем Осначем. Он значительно улучшил сжатие добавлением Вторичной Оценки Символа между предсказателем и кодировщиком.Вторичная Оценка Символа подавала на вход небольшой контекст и текущее предсказание и на выходе получалось новое предсказание из таблицы. Табличное значение затем обновлялось для отражения текущего бита.
  • PAQ3N был выпущен 9 октября, 2003. Была добавлена разрежённая модель.
  • PAQ4 выпущенный 15 ноября, 2003 Маттом Махонеем использовал адаптивное взвешивание. PAQ5(18 декабря,2003) и PAQ6(30 декабря,2003) были незначительными улучшениями, включающими аналоговую модель. К этому времени PAQ конкурировал с лучшими PPM-компрессорами и привлёк внимание сообщества людей, занимающихся сжатием данных, которое вылилось в многочисленных улучшениях до апреля 2004. Берто Дестасио доводил модели и поправил последовательность обхода счётчиков. Джоган де Бок внёс улучшения в интерфейс пользователя. Дэвид А. Скотт улучшил арифметический кодер. Фабио Буффони ускорил программу.
  • В период с 20 мая,2004 по 27 июля,2004 Александр Ратушняк выпустил семь версий PAQAR, который был значительным совершенствованием сжатия путём добавления многих новых моделей, многочисленных миксеров с выбором весов по контексту, добавлением Вторичной Оценки Символа на выход каждого миксера и наконец добавлением предварительной обработки исполянемых файлов архитектуры процессоров Intel. PAQAR оставался на вершине программ сжатия данных без потерь до конца 2004 года, но был гораздо медленнее своих предшественников.
  • С 18 января по 7 февраля 2005 года Przemyslaw Skibinski выпустил четыре версии PAsQDa, базировавшиеся на PAQ6 и PAQAR и дополненные Английским словарным препроцессором. Он достил наилучшего результата на Калгари Корпусе, но не на большинстве других тестов.
  • Модифицированная Маттом Махонеем, версия PAQ6 взяла приз на Калгари Корпус Челлендж 10 января ,2004.Это событие перекрылось десятью последовательными версиями PAQAR Александра Ратушняка. Наиболее поздняя увидела свет 5 июня,2006года, она состояла из сжатых вместе данных и текста программы и занимала 589 862 байта.
  • PAQ7 был выпущен в декабре 2005 Маттом Махонеем.PAQ7 — это полностью переписанный PAQ6 и его варианты(PAQAR,PAsQDa). Степень сжатия была схожа с PAQAR, но время выполнения в 3 раза меньше. Но ему не хватало x86 и словаря, поэтому он был не так хорош на Windows-ских исполняемых модулях и английских текстах как PAsQDa. Хотя он включал модели для цветных .bmp,.tiff и .jpeg файлов, поэтому сжимал их лучше. Главное отличие PAQ7 было в том, что он использован нейронную сеть для комбинирования моделей в отличии от уменьшающего градиент миксера. Другой чертой PAQ7 была возможность сжимать встроенные в Exel-, 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 года Przemyslaw Skibinski. PAQ8G это PAQ8F, но со словарями и переработанной моделью препроцессора текстовых данных, которая не улучшала сжатие на нетекстовых файлах.
  • PAQ8H появился 22 марта, 2006 года, благодаря Александру Ратушняку, и был обновлен 24 марта, 2006 года. PAQ8H был улучшением PAQ8G в некоторых моделях.
  • Билл Петтис выпустил PAQ8J 13 ноября, 2006 года. Программа базировалась на PAQ8F с некоторыми улучшениями текстовой модели, заимствованными из PAQ8HP5. Хотя, она не включала в себя словари из PAQ8G или PGM модели из PAQ8I.
  • PAQ8JD увидел свет 30 декабря 2006 года стараниями Билла Петтиса. Он был портирован на 32-битную Windows для нескольких процессоров, и 32- и 64- битный Linux.
  • Билл Петтис произвёл PAQ8K 13 февраля 2007 года. В него были добавлены дополнительные модели для бинарных файлов.


Приз Хаттера[править]

Серия архиваторов PAQ8HP1-PAQ8HP8 была написана Александром Ратушняком с 21 августа 2006 года по 18 января 2007 года в качестве претендентов на Приз Хаттера. Приз Хаттера — это сжатие текстовых данных размером 100MB Английского текста. PAQ8HP серия произошла от PAQ8H. Программы включали в себя словари для предварительной обработки текста и специализированный тюнинг моделей для теста. Не текстовые модели были удалены из программ. Словарь был сгруппирован из синтаксически и семантически близких слов с общими суффиксами. Синтаксическая группировка позволяла сжимать текстовые данные потому, что близкие по написанию слова часто появлялись вместе, и их словарные коды легко моделировались на старших битах. Семантическая группировка позволяла легче сжимать словарь. В тесте учитывался размер программы вместе со сжатым словарём.

27 октября 2006 года Приз Хаттера был анносирован Джейсом Боуери [1] Приз получен 30 октября 2006 года после выхода PAQ8HP5 в размере 3416 евро. Последующие архиваторы этой серии ожидают своего приза.

Результаты тестов[править]

Максимальное сжатие[править]

Тест Максимальное сжатие поддерживается Вернером Бергмэнсом. Он использует два набора тестовых данных - один публичный и один приватный. Публичный набор состоит из около 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[править]

PAQ - это Свободное Программное Обеспечение и распространяется на условиях Открытого лицензионного соглашения GNU. Это позволяет другим авторам расщепить ядро PAQ и вносить такие изменения, как Графический интерфейс пользователя либо улучшить скорость сжатия за счёт коэффициента компрессии. Наиболее известные PAQ-клоны:

  • WinUDA 0.291, базируется на PAQ6, но быстрее [1]
  • UDA 0.301 основывается на алгоритме PAQ8I [2]
  • KGB Архиватор в основном PAQ6v2 с графическим интерфейсом [3] (бэта версия поддерживает PAQ7 алгоритм сжатия)
  • Emilcont на основе PAQ6 [4]
  • Peazip - графическая оболочка (под Windows и Линукс ) для PAQ8F,PAQ8JD и PAQ8L [5]

Смотреть также[править]

Ссылки[править]

Внешние ссылки[править]

Архиваторы
Open Source: 7-Zip • Ark • File Roller • KGB Archiver • PeaZip • The Unarchiver

Freeware: DGCA • Filzip • GCA • IZArc • TUGZip • QuickZip • Zipeg • ZipGenius


Проприетарные: ALZip • BOMArchiveHelper • MacBinary • PowerArchiver • Squeez • StuffIt • WinAce • WinRAR • WinRK • WinZip


Командная строка: ARC • ARJ • JAR • Info-ZIP • LHA • NABOB • PAQ • PKZIP • RAR • SBC • Tar • UPX


Компрессоры: bzip2 • compress • gzip • lzop