УПАКОВКА

Для несвязанного PAQ.EXE компрессор для DOS, см. Квантовое сжатие .

Пример сеанса PAQ8O

PAQ — это серия архиваторов со сжатием данных без потерь , которые прошли совместную разработку и заняли первые места в нескольких тестах, измеряющих степень сжатия (хотя и за счет скорости и использования памяти). Специализированные версии PAQ получили премию Hutter Prize и Calgary Challenge . PAQ — бесплатное программное обеспечение , распространяемое по лицензии GNU General Public License .

Алгоритм

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

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

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

• В PAQ1–PAQ3 каждое предсказание представлено в виде пары битов. $(n_{0},n_{1})$. Эти значения объединяются путем взвешенного суммирования, при этом больший вес присваивается более длинным контекстам.
• В PAQ4–PAQ6 прогнозы объединяются, как и раньше, но веса, присвоенные каждой модели, корректируются в пользу более точных моделей.
• В PAQ7 и более поздних версиях каждая модель выводит вероятность, а не пару значений. Вероятности объединяются с помощью искусственной нейронной сети .

PAQ1SSE и более поздние версии выполняют постобработку прогноза с использованием оценки вторичного символа (SSE). Комбинированный прогноз и небольшой контекст используются для поиска нового прогноза в таблице. После кодирования бита запись таблицы корректируется, чтобы уменьшить ошибку прогнозирования. Этапы SSE могут быть конвейерными с различными контекстами или вычисляться параллельно с усреднением выходных данных.

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

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

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

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

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

Адаптивное взвешивание модели

В версиях от PAQ до PAQ6 каждая модель отображает набор отдельных контекстов в пару счетчиков. $n_{0}$, количество нулевых битов и $n_{1}$, счет 1 бит. Чтобы отдать предпочтение недавней истории, половина отсчета больше 2 отбрасывается, когда наблюдается противоположный бит. Например, если текущее состояние, связанное с контекстом, $(n_{0},n_{1})=(12,3)$ и наблюдается 1, то счетчик обновляется до (7, 4).

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

• S ₀ знак равно Σ _я ш _я п _{0 я} ,
• S ₁ знак равно Σ _я ш _я п _{1 я} ,
• S = S ₀ + S ₁ ,
• Р(0) S0 ₌ / S ,
• (1) = S1 _/ Р S ,

где w _i — вес i -й модели. В PAQ3 веса фиксировались и устанавливались в зависимости от ситуации. (Контексты порядка n имели вес n ² .) Начиная с PAQ4, веса корректировались адаптивно в направлении, которое позволит уменьшить будущие ошибки в том же наборе контекстов. Если кодируемый бит равен y , то корректировка веса равна:

• п _{я знак} равно п _{0 я} + п _{1 я} ,
• ошибка = y – P(1),
• ш _я ← ш _я + [( S п _{1 я} - S ₁ п _я ) / ( S ₀ S ₁ )] ошибка.

Смешение нейронных сетей

Начиная с PAQ7, каждая модель выдает прогноз (вместо пары значений). Эти прогнозы усреднены в логистической области:

• x _i = растяжение (P _i (1)),
• P(1) = сквош(Σ _i w _i x _i ),

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

• растяжение( х ) = ln( х / (1 - х )),
• сквош( x ) = 1 / (1 + e ^{− х} ) (обратное растяжению).

После каждого прогноза модель обновляется путем корректировки весов, чтобы минимизировать затраты на кодирование:

• w _i ← w _i + η x _i ( y − P(1)),

где η — скорость обучения (обычно от 0,002 до 0,01), y — прогнозируемый бит, а ( y — P(1)) — ошибка прогнозирования. Алгоритм обновления веса отличается от обратного распространения ошибки тем, что члены P(1)P(0) отбрасываются. Это связано с тем, что целью нейронной сети является минимизация затрат на кодирование, а не среднеквадратическая ошибка.

Большинство версий PAQ используют небольшой контекст для выбора набора весов для нейронной сети. В некоторых версиях используются несколько сетей, выходные данные которых объединяются с еще одной сетью перед этапами SSE. Более того, для каждого входного предсказания может быть несколько входных данных, которые являются нелинейными функциями от Pi ₍ 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, в частности PAsQDa, PAQAR (обе производные от PAQ6) и от PAQ8HP1 до PAQ8HP8 (производные от PAQ8 и получатели призов Hutter ), предварительно обрабатывают текстовые файлы, просматривая слова во внешнем словаре и заменяя их 1-3-байтовыми кодами. . Кроме того, прописные буквы кодируются специальным символом, за которым следует строчная буква. В серии PAQ8HP словарь организован путем группировки синтаксически и семантически связанных слов. Это позволяет моделям использовать в качестве контекста только наиболее значимые биты словарных кодов.

Сравнение

В следующей таблице представлен образец теста сжатия большого текста Мэтта Махони, который состоит из файла, состоящего из 10 ⁹ байты (1 ГБ или 0,931 ГиБ ) текста английской Википедии .

Программа	Сжатый размер (байты)	% исходного размера	Время сжатия ( нс / Б )	Память (МиБ)
PAQ8HP8	133,423,109	13.34	64 639	1849
PPMd	183,976,014	18.4	880	256
bzip2	254,007,875	25.4	379	8
ИнфоZIP	322,649,703	32.26	104	0.1

разделе Тесты сжатия без потерь Список тестов сжатия файлов см. в .

История

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

• PAQ1 был выпущен 6 января 2002 года Мэттом Махони. Он использовал фиксированные веса и не включал аналоговую или разреженную модель.
• PAQ1SSE/PAQ2 был выпущен 11 мая 2003 года Сержем Оснаком. Это значительно улучшило сжатие за счет добавления этапа вторичной оценки символов (SSE) между предсказателем и кодером. SSE вводит краткий контекст и текущий прогноз и выводит новый прогноз из таблицы. Затем запись таблицы корректируется для отражения фактического значения бита.
• PAQ3N , выпущенный 9 октября 2003 г., добавил разреженную модель.
• PAQ4 , выпущенный 15 ноября 2003 года Мэттом Махони, использовал адаптивное взвешивание. PAQ5 (18 декабря 2003 г.) и PAQ6 (30 декабря 2003 г.) представляли собой незначительные улучшения, включая новую аналоговую модель. На этом этапе PAQ конкурировал с лучшими компрессорами PPM и привлек внимание сообщества специалистов по сжатию данных, что привело к большому количеству дополнительных улучшений до апреля 2004 года. Берто Дестазио настроил модели и скорректировал график дисконтирования количества битов. Йохан де Бок улучшил пользовательский интерфейс. Дэвид А. Скотт усовершенствовал арифметический кодер. Фабио Буффони улучшил скорость.
• В период с 20 мая 2004 г. по 27 июля 2004 г. Александр Ратушняк выпустил семь версий PAQAR , в которых были достигнуты значительные улучшения сжатия за счет добавления множества новых моделей, нескольких микшеров с весами, выбранными в зависимости от контекста, добавления этапа SSE к каждому выходу микшера и добавление препроцессора для улучшения сжатия исполняемых файлов Intel. PAQAR оставался лучшим компрессором до конца 2004 года, но был значительно медленнее, чем предыдущие версии PAQ.
• В период с 18 января 2005 г. по 7 февраля 2005 г. Пшемыслав Скибински выпустил четыре версии PASqDa , основанные на PAQ6 и PAQAR с добавлением препроцессора английского словаря. Он занял первое место в рейтинге Калгари, но не по большинству других показателей.
• Модифицированная версия PAQ6 выиграла Calgary Challenge 10 января 2004 года Мэтта Махони. Это было улучшено десятью последующими версиями PAQAR Александра Ратушняка. Самый последний из них был отправлен 5 июня 2006 г. и состоял из сжатых данных и исходного кода программы общим объемом 589 862 байта.
• PAQ7 был выпущен в декабре 2005 года Мэттом Махони. PAQ7 — это полная переработка PAQ6 и его вариантов (PAQAR, PAsQDa). Степень сжатия аналогична PAQAR, но в 3 раза быстрее. Однако ему не хватало x86 и словаря, поэтому он не сжимал исполняемые файлы Windows и текстовые файлы на английском языке, а также PAsQDa. Он включает модели для цветных файлов BMP, TIFF и JPEG, поэтому эти файлы сжимаются лучше. Основное отличие от PAQ6 заключается в том, что для объединения моделей используется нейронная сеть, а не смеситель градиентного спуска. Еще одной особенностью является способность PAQ7 сжимать встроенные изображения JPEG и растровые изображения в файлы Excel, Word и pdf.
• PAQ8A был выпущен 27 января 2006 г., PAQ8C - 13 февраля 2006 г. Это была экспериментальная предварительная версия ожидаемого PAQ8. Исправлено несколько проблем в PAQ7 (в некоторых случаях плохое сжатие). PAQ8A также включал модель для сжатия исполняемых файлов (x86).
• PAQ8F был выпущен 28 февраля 2006 года. PAQ8F имел три улучшения по сравнению с PAQ8A: контекстную модель с более эффективным использованием памяти, новую модель косвенного контекста для улучшения сжатия и новый пользовательский интерфейс для поддержки перетаскивания в Windows. Он не использует английский словарь, как варианты PAQ8B/C/D/E.
• PAQ8G был выпущен 3 марта 2006 года Пшемыславом Скибинским. PAQ8G — это PAQ8F с добавленными словарями и некоторыми другими улучшениями, такими как переработанный TextFilter (который не снижает производительность сжатия нетекстовых файлов).
• 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 года Биллом Петтисом. Эта версия с тех пор была перенесена на 32-битную Windows для нескольких процессоров, а также на 32- и 64-битную Linux .
• PAQ8K был выпущен 13 февраля 2007 года Биллом Петтисом. Он включает дополнительные модели для двоичных файлов.
• PAQ8L был выпущен 8 марта 2007 года Мэттом Махони. Он основан на PAQ8JD и добавляет модель DMC .
• PAQ8O был выпущен 24 августа 2007 года Андреасом Морфисом. Содержит улучшенные модели BMP и JPEG по сравнению с PAQ8L. Опционально может быть скомпилирован с поддержкой SSE2 и для 64-битной версии Linux. Алгоритм имеет заметные преимущества в производительности в 64-битной ОС.
• PAQ8P был выпущен 25 августа 2008 года Андреасом Морфисом. Содержит улучшенную модель BMP и добавляет модель WAV .
• PAQ8PX был выпущен 25 апреля 2009 года Яном Ондрусом. Он содержит различные улучшения, такие как улучшенное сжатие WAV и EXE . сжатие
• PAQ8KX был выпущен 15 июля 2009 года Яном Ондрусом. Это комбинация PAQ8K и PAQ8PX.
• PAQ8PF был выпущен 9 сентября 2009 года компанией LovePimple без исходного кода (чего требует лицензия GPL ). Он сжимает на 7% хуже, но в 7 раз быстрее по сравнению с PAQ8PX v66 (измерения проводились с текстом на английском языке размером 1 МБ).
• PAQ9A был выпущен 31 декабря 2007 года Мэттом Махони. Новая экспериментальная версия. Он не включает модели для определенных типов файлов, имеет препроцессор LZP и поддерживает файлы размером более 2 ГБ.
• ZPAQ был выпущен 12 марта 2009 года Мэттом Махони. Он использует новый формат архива, разработанный таким образом, чтобы текущая программа ZPAQ могла распаковывать архивы, созданные будущими версиями ZPAQ. (различные варианты PAQ, перечисленные выше, не имеют прямой совместимости таким образом). Это достигается путем указания алгоритма распаковки в программе с байт-кодом, которая хранится в каждом созданном архивном файле.

Премии Хаттера

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

27 октября 2006 года было объявлено. что PAQ8HP5 получил премию Hutter за сжатие человеческих знаний без потерь в размере 3416 евро .

Ратушняка 30 июня 2007 года PAQ8HP12 был награжден вторым призом Hutter в размере 1732 евро. улучшив свой предыдущий рекорд на 3,46%.

Выводы PAQ

Будучи свободным программным обеспечением , PAQ может модифицироваться и распространяться любым, у кого есть копия. Это позволило другим авторам расширить механизм сжатия PAQ и добавить новые функции, такие как графический интерфейс пользователя или повышенную скорость (за счет степени сжатия). Известные производные PAQ включают:

• WinUDA 0.291 , на основе PAQ6, но быстрее.
• UDA 0.301 , на основе алгоритма PAQ8I.
• КГБ , на базе PAQ6 (бета-версия основана на PAQ7).
• Эмилконт на базе PAQ6
• Графический интерфейс Peazip (для Windows и Linux) для LPAQ , ZPAQ и различные алгоритмы PAQ8*
• PWCM (PAQ-взвешенное смешивание контекстов) — это независимо разработанная реализация алгоритма PAQ с закрытым исходным кодом, используемого в WinRK.
• PAQCompress — это графический интерфейс пользователя для нескольких новых версий PAQ, включая последние выпуски PAQ8PX, PAQ8PXD и PAQ8PXV. Он обновляется всякий раз, когда выходит новая версия. Программное обеспечение разумно добавляет расширение к имени файла, которое можно использовать для распаковки файла с использованием правильной версии PAQ. Программное обеспечение имеет открытый исходный код.
• PerfectCompress Это программное обеспечение для сжатия с функцией UCA (ULTRA Compressed Archive). Формат сжатия, в котором использовались версии PAQ8PX v42–v65 и который теперь может использовать PAQ8PF, PAQ8KX или PAQ8PXPRE в качестве компрессора UCA по умолчанию. Кроме того, PerfectCompress может сжимать файлы в форматы PAQ8PX v42–v67, а ZPAQ, а начиная с версии 6.0, может сжимать файлы в форматы LPAQ и PAQ8PF от бета-версии 1 до бета-версии 3. В PerfectCompress v6.10 реализована поддержка сжатия для недавно выпущенного PAQ8PXPRE. В PerfectCompress 6.12 представлена ​​поддержка серии PAQ8KX.
• FrontPAQ , небольшой графический интерфейс для PAQ. Последняя версия — FrontPAQ v8, поддерживающая PAQ8PX, PAQ8PF и FP8. Программное обеспечение больше не обновляется, и пользователям рекомендуется использовать PAQCompress, в котором реализованы последние версии PAQ.

См. также

• Список форматов архивов
• Сравнение файловых архиваторов

Дальнейшее чтение

• Дэвид Саломон, Джованни Мотта (при участии Дэвида Брайанта), Справочник по сжатию данных , 5-е издание, Springer, 2009 г., ISBN   1-84882-902-7 , 5.15 PAQ, стр. 314–319
• Байрон Нолл, Нандо де Фрейтас, Перспектива машинного обучения в прогнозирующем кодировании с помощью PAQ , Университет Британской Колумбии, Ванкувер, Канада, 17 августа 2011 г.

Внешние ссылки

• Официальный сайт
• Скомпилированные двоичные файлы Linux — загрузка исполняемых файлов командной строки Linux.