Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску
ZPAQ
Разработчики)Мэтт Махони
Стабильный выпуск
7.15 / 17 августа 2016 г . ; 4 года назад ( 2016-08-17 )
Репозиторий
Отредактируйте это в Викиданных
Написано вC ++
Операционная системаMicrosoft Windows , Linux
ПлатформаIA-32 , x86-64
ТипФайловый архиватор
ЛицензияMIT , общественное достояние
Веб-сайтmattmahoney .net / dc / zpaq .html Отредактируйте это в Викиданных

ZPAQ - это архиватор командной строки с открытым исходным кодом для Windows и Linux . Он использует формат ведения журнала или только для добавления, который можно откатить до более раннего состояния для получения более старых версий файлов и каталогов. Он поддерживает быстрое инкрементное обновление, добавляя только файлы, дата последнего изменения которых изменилась с момента предыдущего обновления. Он сжимает с использованием дедупликации и нескольких алгоритмов ( LZ77 , BWT и смешение контекста). ) в зависимости от типа данных и выбранного уровня сжатия. Чтобы сохранить прямую и обратную совместимость между версиями по мере улучшения алгоритма сжатия, он сохраняет алгоритм распаковки в архиве. Источник ZPAQ код включает в себя общественное достояние API , libzpaq , который обеспечивает сжатия и распаковки услуги C ++ приложений. Считается, что этот формат не обременен патентами .

Формат архива [ править ]

Файлы сохраняются в формате журнала ZPAQ level 2. [1] Стандарт определяет два формата - потоковую передачу и ведение журнала. Только формат ведения журнала поддерживает дедупликацию, атрибуты каталогов и несколько датированных версий файлов.

Формат потокового архива предназначен для извлечения за один проход. Архив делится на последовательность блоков, которые могут быть распакованы независимо друг от друга. Блоки делятся на сегменты, которые необходимо распаковать последовательно по порядку. Заголовок каждого блока содержит описание алгоритма распаковки. Каждый сегмент имеет заголовок, содержащий необязательное имя файла и необязательный комментарий для метаданных, таких как размер, дата и атрибуты, а также необязательный завершающий SHA-1.контрольная сумма исходных данных для проверки целостности. Если имя файла опущено, предполагается, что он является продолжением последнего указанного файла, который может находиться в предыдущем блоке. Таким образом, вставка, удаление или переупорядочение блоков в потоковом архиве приводит к выполнению тех же операций с данными, которые представляют блоки.

Формат ведения журнала состоит из последовательности транзакций или обновлений. Обновление содержит 4 типа блоков: блок заголовка транзакции, последовательность блоков данных, соответствующую последовательность таблиц фрагментов и последовательность блоков индекса. Блок заголовка транзакции содержит дату транзакции и указатель, пропускающий блоки данных, чтобы можно было быстро прочитать индекс архива. Блоки данных содержат последовательность сжатых вместе фрагментов файлов. В таблицах фрагментов указан размер и хэш SHA-1 каждого фрагмента. Блоки индекса содержат список изменений глобального индекса архива. Редактирование - это либо обновление файла, либо удаление файла. Обновление включает имя файла, дату последнего изменения, атрибуты и список указателей фрагментов в текущей и предыдущей транзакциях. Фрагменты могут использоваться более чем одним файлом.Удаление не удаляет какие-либо данные из архива, а скорее указывает на то, что файл не должен быть извлечен, если архив не откатывается к более ранней дате.

Стандарт ZPAQ не определяет алгоритм сжатия. Скорее, он определяет формат для представления алгоритма распаковки в заголовках блоков. Алгоритмы декомпрессии написаны на языке ZPAQL и хранятся в виде байтового кода, который можно интерпретировать или преобразовать непосредственно в 32- или 64-разрядный код x86 и выполнить. Программа ZPAQL состоит из 3 частей.

  • COMP - необязательная цепочка компонентов контекстного моделирования.
  • HCOMP - машинный код для вычисления контекстов для компонентов COMP.
  • PCOMP - Дополнительный машинный код для пост-обработки декодированных данных.

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

  • CONST - фиксированный прогноз.
  • CM - Контекстная модель. Контекст используется для поиска прогноза в таблице. При обновлении выбранная запись корректируется, чтобы уменьшить ошибку предсказания.
  • ICM - косвенная контекстная модель. Контекст используется для поиска 8-битного состояния, представляющего недавнюю битовую историю. История выбирает прогноз, как с CM.
  • MIX - группа прогнозов объединяется взвешенным усреднением в логистической области или log (p / (1-p)). Веса выбираются в зависимости от контекста. При обновлении веса корректируются в пользу более точных входных данных.
  • MIX2 - 2 входных MIX с весами, ограниченными суммой до 1.
  • AVG - MIX2 с фиксированным весом.
  • SSE - Оценщик вторичного символа. Ищет предсказание из интерполированной таблицы с учетом контекста и квантованное предсказание из другого компонента.
  • ISSE - Косвенная вторичная оценка символа. Контекст выбирает битовую историю, как в случае с ICM, а затем битовая история выбирает пару весов, чтобы смешать вход с константой 1.
  • MATCH - ищет предыдущее вхождение контекста и предсказывает, какой бит последует за ним, с силой, зависящей от длины совпадения.

Раздел HCOMP вычисляет контексты для компонентов в разделе COMP. Это виртуальная машина, состояние которой - 4 32-битных регистра (A, B, C, D), 16-битный счетчик программ, бит флага условия и два массива памяти, один из байтов (M) и один из 32 битов. слова (H). Начало H образует массив контекстов. Ассемблере -как программы вызывается один раз для каждого кодированного или декодированного байта с этого байта в качестве входных данных в A. Конечный контекст рассматривается в разделе Комп вычисленное контекст в сочетании с ранее видели битов текущего байта.

Дополнительная секция PCOMP используется для пост-обработки декодированных данных. Он работает на отдельной виртуальной машине, такой как HCOMP. Однако, в отличие от разделов COMP и HCOMP, которые используются как для сжатия, так и для распаковки, раздел PCOMP запускается только во время распаковки. Компрессор отвечает за выполнение обратной операции над входными данными перед кодированием.

Пример ZPAQL [ править ]

Исходный код ZPAQL использует текстовый синтаксис, при этом каждое слово, разделенное пробелами, в большинстве случаев объединяется в один байт, а комментарии заключены в скобки. Следующий пример представляет собой среднюю конфигурацию, аналогичную сжатию уровня 5. Он описывает цепочку компонентов ICM-ISSE, принимающих хешированные контексты порядков от 0 до 5, MATCH, принимающий контекст порядка 7, и в качестве последнего шага усреднение этих битовых предсказаний с использованием MIX. Постобработки нет.

comp 3 3 0 0 8 (hh hm ph pm n) 0 icm 5 (order 0...5 chain) 1 isse 13 0 2 isse 17 1 3 isse 18 2 4 isse 18 3 5 isse 19 4 6 match 22 24 (order 7) 7 mix 16 0 7 24 255 (order 1) hcomp c++ *c=a b=c a=0 (save in rotating buffer M) d= 1 hash *d=a (orders 1...5 for isse) b-- d++ hash *d=a b-- d++ hash *d=a b-- d++ hash *d=a b-- d++ hash *d=a b-- d++ hash b-- hash *d=a (order 7 for match) d++ a=*c a<<= 8 *d=a (order 1 for mix) halt end

Параметры COMP описывают размер логической базы 2 для массивов слов и байтов (hh, hm), по 8 байтов каждый в разделе HCOMP и не используются в разделе PCOMP. Пронумерованных компонентов n = 8. Компоненты принимают параметры, описывающие их размеры таблиц и входные данные. В частности, каждый ISSE принимает входные данные от предыдущего компонента, а MIX принимает входные данные от 7 компонентов, начиная с 0. Строка «5 isse 19 4» говорит, что ISSE имеет размер таблицы 2 19 + 6 битовых историй и принимает входные данные от компонента 4.

В разделе HCOMP регистры B и C указывают на 8-байтовый вращающийся массив M, а D указывает на массив из 8 слов H. M используется для хранения последних 8 байтов ввода из регистра A. C указывает на заголовок этого буфера. Инструкция HASH вычисляет:

 а = (а + * б + 512) * 773;

Таким образом, код хранит хеши контекста различного порядка в H [0] ... H [7].

Дедупликация [ править ]

При обновлении ZPAQ делит входные файлы на фрагменты, вычисляет их хэши SHA-1 и сравнивает их с хешами, хранящимися в архиве. Если есть совпадение, то предполагается, что фрагменты идентичны, и сохраняется только указатель на ранее сжатый фрагмент. В противном случае фрагмент упаковывается в блок для сжатия. Размер блока может составлять от 16 до 64 МБ в зависимости от уровня сжатия.

Файлы разбиты на фрагменты по зависимым от содержимого границам. Вместо отпечатка Рабина ZPAQ использует скользящий хэш, который зависит от последних 32 байтов, которые не предсказываются контекстом порядка 1, плюс любые предсказанные байты между ними. Если все ведущие 16 бит 32-битного хэша равны 0, то отмечается граница фрагмента. Это дает средний размер фрагмента 64 КБ.

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

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

ZPAQ имеет 5 уровней сжатия, от самого быстрого до лучшего. На любом уровне, кроме наилучшего, он использует статистику таблицы прогнозирования порядка 1, используемой для дедупликации, чтобы проверить, является ли ввод случайным. Если это так, он сохраняется без сжатия для оптимизации скорости. В противном случае он выбирает следующий алгоритм сжатия:

  • Уровень 0 - Без сжатия.
  • Уровень 1 (по умолчанию) - LZ77, сжатие путем замены повторяющихся строк указателями на предыдущие вхождения.
  • Уровень 2 - то же, что и уровень 1, но тратит больше времени на поиск лучших совпадений с использованием массива суффиксов вместо хеш-таблицы.
  • Уровень 3 - использует либо BWT, либо LZ77 для длинных совпадений, а также контекстную модель первого порядка и арифметическое кодирование для литералов в зависимости от типа файла.
  • Уровень 4 - Пробует как LZ77 (например, 3), так и BWT и выбирает тот, который сжимает лучше.
  • Уровень 5 - Использует сложную модель смешивания контекста высокого порядка с более чем 20-битными компонентами предсказания.

Кроме того, ZPAQ будет использовать преобразование E8E9 для улучшения сжатия кода x86, который обычно встречается в файлах .exe и .dll. Преобразование E8E9 сканирует инструкции CALL и JMP (шестнадцатеричные коды операций E8 и E9) и заменяет их относительные адреса абсолютными. Затем он вставляет код в раздел PCOMP для выполнения обратного преобразования.

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

В ZPAQ отсутствует исправление ошибок, но есть несколько функций, которые ограничивают повреждение в случае повреждения архива. При распаковке проверяются все хэши SHA-1. Если хэш не совпадает или возникает другая ошибка, выводится предупреждение и блок игнорируется. Блоки начинаются с 13-байтового «тега локатора», содержащего случайно выбранную, но фиксированную строку, позволяющую найти начало следующего блока путем сканирования. Если фрагмент данных потерян, то все файлы, ссылающиеся на этот фрагмент и оставшиеся фрагменты в блоке, также теряются. Если таблица фрагментов потеряна, ее можно восстановить из избыточного списка размеров фрагментов, хранящегося в соответствующем блоке данных, и путем пересчета хэшей. В этом случае проверяется второй хеш всего блока данных. Если индексный блок потерян, соответствующие файлы будут потеряны.Индексные блоки небольшие (16 КиБ), чтобы ограничить урон.

Обновления выполняются путем добавления временного заголовка транзакции и последующего обновления заголовка на последнем этапе. Если обновление прерывается, временный заголовок сигнализирует ZPAQ о том, что после него не найдено никаких полезных данных. Следующее обновление перезапишет эти лишние данные.

История [ править ]

  • 15 февраля 2009 г. - экспериментальная версия zpaq 0.01.
  • 12 марта 2009 г. - завершена спецификация zpaq 1.00, гарантирующая обратную совместимость.
  • 29 сентября 2009 г. - zpaq 1.06, спецификация обновлена ​​до версии 1.01, добавлены теги локатора для поддержки самораспаковывающихся архивов.
  • 14 октября 2009 г. - zpaq 1.09 добавляет переводчик ZPAQL в C ++ для оптимизации скорости.
  • 27 сентября 2010 г. - отдельный API libzpaq 0.01.
  • 21 января 2011 г. - pzpaq 0.01, первая многопоточная версия, позже снова включенная в zpaq.
  • 13 ноября 2011 г. - в zpaq 4.00 добавлен JIT-компилятор (ZPAQL для x86), устраняющий необходимость во внешнем компиляторе C ++ для оптимизации.
  • 1 февраля 2012 г. - zpaq 5.00, спецификация обновлена ​​до версии 2.00, чтобы разрешить пустой раздел COMP (только постобработка).
  • 28 сентября 2012 г. - zpaq 6.00, спецификация обновлена ​​до версии 2.01, добавлен формат журналирования.
  • 23 января 2013 г. - zpaq 6.19 разделяет функции разработки в отдельную программу zpaqd.
  • 20 декабря 2013 г .: zpaq 6.43. Добавляет шифрование AES.
  • 22 ноября 2014 г .: zpaq 6.56. Поддерживает удаленные многокомпонентные архивы с локальным индексом.

Связанные проекты [ править ]

  • Squash , уровень абстракции сжатия, поддерживающий множество кодеков .
  • PeaZip , архиватор, поддерживающий более 150 форматов, включая извлечение потокового формата ZPAQ.
  • fastqz , компрессор FASTQ, созданный с использованием libzpaq. [2]

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

  1. ^ Махони, М. [1] Открытый стандарт ZPAQ для сильно сжатых данных - уровень 2, 3 июня 2013 г.
  2. ^ Бонфилд Дж. К., Махони М. В. (2013) Сжатие данных секвенирования в форматах FASTQ и SAM . PLoS ONE 8 (3): e59190. DOI: 10.1371 / journal.pone.0059190

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

  • Официальный сайт
  • zpaq на GitHub
  • Введение в zpaql с изображениями в градациях серого