rzip

rzipは、900 MB の辞書ウィンドウで最初にLZ77スタイルの文字列マッチングを行い、続いて 900 kB の出力チャンクでbzip2ベースのBurrows–Wheeler 変換とエントロピー符号化 (ハフマン) を行う大規模なデータ圧縮 コンピュータプログラムです。

rzip は 2 段階で動作します。最初の段階では、入力ファイル内の潜在的に非常に長い距離 (900 MB) にわたる重複データの大きなチャンクを検出してエンコードします。2 番目の段階では、標準の圧縮アルゴリズム ( bzip2 ) を使用して、最初の段階の出力を圧縮します。

最近では、長距離の冗長性を含むファイルを圧縮する必要があることはごく一般的です。たとえば、ホーム ディレクトリのセットを圧縮する場合、複数のユーザーが同じファイルまたは非常に類似したファイルのコピーを持っている可能性があります。また、同じイメージの繰り返しコピーを含むPDFファイルなど、長距離にわたる大きな重複チャンクを含む単一のファイルを持つこともよくあります。ほとんどの圧縮プログラムはこの冗長性を利用できないため、rzip が達成できるよりもはるかに低い圧縮率になる可能性があります。

2 つのステージ間の中間インターフェースは、バイト整列されたデータ ストリームで構成され、長さとデータを含むリテラル(「add」) という 2 つのコマンドがあります。

type:8 = 0 => リテラル/カウントバイトの範囲を追加
 カウント:16 = 1..65535
 data:8..∞ = 挿入するリテラルデータ (n バイト全体)

長さとオフセットパラメータを持つ一致（「コピー」）:

type:8 = 1 => count バイトの範囲を一致/コピーします
 カウント:16 = 31..65535
 offset:32 = コピー元の位置へのオフセット

65,535 バイトを超えるリテラルまたは一致/コピーの長さは、複数の命令に分割されます。ストリームの終了は、長さゼロのリテラル/追加 (type=0、count=0) コマンドで示され、その直後に32 ビットの CRCチェックサムが続きます。

rsyncのアルゴリズムに基づくローリング チェックサム アルゴリズムは、このような大規模なデータセットから潜在的な一致を見つけるために使用されます。ハッシュ バケットがいっぱいになると、以前のハッシュ (「タグ」) は 2 度に基づいて破棄されます。^{[説明が必要]タグは、距離が増加するにつれて一致の粒度が徐々に減少し、}かなり良好なカバレッジ を提供するような方法で破棄されます。この実装では、連続する 31 バイト未満の一致長は検索されません。

rzip と他のよく知られた圧縮アルゴリズムとの主な違いは、非常に長距離の冗長性を利用できることです。gzip で使用されているよく知られたデフレート アルゴリズムは、最大32 KiB の履歴バッファを使用します。bzip2で使用されているBurrows-Wheeler 変換ブロック ソート アルゴリズムは、900 KiB の履歴に制限されています。rzip の履歴バッファは最大 900 MiB の長さで、gzip や bzip2 よりも数桁大きいです。rzip は、バックエンドとして bzip2 ライブラリを使用しているにもかかわらず、bzip2 よりもはるかに高速であることがよくあります。これは、rzip が bzip2 に縮小されたデータを供給するため、bzip2 の作業が少なくて済むためです。簡単な比較 (ただし、信頼できるベンチマークには小さすぎます) が作成されています。^{[1] [2]}

rzip はあらゆる目的に適しているわけではありません。rzip の 2 つの最大の欠点は、パイプライン化できない (したがって標準入力から読み込んだり標準出力に書き込んだりできない) ことと、大量のメモリを使用することです。大きなファイルで一般的な圧縮を実行すると、数百メガバイトのRAMが使用されることがあります。RAM の余裕が多く、非常に高い圧縮率が必要な場合は rzip を使用する必要がありますが、これらの条件が満たされない場合は、メモリをあまり消費しない gzip や bzip2 などの代替圧縮方法を rzip の代わりに使用する必要があります。パイプライン化を有効にするパッチが少なくとも 1 つあります。^[3]

rzip はもともと、Andrew Tridgellが博士研究の一環として作成したものです。

lrzip (Long Range ZIP) は rzip の改良版です。ファイル形式 ( .lrz) は rzip と互換性がありません。次のような改良点があります。

• LZMA、LZO、DEFLATE、Bzip2、ZPAQ圧縮の選択(Bzip2 のみではなく)
• 辞書の制限はなく、利用可能なRAMによっても制限されません
• 圧縮前にデータの圧縮可能性をテストする機能により、圧縮不可能なデータを圧縮しようとしてコンピュータが時間を無駄にすることを防ぐ
• 標準入力/標準出力からパイプライン化できる機能（圧縮率は低下します）
• 別のコンプレッサーで使用するために最終段階の圧縮を無効にする機能
• オプションのAES-128暗号化^[4]

lrzip ディストリビューションには、tarおよびlrztarで使用するための 2 つのプログラムが付属していますlrzuntar。

rzip64 は、複数のCPU コアを並列に使用できる非常に大きなファイル用の rzip の拡張です。ベンチマーク結果があります。^[5]しかし、最も重要なのは、rzip64 がいつでも中断できることです。これにより、実行中の圧縮タスク (大きなファイルの場合は数時間かかることもあります) は、システムメンテナンスの再起動後も完了した作業を失うことなく存続し、後で再開できます。rzip64 のファイル形式は、元の rzip と同じです。

REP は、Bulat Ziganshin による rzip アルゴリズムの代替実装であり、FreeArcアーカイバで LZMA/Tornado 圧縮アルゴリズムのプリプロセッサとして使用されています。FreeArc では、REP は長距離の一致を見つけ、残りのデータを LZMA で圧縮します。たとえば、2 GB RAM のコンピュータでは、REP は 1 GB までの距離で少なくとも 512 バイトの長さの一致を見つけ、次に LZMA は 128 MB までの距離で残りの一致を見つけます。したがって、これらが連携して動作することで、2 GB RAM の予算で可能な限り最高の圧縮が実現します。

REP はストリームの解凍と LZMA との共同作業に最適化されているため、元の RZIP 実装とはいくつかの点で異なります。まず、デフォルトでは 512 バイト以上の一致のみを検出します。これは、ベンチマークにより、これが REP+LZMA 圧縮全体にとって最適な設定であることが証明されたためです。次に、RAM の約半分の長さのスライディング ディクショナリを使用するため、解凍時に解凍されたファイルからデータを再度読み込む必要がありません。REP の利点は、計算が速く、ほぼ理想的な分布を持つ乗法ローリング ハッシュです。

最小一致長が大きい (rzip の 32 バイトに対して 512 バイト) ため、速度の最適化がさらに進み、REP は非常に高速な圧縮 (Intel i3-2100 で約 200 MB/秒) を実現します。

SREP (SuperREP) は、Tridgell の LZ 圧縮のアイデアを実装したもので、辞書を RAM に保存せず、代わりに処理されたブロックの SHA1 ハッシュを使用して内容を比較します。これにより、プログラムは利用可能な RAM の約 10 倍の大きさのファイルを圧縮できます。解凍は、ファイルの解凍された部分からデータを読み取るか、将来の一致をメモリに保存することによって実行されます (将来の LZ 圧縮アルゴリズム)。もちろん、将来の LZ 圧縮では入力ファイルを 2 回パスする必要がありますが、解凍に必要なメモリはごくわずかです。^{[引用が必要]}ある実験では、最小一致長が 512 バイトで圧縮された 22 GB のファイルと完全な 22 GB の辞書の解凍に必要な RAM はわずか 2 GB でした。^{[引用が必要]}

• アーカイブ形式のリスト、アーカイブ形式の比較
• ファイルアーカイバの一覧、ファイルアーカイバの比較

• rzip
• lrzip — rzip の改良版で、第 2 段階のbzip2圧縮をLZMA、LZO 、または第 2 段階なし (raw、辞書のみの圧縮)に置き換えることができます。作者は Con Kolivas で、'lrzip' は 'Long Range ZIP' の略であると述べています。
• rzip64 — Kay Gorontzi による、ストップ アンド ゴー モードを備えた 'rzip' の並列改良。
• Wayback Machineの REP (2016-11-19 アーカイブ) — LZMA との併用に最適化された改良された RZIP 実装
• Wayback Machineの SREP (2016-12-23 アーカイブ) — 辞書サイズよりも少ない RAM を使用する最初の LZ 圧縮機
• DataCompression.info – LZ77/LZSS とその派生