PAQ: Алгоритмы сжатия данных без потерь и их особенности.

Введение

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

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

Строка s сжимается до кратчайшей байтовой строки, представляющей число x в системе с основанием 256 в формате big endian в диапазоне [0, 1], такое, что P(r < s) ≤ x < P(r ≤ s), где P(r < s) – это вероятность того, что случайная строка r той же длины, что и s, будет лексикографически меньше s. Всегда можно найти x, такое, что длина x не превышает предела Шеннона более чем на один байт, то есть -log2P(r = s) бит. Длина s хранится в заголовке архива. Арифметический кодировщик в PAQ реализован путем поддержания для каждой предсказательной модели нижней и верхней границы для x, изначально [0, 1]. После каждого предсказания текущий диапазон делится на две части пропорционально P(0) и P(1) – вероятности того, что следующий бит s будет равен 0 или 1 соответственно, учитывая предыдущие биты s. Затем следующий бит кодируется путем выбора соответствующего поддиапазона в качестве нового диапазона. Число x декодируется обратно в строку s путем выполнения идентичной последовательности предсказаний битов (поскольку предыдущие биты s известны). Диапазон разделяется так же, как и при сжатии. Часть диапазона, содержащая x, становится новым диапазоном, и соответствующий бит добавляется к s. В PAQ нижняя и верхняя границы диапазона представлены в 3 частях. Наиболее значащие цифры в системе с основанием 256 идентичны, поэтому их можно записать как старшие байты x. Следующие 4 байта хранятся в памяти, при этом старший байт различается. Менее значащие биты считаются равными нулю для нижней границы и единице для верхней границы. Сжатие завершается записью еще одного байта из нижней границы.

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

Некоторые версии PAQ, в частности PAsQDa, PAQAR (оба являются производными PAQ6) и PAQ8HP1–PAQ8HP8 (производные PAQ8 и победители премии Hutter) предварительно обрабатывают текстовые файлы, выполняя поиск слов во внешнем словаре и заменяя их кодами длиной от 1 до 3 байт. Кроме того, прописные буквы кодируются специальным символом, за которым следует строчная буква. В серии PAQ8HP словарь организован путем группировки синтаксически и семантически связанных слов. Это позволяет моделям использовать в качестве контекста только наиболее значимые биты кодов словаря.

Сравнение

Следующая таблица представляет собой пример из бенчмарка сжатия больших текстов, разработанного Мэттом Махони, и содержит файл размером 109 байт (1 ГБ или 0,931 ГиБ) текста английской Википедии. Программа Сжатый размер (байты) % от исходного размера Время сжатия (нс/байт) Память (МиБ) PAQ8HP8 133 423 109 64 639 1849 PPMd 183 976 014 880 256 bzip2 254 007 875 379 8 InfoZIP 322 649 703 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 с добавлением препроцессора английского словаря. Он достиг наивысшего рейтинга в корпусе Calgary, но не в большинстве других тестов. Модифицированная версия 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 и Bitmap в файлах Excel, Word и PDF. PAQ8A был выпущен 27 января 2006 года, PAQ8C — 13 февраля 2006 года. Это были экспериментальные предварительные выпуски ожидаемого PAQ8. Они исправили несколько проблем в PAQ7 (плохое сжатие в некоторых случаях). PAQ8A также включал модель для сжатия исполняемых файлов (x86). PAQ8F был выпущен 28 февраля 2006 года. PAQ8F имел 3 улучшения по сравнению с PAQ8A: более эффективную модель контекста с точки зрения использования памяти, новую косвенную модель контекста для улучшения сжатия и новый пользовательский интерфейс с поддержкой перетаскивания в Windows. Он не использует английский словарь, как варианты PAQ8B/C/D/E. PAQ8G был выпущен 3 марта 2006 года Пржемыславом Скибинским. PAQ8G представляет собой PAQ8F с добавленными словарями и некоторыми другими улучшениями в виде переработанного текстового фильтра (который не снижает производительность сжатия нетекстовых файлов). 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, перечисленные выше, не совместимы в этом отношении). Это достигается путем указания алгоритма распаковки в байт-кодовой программе, которая хранится в каждом созданном архивном файле.

The following lists the major enhancements to the PAQ algorithm. In addition, there have been a large number of incremental improvements, which are omitted. PAQ1 was released on January 6, 2002 by Matt Mahoney. It used fixed weights and did not include an analog or sparse model. PAQ1SSE/PAQ2 was released on May 11, 2003 by Serge Osnach. It significantly improved compression by adding a Secondary Symbol Estimation (SSE) stage between the predictor and encoder. SSE inputs a short context and the current prediction and outputs a new prediction from a table. The table entry is then adjusted to reflect the actual bit value. PAQ3N, released October 9, 2003 added a sparse model. PAQ4, released November 15, 2003 by Matt Mahoney used adaptive weighting. PAQ5 (December 18, 2003) and PAQ6 (December 30, 2003) were minor improvements, including a new analog model. At this point, PAQ was competitive with the best PPM compressors and attracted the attention of the data compression community, which resulted in a large number of incremental improvements through April 2004. Berto Destasio tuned the models and adjusted the bit count discounting schedule. Johan de Bock made improvements to the user interface. David A. Scott made improvements to the arithmetic coder. Fabio Buffoni made speed improvements. During the period May 20, 2004 through July 27, 2004, Alexander Ratushnyak released seven versions of PAQAR, which made significant compression improvements by adding many new models, multiple mixers with weights selected by context, adding an SSE stage to each mixer output, and adding a preprocessor to improve the compression of Intel executable files. PAQAR stood as the top ranked compressor through the end of 2004 but was significantly slower than prior PAQ versions. During the period January 18, 2005 through February 7, 2005, Przemyslaw Skibinski released four versions of PASqDa, based on PAQ6 and PAQAR with the addition of an English dictionary preprocessor. It achieved the top ranking on the Calgary corpus but not on most other benchmarks. A modified version of PAQ6 won the Calgary Challenge on January 10, 2004 by Matt Mahoney. This was bettered by ten subsequent versions of PAQAR by Alexander Ratushnyak. The most recent was submitted on June 5, 2006, consisting of compressed data and program source code totaling 589,862 bytes. PAQ7 was released December 2005 by Matt Mahoney. PAQ7 is a complete rewrite of PAQ6 and variants (PAQAR, PAsQDa). Compression ratio was similar to PAQAR but 3 times faster. However it lacked x86 and a dictionary, so it did not compress Windows executables and English text files as well as PAsQDa. It does include models for color BMP, TIFF and JPEG files, so compresses these files better. The primary difference from PAQ6 is it uses a neural network to combine models rather than a gradient descent mixer. Another feature is PAQ7's ability to compress embedded jpeg and bitmap images in Excel , Word and pdf files. PAQ8A was released on January 27, 2006, PAQ8C on February 13, 2006. These were experimental pre release of anticipated PAQ8. It fixed several issues in PAQ7 (poor compression in some cases). PAQ8A also included model for compressing (x86) executables. PAQ8F was released on February 28, 2006. PAQ8F had 3 improvements over PAQ8A: a more memory efficient context model, a new indirect context model to improve compression, and a new user interface to support drag and drop in Windows. It does not use an English dictionary like the PAQ8B/C/D/E variants. PAQ8G was released March 3, 2006 by Przemyslaw Skibinski. PAQ8G is PAQ8F with dictionaries added and some other improvements as a redesigned TextFilter (which does not decrease compression performance on non textual files)
PAQ8H was released on March 22, 2006 by Alexander Ratushnyak and updated on March 24, 2006. PAQ8H is based on PAQ8G with some improvements to the model. PAQ8I was released on August 18, 2006 by Pavel L. Holoborodko, with bug fixes on August 24, September 4, and September 13. It added a grayscale image model for PGM files. PAQ8J was released on November 13, 2006 by Bill Pettis. It was based on PAQ8F with some text model improvements taken from PAQ8HP5. Thus, it did not include the text dictionaries from PAQ8G or PGM model from PAQ8I. Serge Osnach released a series of modeling improvements: PAQ8JA on November 16, 2006, PAQ8JB on November 21, and PAQ8JC on November 28. PAQ8JD was released on December 30, 2006 by Bill Pettis. This version has since been ported to 32 bit Windows for several processors, and 32 and 64 bit Linux. PAQ8K was released on February 13, 2007 by Bill Pettis. It includes additional models for binary files. PAQ8L was released on March 8, 2007 by Matt Mahoney. It is based on PAQ8JD and adds a DMC model. PAQ8O was released on August 24, 2007 by Andreas Morphis. Contains improved BMP and JPEG models over PAQ8L. Can be optionally compiled with SSE2 support and for 64 bit Linux. The algorithm has notable performance benefits under 64 bit OS. PAQ8P was released on August 25, 2008 by Andreas Morphis. Contains improved BMP model and adds a WAV model. PAQ8PX was released on April 25, 2009 by Jan Ondrus. It contains various improvements like better WAV compression and EXE compression. PAQ8KX was released on July 15, 2009 by Jan Ondrus. It is a combination of PAQ8K with PAQ8PX. PAQ8PF was released on September 9, 2009 by LovePimple without source code (which the GPL license requires). It compresses 7% worse, but is 7 times faster compared to PAQ8PX v66 (measured with 1 MB English text)
PAQ9A was released on December 31, 2007 by Matt Mahoney. A new experimental version. It does not include models for specific file types, has an LZP preprocessor and supports files over 2 GB. ZPAQ was released on March 12, 2009 by Matt Mahoney. It uses a new archive format designed so that the current ZPAQ program will be able to decompress archives created by future ZPAQ versions (the various PAQ variants listed above are not forward compatible in this fashion). It achieves this by specifying the decompression algorithm in a bytecode program that is stored in each created archive file.

Премии Гутера

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