ZPAQ
「ZPAQ」
ZPAQは、WindowsおよびLinux用のオープンソースの コマンドライン アーカイバです。ジャーナリング形式または追加専用形式を使用しており、以前の状態にロールバックして、古いバージョンのファイルとディレクトリを取得できます。前回の更新以降に最終更新日が変更されたファイルのみを追加することにより、高速増分更新をサポートします。重複排除といくつかのアルゴリズム（LZ77、BWT、コンテキストミキシング）を使用して圧縮します）データ型と選択した圧縮レベルによって異なります。圧縮アルゴリズムが改善されたときにバージョン間の上位互換性と下位互換性を維持するために、解凍アルゴリズムがアーカイブに保存されます。ZPAQのソースコードは、パブリックドメイン API、libzpaqに圧縮と解凍のサービスを提供し、C ++アプリケーションを。このフォーマットは、特許によって妨げられていないと考えられています。 ZPAQ 開発者
マットマホニー
安定したリリース
7.15 / 2016年8月17日 ; 4年前 （2016-08-17）
リポジトリ
github .com / zpaq / zpaq
で書かれている
C ++
オペレーティング・システム
Microsoft Windows、Linux
プラットホーム
IA-32、x86-64
タイプ
ファイルアーカイバ
ライセンス
MIT、パブリックドメイン
Webサイト
mattmahoney .net / dc / zpaq .html
コンテンツ
1 アーカイブ形式
1.1 ZPAQLの例 1.2 重複排除 1.3 圧縮 1.4 エラー回復
2 歴史
3 関連プロジェクト
4 参考文献
5 外部リンク
アーカイブ形式
ファイルは、ZPAQレベル2ジャーナリング形式で保存されます。この規格では、ストリーミングとジャーナリングの2つの形式が定義されています。ジャーナリング形式のみが、重複排除、ディレクトリ属性、および複数の日付の付いたファイルバージョンをサポートします。
ストリーミングアーカイブ形式は、シングルパスで抽出されるように設計されています。アーカイブは、独立して並行して解凍できる一連のブロックに分割されます。ブロックはセグメントに分割され、順番に順番に解凍する必要が各ブロックヘッダーには、解凍アルゴリズムの説明が含まれています。各セグメントには、オプションのファイル名と、サイズ、日付、属性などのメタデータのオプションのコメントを含むヘッダーと、整合性チェックのための元のデータのオプションの末尾のSHA-1チェックサムがファイル名が省略されている場合は、最後に名前が付けられたファイルの続きであると見なされます。これは、前のブロックにある可能性がしたがって、ストリーミングアーカイブ内のブロックを挿入、削除、または並べ替えると、ブロックが表すデータに対して同じ操作を実行する効果が
ジャーナリング形式は、一連のトランザクションまたは更新で構成されます。更新には、トランザクションヘッダーブロック、データブロックのシーケンス、対応するフラグメントテーブルのシーケンス、およびインデックスブロックのシーケンスの4種類のブロックが含まれます。トランザクションヘッダーブロックには、トランザクションの日付と、データブロックをスキップするポインターが含まれているため、アーカイブインデックスをすばやく読み取ることができます。データブロックには、一緒に圧縮された一連のファイルフラグメントが含まれています。フラグメントテーブルは、各フラグメントのサイズとSHA-1ハッシュを示します。インデックスブロックには、グローバルアーカイブインデックスの編集リストが含まれています。編集は、ファイルの更新またはファイルの削除のいずれかです。更新には、ファイル名、最終変更日、属性、および現在および以前のトランザクションへのフラグメントポインターのリストが含まれます。フラグメントは複数のファイルで共有される場合が削除してもアーカイブからデータは削除されませんが、アーカイブが以前の日付にロールバックされない限り、ファイルが抽出されないことを示します。
ZPAQ標準では、圧縮アルゴリズムは指定されむしろ、ブロックヘッダーで解凍アルゴリズムを表すための形式を指定します。解凍アルゴリズムはZPAQLと呼ばれる言語で記述され、32ビットまたは64ビットのx86コードに直接解釈または変換して実行できるバイトコードとして格納されます。ZPAQLプログラムには3つの部分が
COMP-コンテキストモデリングコンポーネントのオプションのチェーン。
HCOMP-COMPコンポーネントのコンテキストを計算するためのマシンコード。
PCOMP-デコードされたデータを後処理するためのオプションのマシンコード。
COMPモデルは、算術符号化を使用して一度に1ビットを圧縮するPAQに基づいています。コンポーネントには9種類各コンポーネントは、コンテキストと、場合によっては前のコンポーネントの予測を取得し、次のビットが1になる予測または確率を出力します。最後のコンポーネントの出力は算術コード化されます。コンポーネントタイプは次のとおりです。
CONST-固定予測。
CM-コンテキストモデル。コンテキストは、テーブル内の予測を検索するために使用されます。更新時に、選択したエントリが調整され、予測エラーが減少します。
ICM-間接コンテキストモデル。コンテキストは、最近のビット履歴を表す8ビットの状態を検索するために使用されます。履歴は、CMと同様に予測を選択します。
MIX-予測のグループは、ロジスティックドメインでの加重平均、またはlog（p /（1-p））によって結合されます。重みはコンテキストによって選択されます。更新時に、より正確な入力を優先するように重みが調整されます。
MIX2-1に追加するように制約された重みを持つ2入力MIX。
AVG-固定ウェイトのMIX2。
SSE-セカンダリシンボル推定器。コンテキストと別のコンポーネントからの量子化された予測を指定して、補間されたテーブルから予測を検索します。
ISSE-間接的な二次シンボル推定器。コンテキストはICMの場合と同様にビット履歴を選択し、次にビット履歴は重みのペアを選択して入力を定数1と混合します。
MATCH-コンテキストの前の出現を検索し、一致の長さに応じた強さで、続くビットを予測します。
HCOMPセクションは、COMPセクションのコンポーネントのコンテキストを計算します。これは、状態が4つの32ビットレジスタ（A、B、C、D）、16ビットのプログラムカウンタ、条件フラグビット、および2つのメモリアレイ（1つはバイト（M）、もう1つは32ビット）である仮想マシンです。単語（H）。Hの先頭は、コンテキストの配列を形成します。アセンブリ言語COMP部から見A.でプログラム様を入力としてそのバイトと各符号化又は復号化バイトのために一度呼び出され、最終的なコンテキストは、現在のバイトの先に見られたビットと組み合わさ計算コンテキストです。
オプションのPCOMPセクションは、デコードされたデータの後処理に使用されます。HCOMPのような別の仮想マシンで実行されます。ただし、圧縮と解凍の両方に使用されるCOMPセクションとHCOMPセクションとは異なり、PCOMPセクションは解凍中にのみ実行されます。コンプレッサーは、コーディングの前に入力データに対して逆の操作を実行する責任が
ZPAQLの例
ZPAQLソースコードはテキスト構文を使用し、ほとんどの場合、スペースで区切られた各単語は1バイトにアセンブルされ、コメントは括弧で囲まれています。次の例は、レベル5の圧縮と同様の中間構成です。これは、0から5のオーダーのハッシュコンテキストを取得するコンポーネントのICM-ISSEチェーン、7次のコンテキストを取得するMATCH、および最後のステップとして、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パラメーターは、ワード配列とバイト配列（hh、hm）の対数ベースの2サイズを記述します。HCOMPセクションではそれぞれ8バイトであり、PCOMPセクションでは使用されません。n = 8個の番号付きコンポーネントがコンポーネントは、テーブルのサイズと入力を説明するパラメーターを取ります。特に、各ISSEは前のコンポーネントから入力を受け取り、MIXは0から始まる7つのコンポーネントから入力を受け取ります。「5isse 19 4」の行は、ISSEのテーブルサイズが2 19 +6ビット履歴であることを示しています。コンポーネント4から入力を受け取ります。
HCOMPセクションでは、レジスタBとCは8バイトの回転配列Mを指し、Dは8ワードの配列Hを指します。MはAレジスタからの入力の最後の8バイトを格納するために使用されます。Cは、このバッファーの先頭を指します。HASH命令は以下を計算します。
a =（a + * b + 512）* 773;
したがって、コードはさまざまな順序のコンテキストハッシュをH … H に格納します。
重複排除
更新時に、ZPAQは入力ファイルをフラグメントに分割し、SHA-1ハッシュを計算して、アーカイブに保存されているハッシュと比較します。一致する場合、フラグメントは同一であると見なされ、以前に圧縮されたフラグメントへのポインターのみが格納されます。それ以外の場合、フラグメントは圧縮されるブロックにパックされます。ブロックサイズは、圧縮レベルに応じて最大16 MiB〜64MiBになります。
ファイルは、コンテンツに依存する境界でフラグメントに分割されます。ZPAQは、Rabinフィンガープリントではなく、次数1のコンテキストで予測されない最後の32バイトと、その間の予測バイトに依存するローリングハッシュを使用します。32ビットハッシュの先頭の16ビットがすべて0の場合、フラグメント境界がマークされます。これにより、平均フラグメントサイズは64KiBになります。
ローリングハッシュは、可能な各順序1のコンテキストで最後に表示されたバイトを含む256バイトのテーブルを使用します。ハッシュは、次のバイトを追加してから、バイトが予測された場合は奇数定数、バイトが予測されなかった場合は4の倍数ではない偶数を乗算することによって更新されます。
圧縮
ZPAQには、最速から最高までの5つの圧縮レベルが最良のレベルを除いて、重複排除に使用される1次予測テーブルの統計を使用して、入力がランダムに表示されるかどうかをテストします。その場合、速度の最適化として圧縮せずに保存されます。
ZPAQは、E8E9変換を使用して、.exeファイルおよび.dllファイルに通常見られるx86コードの圧縮を改善します。E8E9変換は、CALLおよびJMP命令（オペコードE8およびE9 hex）をスキャンし、それらの相対アドレスを絶対アドレスに置き換えます。次に、PCOMPセクションにコードを挿入して、逆変換を実行します。
エラー回復
ZPAQにはエラー訂正がありませんが、アーカイブが破損した場合の損傷を制限するいくつかの機能が解凍時に、すべてのSHA-1ハッシュがチェックされます。ハッシュが一致しない場合、またはその他のエラーが発生した場合、警告が出力され、ブロックは無視されます。ブロックは、ランダムに選択されたが固定された文字列を含む13バイトの「ロケータータグ」で始まり、スキャンによって次のブロックの開始を見つけることができます。データフラグメントが失われると、そのフラグメントを参照しているすべてのファイルとブロック内の残りのフラグメントも失われます。フラグメントテーブルが失われた場合、対応するデータブロックに格納されているフラグメントサイズの冗長リストから、ハッシュを再計算することで回復できます。この場合、データブロック全体の2番目のハッシュがチェックされます。インデックスブロックが失われると、対応するファイルが失われます。損傷を制限するために、インデックスブロックは小さい（16 KiB）。
更新は、一時的なトランザクションヘッダーを追加し、最後のステップとしてヘッダーを更新することによって処理されます。更新が中断された場合、一時ヘッダーはZPAQに、その後に有用なデータが見つからないことを通知します。次の更新では、この余分なデータが上書きされます。
歴史
2009年2月15日-zpaq0.01実験リリース。
2009年3月12日-zpaq1.00仕様が完成し、下位互換性が保証されました。
2009年9月29日-zpaq1.06、v1.01に更新された仕様は、自己解凍アーカイブをサポートするためにロケータータグを追加します。
2009年10月14日-zpaq1.09は、速度の最適化としてZPAQLをC ++トランスレーターに追加します。
2010年9月27日-個別のlibzpaq0.01API。
2011年1月21日-pzpaq0.01、最初のマルチスレッドバージョン、後でzpaqに組み込まれました。
2011年11月13日-zpaq4.00、JITコンパイラー（ZPAQLからx86）を追加し、最適化のための外部C ++コンパイラーの必要性を排除します。
2012年2月1日-zpaq5.00、空のCOMPセクションを許可するように仕様がv2.00に更新されました（後処理のみ）。
2012年9月28日-zpaq6.00、仕様がv2.01に更新され、ジャーナリング形式が追加されました。
2013年1月23日-zpaq6.19は、開発関数を別のプログラムzpaqdに分割します。
関連プロジェクト
Squash、多くのコーデックをサポートする圧縮抽象化レイヤー。
PeaZip、ZPAQストリーミングフォーマット抽出を含む150以上のフォーマットをサポートするアーカイバ。
fastqz、libzpaqを使用して構築されたFASTQコンプレッサー。
zpaqfranz、深刻なバックアップおよび災害復旧マネージャーのためのスイスアーミーナイフ。
wcx_zpaq、Total Commander用のパッカープラグイン（wcx）。
参考文献
^ Mahoney、M。 高度に圧縮されたデータのZPAQオープンスタンダード-レベル2、2013年6月3日 ^ Bonfield JK、Mahoney MV（2013） FASTQおよびSAM形式のシーケンスデータの圧縮。PLoS ONE 8（3）：e59190。doi：10.1371 / journal.pone.0059190 ^ ” ZPAQ”。トータルコマンダーフォーラム。
外部リンク
公式ウェブサイト
zpaqのGitHubの
グレースケール画像を使用したzpaqlの概要”