zip2 形式

zip2 形式

原作者	ジュリアン・スワード
開発者	マーク・ウィラード、フェデリコ・メナ、ミカ・スナイダー
初回リリース	1996年7月18日; 28年前[1] ( 1996-07-18 )
安定版リリース	1.0.8 / 2019年7月13日; 5年前 ( 2019-07-13 )
リポジトリ	https://gitlab.com/bzip2/bzip2/
オペレーティング·システム	クロスプラットフォーム[どれ？ ]
タイプ	データ圧縮
ライセンス	修正されたzlibライセンス[2]
Webサイト	ソースウェア.org/bzip2/

bzip2 は、Burrows-Wheeler アルゴリズムを使用する無料のオープンソース ファイル 圧縮プログラムです。単一のファイルのみを圧縮し、ファイル アーカイバではありません。複数のファイルの処理、暗号化、アーカイブの分割などのタスクには、別の外部ユーティリティを使用します。

bzip2 は、1996 年にJulian Sewardによって最初にリリースされました。ほとんどのファイルを、古いLZWおよびDeflate 圧縮アルゴリズムよりも効率的に圧縮しますが、低速です。bzip2 はテキスト データに特に効率的で、解凍は比較的高速です。このアルゴリズムは、ランレングス符号化(RLE)、Burrows–Wheeler 変換(BWT)、先頭移動変換(MTF)、ハフマン符号化などの複数の層の圧縮技術を使用します。bzip2 は 100 ～ 900 kB のブロックでデータを圧縮し、Burrows–Wheeler 変換を使用して、頻繁に繰り返される文字列を同一文字の文字列に変換します。次に、先頭移動変換とハフマン符号化が適用されます。圧縮のパフォーマンスは非対称で、解凍の方が圧縮よりも高速です。

このアルゴリズムは最初のリリース以来、複数のメンテナーを経て、2021 年 6 月から Micah Snyder がメンテナーを務めています。このアルゴリズムには、マルチスレッドを使用してマルチ CPU およびマルチコア コンピューターでの圧縮速度を向上させる pbzip2 など、いくつかの変更が加えられています。

bzip2 は、圧縮されたブロックを以前のブロックを処理しなくても解凍できるため、 HadoopやApache Sparkなどのクラスター コンピューティングフレームワークを使用したビッグ データアプリケーションでの使用に適しています。

Sewardは1996年7月にbzip2のバージョン0.15を初めて公開しました。圧縮プログラムの安定性と人気はその後数年間で高まり、Sewardは2000年後半にバージョン1.0をリリースしました。^{[本文では未確認]} 2010年以来9年間プロジェクトの更新が中断されていましたが、2019年6月4日にFederico Menaがbzip2プロジェクトのメンテナシップを受け入れました。^[4] 2021年6月以降、メンテナはMicah Snyderです。^[5]

bzip2 は、互いに積み重ねられた複数の層の圧縮技術を使用します。圧縮時には次の順序で実行され、解凍時にはその逆の順序で実行されます。

1. 初期データのランレングス符号化(RLE)。
2. Burrows–Wheeler 変換(BWT)、またはブロックソート。
3. 最前面へ移動(MTF) 変換。
4. MTF 結果のランレングス符号化 (RLE)。
5. ハフマン符号化。
6. 複数のハフマン テーブルの選択。
7. ハフマン テーブル選択の単項 1進エンコード。
8. ハフマンコードのビット長のデルタ符号化(Δ)。
9. 使用されているシンボルを示すスパースビット配列。

4 ～ 255 個の連続する重複シンボルのシーケンスは、最初の 4 個のシンボルと 0 ～ 251 の繰り返し長さに置き換えられます。したがって、シーケンスはAAAAAAABBBBCCCDに置き換えられます。AAAA\3BBBB\0CCCDここで、\3と は\0それぞれバイト値 3 と 0 を表します。連続するシンボルは、連続長が 0 に設定されている場合でも、4 個の連続するシンボルの後は常に変換され、変換を可逆的に維持します。

最悪の場合、1.25 の拡大が起こり、最良の場合、0.02 未満に縮小します。仕様では理論的には長さ 256 ～ 259 の連続をエンコードできますが、リファレンス エンコーダーはそのような出力を生成しません。

bzip2の作者は、RLEステップは歴史的な間違いであり、元のBWT実装を異常なケースから保護することのみを目的としていたと述べています。^[6]

Burrows-Wheeler 変換は、bzip2 の中核をなす可逆ブロック ソートです。ブロックは完全に自己完結的で、入力バッファと出力バッファは同じサイズのままです。bzip2 では、このステージの動作制限は900 kB です。ブロック ソートでは、(概念的な) 行列が作成されます。この行列の行iには、 i番目のシンボルから始まるように回転されたバッファ全体が含まれます。回転後、行列の行はアルファベット順 (数値順) にソートされます。ブロックが未変換の場合の開始位置を示す 24 ビットのポインタが格納されます。実際には、行列全体を作成する必要はありません。むしろ、ソートはバッファ内の各位置のポインタを使用して実行されます。出力バッファは行列の最後の列です。この列にはバッファ全体が含まれますが、同じシンボルが大量に連続して含まれるように並べ替えられます。

先頭への移動変換では、処理されたブロックのサイズは変更されません。ドキュメントで使用されている各シンボルは、配列内に配置されます。シンボルが処理されると、配列内の位置 (インデックス) に置き換えられ、そのシンボルは配列の先頭にシャッフルされます。その結果、すぐに繰り返されるシンボルはゼロ シンボルに置き換えられ (任意のシンボルの長い連続はゼロシンボルの連続になります)、他のシンボルはローカル頻度に従って再マップされます。

多くの「自然な」データには、限られた範囲内で繰り返される同一のシンボルが含まれています (テキストが良い例です)。MTF 変換では、頻繁に繰り返されるシンボルに低い値が割り当てられるため、低い整数範囲の多数のシンボルを含むデータ ストリームが生成され、その多くは同一のシンボルです (異なる繰り返し入力シンボルは、実際には同じ出力シンボルにマップできます)。このようなデータは、従来の圧縮方法で非常に効率的にエンコードできます。

先頭に移動変換の出力内の長いゼロの文字列 (BWT の出力内の繰り返しシンボルから生成) は、2 つの特殊コード RUNA と RUNB のシーケンスに置き換えられます。これらは、ランレングスを 2 進数で表します。実際のゼロは出力にエンコードされません。単独のゼロは RUNA になります。(この手順は実際には MTF と同時に実行されます。MTF がゼロを生成するときは常に、代わりにカウンターを増やして RUNA と RUNB でエンコードします。)

このシーケンスは;0, 0, 0, 0, 0, 1と表現されます。 は、以下に説明するように、値 5 を表します。ランレングスコードは、別の通常のシンボルに到達することで終了します。この RLE プロセスは、任意の長さの整数をエンコードできるため、最初の RLE ステップよりも柔軟性があります (実際には、これは通常、ブロックサイズによって制限されるため、このステップでは、1 を超えるランはエンコードされません)。RUNA, RUNB, 1RUNA, RUNBランレングスは次のようにエンコードされます。シーケンスの最初のビットに 1、2 番目のビットに 2、3 番目のビットに 4 などを割り当て、RUNB スポットの各位置の値を 2 倍にして、結果の位置の値 (RUNA 値と RUNB 値の両方) をすべて加算します。これは、2 を底とする全単射の記数法に似ています。したがって 、シーケンスのRUNA, RUNB値は (1 + 2 × 2) = 5 になります。より複雑な例として、次の例を示します。

ルナ・ルナ・ルナ・ルナ・ルナ（ABAAB）
   1 2 4 8 16
   1 4 4 8 32 = 49

このプロセスでは、使用頻度に基づいて、0～258 の範囲の固定長シンボルを可変長コードに置き換えます。頻繁に使用されるコードは短くなり (2～3 ビット)、まれなコードには最大 20 ビットが割り当てられます。コードは慎重に選択され、ビットのシーケンスが別のコードと混同されることがないようにしています。

ストリーム終了コードは特に興味深いものです。非圧縮データでn 個の異なるバイト (シンボル) が使用されている場合、ハフマン コードは 2 つの RLE コード (RUNA と RUNB)、n − 1 個のシンボル コード、および 1 つのストリーム終了コードで構成されます。前の 2 つの手順での MTF と RLE エンコードを組み合わせた結果により、MTF テーブルの最初のシンボル (通常の MTF では 0) を明示的に参照する必要がなくなり、ストリーム終了マーカー用に 1 つのシンボルが節約されます (ハフマンツリーでn − 1 個のシンボルのみがコード化される理由も説明されます)。非圧縮データで 1 つのシンボルのみが使用される極端なケースでは、ハフマン ツリーにシンボル コードがまったく存在せず、ブロック全体が RUNA と RUNB (暗黙的に 1 バイトを繰り返す) と値 2 のストリーム終了マーカーで構成されます。

0: ルナ、

1: ランブ、

2～257: バイト値0～255、

258: ストリームの終了、処理の終了 (2 まで下がる可能性があります)。

ブロックでは、同じサイズのハフマン テーブルを複数使用できます。ただし、それらの使用による利点が、追加のテーブルを含めるコストよりも大きい場合です。少なくとも 2 つ、最大 6 つのテーブルが存在でき、50 シンボルが処理される前に最も適切なテーブルが再選択されます。この方法には、DEFLATE で必要となるように、継続的に新しいテーブルを提供する必要がなく、応答性の高いハフマン ダイナミクスを実現できるという利点があります。前の手順のランレングス エンコーディングは、使用中の最短コード ハフマン コードよりも使用確率の逆数が高いコードを処理するように設計されています。

複数のハフマン テーブルが使用されている場合、各テーブル (0 から 5 の番号が付けられている) は、長さが 1 から 6 ビットのゼロ終端ビットによってリストから選択されます。選択は、テーブルのMTFリストに対して行われます。この機能を使用すると、最大で約 1.015 の拡張が実現されますが、通常はそれより小さくなります。この拡張は、より適切なハフマン テーブルを選択できる利点によって大幅に影を潜めてしまう可能性があり、同じハフマン テーブルを引き続き使用する一般的なケースは、1 ビットとして表されます。これは、単項エンコードではなく、実質的にはハフマン ツリーの極端な形式であり、各コードは前のコードの半分の確率を持ちます。

使用される標準的なハフマン テーブルをそれぞれ再構築するには、ハフマン コードのビット長が必要です。各ビット長は、前のコードのビット長とのエンコードされた差として格納されます。ビットが 0 の場合、前のビット長を現在のコードに複製する必要があります。ビットが 1 の場合、さらに 1 ビットを読み取り、その値に基づいてビット長を増分または減分する必要があります。一般的なケースでは、テーブルごとにシンボルごとに 1 ビットが使用され、最悪のケース (長さ 1 から長さ 20 まで) では約 37 ビットが必要になります。以前の MTF エンコードの結果、コード長は 2 ～ 3 ビット (非常に頻繁に使用されるコード) から始まり、徐々に増加します。つまり、デルタ形式はかなり効率的で、完全なハフマン テーブルごとに約 300 ビット (38 バイト) が必要です。

ビットマップは、ブロック内で使用されているシンボルを示し、ハフマン ツリーに含める必要があるシンボルを示します。バイナリ データでは、1 バイトで表現できる 256 個のシンボルがすべて使用される可能性がありますが、テキスト データでは、使用可能な値の小さなサブセットのみが使用されます。これは、おそらく32 ～ 126 のASCII範囲に相当します。256 個のゼロ ビットがほとんど使用されない場合は、256 個のゼロ ビットを格納することは非効率的です。スパースメソッドが使用されます。つまり、256 個のシンボルは 16 の範囲に分割され、そのブロック内でシンボルが使用されている場合にのみ、16 ビット配列が含まれます。これらの 16 個の各範囲の存在は、先頭の追加の 16 ビット ビット配列によって示されます。ビットマップ全体では、32 ～ 272 ビットのストレージ (4 ～ 34 バイト) が使用されます。対照的に、DEFLATEアルゴリズムでは、ランレングス エンコーディングと追加のハフマン コーディングを使用して、シンボルをゼロ ビット長としてエンコードすることで、シンボルが存在しないことを示します。

bzip2の正式な仕様は存在しないが、非公式の仕様はリファレンス実装からリバースエンジニアリングされている。^[7]

概要としては、.bz2ストリームは 4 バイトのヘッダー、それに続く 0 個以上の圧縮ブロック、そしてその直後に処理されたプレーンテキスト全体のストリームに対する 32 ビット CRC を含むストリーム終了マーカーで構成されます。圧縮ブロックはビット整列されており、パディングは発生しません。

.magic:16 = 'BZ' 署名/マジックナンバー
.version:8 = 'h' は Bzip2 ('H'uffman コーディング)、'0' は Bzip1 (非推奨)
.hundred_k_blocksize:8 = '1'..'9' ブロックサイズ 100 kB-900 kB (非圧縮)

.compressed_magic:48 = 0x314159265359 (BCD (円周率))
.crc:32 = このブロックのチェックサム
.randomised:1 = 0=>通常、1=>ランダム化（非推奨）
.origPtr:24 = 逆変換後の BWT への開始ポインタ
.huffman_used_map:16 = ビットマップ、16 バイトの範囲、存在/非存在
.huffman_used_bitmaps:0..256 = ビットマップ、使用されているシンボルの有無（16 の倍数）
.huffman_groups:3 = 2..6 使用されている異なるハフマンテーブルの数
.selectors_used:15 = ハフマンテーブルが交換される回数（各 50 シンボル）
*.selector_list:1..6 = MTF されたハフマン テーブルのゼロ終了ビット ラン (0..62) (*selectors_used)
.start_huffman_length:5 = 0..20 ハフマンデルタの開始ビット長
*.delta_bit_length:1..40 = 0=>次のシンボル; 1=>長さを変更
                                                { 1=>長さを減少; 0=>長さを増加 } (*(シンボル+2)*グループ)
.contents:2..∞ = ブロックの終わりまでのハフマンエンコードされたデータストリーム（最大 7372800 ビット）

.eos_magic:48 = 0x177245385090 (BCD sqrt(pi))
.crc:32 = ストリーム全体のチェックサム
.padding:0..7 = バイト全体に揃える

第 1 段階の RLE 圧縮 (上記参照) により、単一の 900 kB bzip2 ブロックに格納できるプレーンテキストの最大長は約 46 MB (45,899,236 バイト) になります。これは、プレーンテキスト全体が繰り返し値のみで構成されている場合 (.bz2この場合、結果のファイルの長さは 46 バイト) に発生します。251 の値のみを含む入力を使用すると、さらに小さい 40 バイトのファイルを実現できます。この場合、見かけの圧縮率は 1147480.9:1 になります。

bzip2の圧縮ブロックは、前のブロックを処理せずに解凍できます。つまり、bzip2ファイルは並列に解凍できるため、HadoopやApache Sparkなどのクラスターコンピューティングフレームワークを使用したビッグデータアプリケーションで使用するのに適した形式です。^[8]

bzip2は、ほとんどのファイルを古いLZW（.Z）やDeflate（.zipと.gz）圧縮アルゴリズムよりも効率的に圧縮しますが、速度はかなり遅くなります。LZMAは一般的にbzip2よりもスペース効率に優れていますが、圧縮速度はさらに遅くなりますが、解凍は高速です。^[9]

bzip2 は 100 から 900 kBのサイズのブロックにデータを圧縮し、Burrows-Wheeler 変換を使用して、頻繁に繰り返される文字列を同一文字の文字列に変換します。次に、先頭に移動変換とハフマン符号化を適用します。bzip2 の祖先であるbzip は、ハフマンの代わりに算術符号化を使用していました。この変更は、ソフトウェア特許の制限のために行われました。^[10] bzip2 と共通の祖先とアルゴリズムセットを共有する最新の圧縮プログラムであるbzip3 ^[11]は、算術符号化に戻りました。

bzip2のパフォーマンスは非対称で、解凍は比較的高速です。圧縮に長い時間がかかることから、2003年にpbzip2と呼ばれる修正版が作成されました。これは、マルチスレッドを使用してファイルを複数のチャンクにエンコードし、マルチCPUおよびマルチコアコンピューターでほぼ線形の速度向上を実現しました。^[12] 2010年5月現在^{[アップデート]}、この機能はメインプロジェクトに組み込まれていません。

gzipと同様に、 bzip2 はデータ圧縮プログラムにすぎません。tarや ZIP のようなアーカイバではありません。 bzip2 ファイル形式は、複数のファイルの内容を 1 つの圧縮ファイルに格納することをサポートしておらず、プログラム自体にも複数のファイル、暗号化、アーカイブ分割の機能はありません。UNIX の伝統では、アーカイブは別のプログラムでアーカイブを生成し、それを bzip2 で圧縮することで実行できます。また、アーカイブの解除は、圧縮されたアーカイブ ファイルを bzip2 で解凍し、別のプログラムで解凍することで実行できます。一部のアーカイバには圧縮と解凍のサポートが組み込まれているため、アーカイブの圧縮や解凍に bzip2 プログラムを使用する必要はありません。 GnuPGにも bzip2 圧縮と解凍のサポートが組み込まれています。

grepベースのツールbzgrepを使用すると、最初に内容を解凍する必要なく、圧縮されたテキストを直接検索できます。^[13]

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

• bzip2 コマンド - Linux 情報プロジェクト (LINFO)
• Windows 用の bzip2
• Windows 用グラフィカル bzip2 (WBZip2)
• MacBzip2 ( Classic Mac OS用。Mac OS Xでは、標準の bzip2 がコマンドラインで使用可能)
• さまざまな種類の並列 bzip2 実装の機能比較とベンチマークが利用可能
• 4 つの並列 bzip2 実装は、2006 年 10 月 18 日にThe Data Compression News Blog のWayback Machineにアーカイブされました。
• オリジナルのbzip圧縮ソフト - 特許によって制限される可能性がある