WikiDer > PAQ

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Март 2011 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

PAQ это серия сжатие данных без потерь архиваторы, прошедшие совместную разработку и занявшие верхние строчки в нескольких тестах, измеряющих степень сжатия (хотя и за счет скорости и использования памяти). Специализированные версии PAQ выиграли Приз Хаттера и Калгари Челлендж.^[1] PAQ - это бесплатно программное обеспечение распространяется в рамках Стандартная общественная лицензия GNU.^[2]

Алгоритм

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

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

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

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

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

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

Строка s сжимается до самой короткой байтовой строки, представляющей базу 256 прямой порядок байтов номер Икс в диапазоне [0, 1] такое, что P (р < s) ≤ Икс

р ≤ s), где P (р < s) - вероятность того, что случайная строка р той же длины, что и s будет лексикографически меньше, чем s. Всегда можно найти Икс так что длина Икс не более чем на один байт длиннее, чем Предел Шеннона, −log₂П(р = s) бит. Длина s хранится в заголовке архива.

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

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

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

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

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

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

• S₀ = Σ_я ш_я п_0я,
• S₁ = Σ_я ш_я п_1я,
• S = S₀ + S₁,
• P (0) = S₀ / S,
• P (1) = S₁ / S,

куда ш_я это вес я-я модель. Через PAQ3 веса были фиксированными и настраивались произвольно. (Заказ-п контексты имели вес п².) Начиная с PAQ4, веса были скорректированы адаптивно в направлении, которое уменьшило бы будущие ошибки в том же наборе контекста. Если кодируемый бит у, то регулировка веса будет:

• п_я = п_0я + п_1я,
• ошибка = у - П (1),
• ш_я ← ш_я + [(S п_1я − S₁ п_я) / (S₀ S₁)] ошибка.

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

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

• Икс_я = растянуть (P_я(1)),
• P (1) = кабачок (Σ_я ш_я Икс_я),

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

• протяжение(Икс) = ln (Икс / (1 − Икс)),
• давить(Икс) = 1 / (1 + е^−Икс) (инверсия растяжения).

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

• ш_я ← ш_я + η Икс_я (у - П (1)),

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

Большинство версий PAQ используют небольшой контекст для выбора среди наборов весов для нейронной сети. Некоторые версии используют несколько сетей, выходы которых объединены с еще одной сетью до этапов SSE. Кроме того, для каждого входного прогноза может быть несколько входов, которые нелинейный функции P_я(1) в дополнение к растяжке (P (1)).

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

Каждая модель разделяет известные части s в набор контекстов и отображает каждый контекст в битовую историю, представленную 8-битным состоянием. В версиях до PAQ6 состояние представляет собой пару счетчиков (п₀, п₁). В 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). Если счет превышает этот предел, то следующее состояние выбирается с таким же соотношением п₀ к п₁. Таким образом, если текущее состояние (п₀ = 4, п₁ = 4, последний бит = 0) и наблюдается 1, то новое состояние - нет (п₀ = 4, п₁ = 5, последний бит = 1). Скорее это (п₀ = 3, п₁ = 4, последний бит = 1).

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

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

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

Сравнение

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

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

История

Ниже перечислены основные улучшения алгоритма 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 мая по 27 июля 2004 года Александр Ратушняк выпустил семь версий PAQAR, который значительно улучшил сжатие, добавив множество новых моделей, несколько микшеров с весами, выбранными по контексту, добавив этап SSE к каждому выходу микшера и добавив препроцессор для улучшения сжатия исполняемых файлов Intel. PAQAR занимал первое место в рейтинге компрессоров до конца 2004 года, но был значительно медленнее, чем предыдущие версии PAQ.
• В период с 18 января 2005 г. по 7 февраля 2005 г. Пшемыслав Скибински выпустил четыре версии 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, поэтому сжимает эти файлы лучше. Основное отличие от PAQ6 заключается в том, что для комбинирования моделей в нем используется нейронная сеть, а не смеситель градиентного спуска. Еще одна особенность PAQ7 - это способность сжимать встроенные jpeg- и растровые изображения в файлах 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.^[3] (различные варианты PAQ, перечисленные выше, не имеют прямой совместимости таким образом). Это достигается за счет определения алгоритма распаковки в программе байт-кода, которая хранится в каждом созданном архивном файле.^[4]

Призы Hutter

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

27 октября 2006 г. было объявлено^[5] который PAQ8HP5 Выиграл Премия Хаттера за сжатие без потерь человеческих знаний из €3,416.

30 июня 2007 г. paq8hp12 получил второй приз Hutter в размере 1732 евро,^[6] улучшив свой предыдущий рекорд на 3,46%.

PAQ производные

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

• WinUDA 0.291, на основе PAQ6, но быстрее^[7]
• UDA 0,301, на основе алгоритма PAQ8I^[7]
• КГБ, на основе PAQ6^[8] (бета-версия основана на PAQ7).
• Эмильконт на основе PAQ6^[9]
• Peazip Интерфейс GUI (для Windows и Linux) для LPAQ^[10], ZPAQ и различные алгоритмы PAQ8 *^[11]
• PWCM (взвешенное смешивание контекста PAQ) - это независимо разработанная реализация алгоритма PAQ с закрытым исходным кодом, используемого в WinRK.^[12]
• PAQCompress представляет собой графический пользовательский интерфейс для нескольких новых версий PAQ, включая последние выпуски PAQ8PX, PAQ8PXD и PAQ8PXV. Он обновляется всякий раз, когда выходит новая версия. Программное обеспечение разумно добавляет расширение к имени файла, которое оно может использовать для распаковки файла с использованием правильной версии PAQ. Программное обеспечение с открытым исходным кодом.^[13]
• PerfectCompress^[14] Это программное обеспечение для сжатия, которое поддерживает UCA (ULTRA Compressed Archive). Формат сжатия с PAQ8PX v42 - v65 и теперь может использовать PAQ8PF, PAQ8KX или PAQ8PXPRE в качестве компрессора UCA по умолчанию. Кроме того, PerfectCompress может сжимать файлы с PAQ8PX v42 до v67 и ZPAQ, а начиная с версии 6.0 может сжимать файлы в LPAQ и PAQ8PF beta 1 до beta 3. PerfectCompress v6.10 представил поддержку сжатия для недавно выпущенного PAQ8PXPRE. PerfectCompress 6.12 представляет поддержку серии PAQ8KX.^[15]
• FrontPAQ, небольшой графический интерфейс для PAQ. Последняя версия - FrontPAQ v8, поддерживающая PAQ8PX, PAQ8PF и FP8. Программное обеспечение больше не обновляется, и пользователям рекомендуется использовать PAQCompress, в котором реализованы последние версии PAQ.^[16]

Смотрите также

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

Рекомендации

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

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

внешняя ссылка

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