bzip2

Bzip2

「Bzip」はタンパク質ドメインについては、bZIPドメインを参照してください
bzip2は、Burrows–Wheelerアルゴリズムを使用する無料のオープンソース ファイル 圧縮プログラムです。単一のファイルのみを圧縮し、ファイルアーカイバではありません。ジュリアン・スワードによって開発され、マーク・ウィーラードとミカ・スナイダーによって維持されました。 bzip2 原作者
ジュリアン・スワード
開発者
マーク・ウィーラード、フェデリコ・メーナ、ミカ・スナイダー
初回リリース
1996年7月18日; 25年前 （1996-07-18）
安定リリース
1.0.8 / 2019年7月13日 ; 2年前  （2019-07-13）
リポジトリ
1.0：https：//sourceware.org/git/bzip2.git 1.1+：https：//gitlab.com/bzip2/bzip2/
オペレーティング・システム
クロスプラットフォーム
タイプ
データ圧縮
ライセンス
BSDライクなライセンス
Webサイト
sourceware .org / bzip2 / bzip2 ファイル名拡張子 .bz2 インターネットメディアタイプ
application/x-bzip2
タイプコード Bzp2 ユニフォームタイプ識別子（UTI）
public.archive.bzip2
マジックナンバー BZh によって開発された
ジュリアン・スワード
フォーマットの種類
データ圧縮
オープンフォーマット？
はい

コンテンツ
1 歴史
2 実装
3 ファイル形式
4 効率
5 も参照してください
6 参考文献
7 外部リンク

歴史
あなたはそれに追加することによって助けることができます
スワードは、1996年7月に、コンプレッサの安定性と人気は今後数年間で成長し、バージョン0.15、BZIP2の最初のパブリックリリースをした、とスワードは後半に2000年にバージョン1.0をリリースの9年間の活動休止後2010年以降のプロジェクトの更新。2019年6月4日、FedericoMenaはbzip2プロジェクトの保守を受け入れました。 2021年6月以降、メンテナはMicahSnyderです。

実装
 「Bzip2」  
Bzip2は、互いに積み重ねられた圧縮技術のいくつかのレイヤーを使用します。これは、圧縮中は次の順序で、解凍中は逆の順序で発生します。
初期データのランレングスエンコーディング（RLE）。
Burrows–Wheeler変換（BWT）、またはブロックソート。
Move-to-Front（MTF）変換。
MTF結果のランレングスエンコーディング（RLE）。
ハフマン符号化。
複数のハフマンテーブルからの選択。
ハフマンテーブル選択の1進ベース1エンコーディング。
ハフマンコードのビット長のデルタエンコーディング（Δ）。
使用されているシンボルを示すスパースビット配列。
4〜255個の連続する重複シンボルのシーケンスは、最初の4個のシンボルと、0〜251の繰り返し長にAAAAAAABBBBCCCD置き換えられます。したがって、シーケンスは、に置き換えられます。AAAA3BBBB CCCDここで3、および はそれぞれバイト値3および0を表します。シンボルのランは、ランレングスがゼロに設定されている場合でも、変換を可逆に保つために、4つの連続するシンボルの後に常に変換されます。
最悪の場合、1.25の拡張が発生する可能性があり、最良の場合、 bzip2の作成者は、RLEステップは歴史的な誤りであり、元のBWT実装を病理学的ケースから保護することのみを目的としていると述べています。
Burrows–Wheeler変換は、bzip2のコアにあるリバーシブルブロックソートです。ブロックは完全に自己完結型であり、入力バッファと出力バッファは同じサイズのままです。bzip2では、このステージの動作制限は900kBです。ブロックソートの場合、（概念的な）行列が作成されます。この行列には、行iにバッファー全体が含まれ、i番目のシンボルから開始するように回転されます。ローテーションに続いて、マトリックスの行はアルファベット（数値）の順序でソートされます。ブロックが変換されていないときの開始位置を示す24ビットポインタが格納されます。実際には、完全なマトリックスを作成する必要はありません。むしろ、ソートはバッファ内の各位置のポインタを使用して実行されます。出力バッファは、行列の最後の列です。これにはバッファ全体が含まれますが、同じシンボルの大規模な実行が含まれる可能性が高いように並べ替えられています。
Move-to-Front変換でも、処理されたブロックのサイズは変更されません。ドキュメントで使用されている各記号は、配列に配置されます。シンボルが処理されると、そのシンボルは配列内のその位置（インデックス）に置き換えられ、そのシンボルは配列の先頭にシャッフルされます。その結果、すぐに繰り返されるシンボルはゼロシンボルに置き換えられ（したがって、任意のシンボルの長い実行はゼロシンボルの実行になります）、他のシンボルはローカル頻度に従って再マップされます。
多くの「自然な」データには、限られた範囲内で繰り返される同一の記号が含まれています（テキストが良い例です）。MTF変換は、頻繁に再表示されるシンボルに低い値を割り当てるため、これにより、低整数範囲の多くのシンボルを含むデータストリームが生成され、それらの多くは同一になります（異なる繰り返し入力シンボルは実際には同じ出力シンボルにマップできます）。このようなデータは、従来の圧縮方法で非常に効率的にエンコードできます。
Move-to-Front変換の出力にあるゼロの長い文字列（BWTの出力に繰り返されるシンボルに由来する）は、ランレングスをとして表す2つの特別なコードRUNAとRUNBのシーケンスに置き換えられます。 2進数。実際のゼロが出力にエンコードされることはありません。唯一のゼロはRUNAになります。（実際、このステップはMTFと同時に実行されます。MTFがゼロを生成する場合は常に、代わりにカウンターを増やしてRUNAおよびRUNBでエンコードします。）
シーケンス0， 0， 0， 0， 0， 1はRUNA， RUNB， 1;として表されます。RUNA， RUNB以下に説明するように、値5を表します。ランレングスコードは、別の通常のシンボルに到達することによって終了します。このRLEプロセスは、任意の長さの整数をエンコードできるため、最初のRLEステップよりも柔軟性があります（実際には、これは通常、ブロックサイズによって制限されるため、このステップでは、900 000 バイト）。ランレングスは次のようにエンコードされます。シーケンスの最初のビットに1、2番目に2、3番目に4などの場所の値を割り当て、RUNBスポットの各場所の値に2を掛け、すべてを加算します。結果の場所の値（RUNA値とRUNB値の両方）が一緒になります。これは、基数2の全単射の数え上げに似ています。したがって、シーケンスのRUNA， RUNB結果は（1 + 2×2）= 5になります。より複雑な例として、次のようになります。
RUNA RUNB RUNA RUNA RUNB（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ではゼロになります）。したがって、最後に1つのシンボルを節約できます。 of-streamマーカー（およびハフマンツリーでn − 1個のシンボルのみがコード化されている理由を説明します）。非圧縮データで1つのシンボルのみが使用される極端なケースでは、ハフマンツリーにシンボルコードはまったくなく、ブロック全体がRUNAとRUNB（1バイトを暗黙的に繰り返す）とend-ofで構成されます。 -値2のストリームマーカー。
0：RUNA、
1：RUNB、
2〜257：バイト値0〜255、
258：ストリームの終了、処理の終了（2まで低くなる可能性があります）。
いくつかの同じサイズのハフマンテーブルは、それらを使用することによる利益が追加のテーブルを含めるコストよりも大きい場合、ブロックで使用できます。少なくとも2つから最大6つのテーブルが存在でき、50のシンボルが処理される前に、最も適切なテーブルが再選択されます。これには、DEFLATEで必要とされるように、新しいテーブルを継続的に提供する必要がなく、非常に応答性の高いハフマンダイナミクスを持つという利点が前のステップのランレングスエンコーディングは、使用中の最短コードハフマンコードよりも使用の逆確率が高いコードを処理するように設計されています。
複数のハフマンテーブルが使用されている場合、各テーブル（0〜5の番号）の選択は、長さが1〜6ビットのゼロで終了するビットによってリストから実行されます。選択はテーブルのMTFリストにこの機能を使用すると、最大で約1.015の拡張が得られますが、通常はそれより小さくなります。この拡張は、より適切なハフマンテーブルを選択する利点によって大幅に影が薄くなる可能性があり、同じハフマンテーブルを引き続き使用する一般的なケースは単一ビットとして表されます。単一のエンコーディングではなく、事実上、これはハフマンツリーの極端な形式であり、各コードは前のコードの半分の確率を持ちます。
使用されている標準ハフマンテーブルのそれぞれを再構築するには、ハフマンコードのビット長が必要です。各ビット長は、前のコードのビット長に対するエンコードされた差として格納されます。ゼロビット（0）は、前のビット長を現在のコードに複製する必要があることを意味し、1ビット（1）は、さらにビットを読み取り、その値に基づいてビット長をインクリメントまたはデクリメントする必要があることを意味します。一般的なケースでは、テーブルごとのシンボルごとに1ビットが使用され、最悪の場合（長さ1から長さ20まで）には約37ビットが必要になります。以前のMTFエンコーディングの結果、コード長は2〜3ビット長（非常に頻繁に使用されるコード）で始まり、徐々に増加します。つまり、デルタ形式はかなり効率的であり、完全なハフマンテーブルごとに約300ビット（38バイト）が必要です。 。
ビットマップは、ブロック内で使用され、ハフマンツリーに含める必要があるシンボルを示すために使用されます。バイナリデータはバイトで表現可能な256個のシンボルすべてを使用する可能性がありますが、テキストデータは使用可能な値の小さなサブセットのみを使用し、おそらく32〜126のASCII範囲をカバーします。256個のゼロビットを格納することは、ほとんど使用されていない場合は非効率的です。疎な方法が使用される：256個のシンボルは、16個の範囲に分割され、シンボルがそのブロック内で使用される場合にのみ、16ビットの配列が含まれています。これらの16の範囲のそれぞれの存在は、前面にある追加の16ビットビット配列によって示されます。合計ビットマップは、32〜272ビットのストレージ（4〜34バイト）を使用します。対照的に、DEFLATEアルゴリズムは、ランレングスエンコーディングと追加のハフマンコーディングを使用してシンボルをゼロビット長としてエンコードすることにより、シンボルが存在しないことを示します。

ファイル形式
非公式の仕様はリファレンス実装からリバースエンジニアリングされていますが、bzip2の正式な仕様は存在しません。
概要として、.bz2ストリームは4バイトのヘッダーで構成され、その後に0個以上の圧縮ブロックが続き、その直後に、処理されたプレーンテキストのストリーム全体の32ビットCRCを含むストリーム終了マーカーが続きます。圧縮されたブロックはビット整列されており、パディングは発生しません。
.magic：16 = ‘BZ’署名/マジックナンバー.version：8 = Bzip2の場合は「h」（「H」uffmanコーディング）、Bzip1の場合は「0」（非推奨）.hundred_k_blocksize：8 = ‘1’ .. ‘9’ブロックサイズ100kB-900 kB（非圧縮）.compressed_magic：48 = 0x314159265359（BCD（pi））.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 kBbzip2ブロックに含めることができるプレーンテキストの最大長は約46MB（45，899，236バイト）です。これは、プレーンテキスト全体が完全に繰り返される値で構成されている場合に発生する可能性があります（.bz2この場合、結果のファイルの長さは46バイトです）。完全に251の値を含む入力を使用することにより、40バイトのさらに小さなファイルを実現できます。見かけの圧縮率は1147480.9：1です。
bzip2の圧縮ブロックは、以前のブロックを処理することなく、個別に解凍できます。BZIP2ファイルはそれで使用するための良好なフォーマット作り、並行して解凍することができることをこれは意味ビッグデータなどのクラスタコンピューティングフレームワークとアプリケーションのHadoopおよびApacheのスパーク。

効率
bzip2は、ほとんどのファイルを古いLZW（.Z）およびDeflate（.zipおよび.gz）圧縮アルゴリズムよりも効果的に圧縮しますが、かなり遅くなります。LZMAは一般に、bzip2よりもスペース効率が高く、圧縮速度がさらに遅くなりますが、解凍ははるかに高速になります。
bzip2は、100〜900 kBのサイズのブロックでデータを圧縮し、Burrows–Wheeler変換を使用して、頻繁に繰り返される文字シーケンスを同一の文字列に変換します。次に、move-to-front変換とハフマンコーディングを適用します。bzip2の祖先bzipは、ハフマンの代わりに算術符号化を使用していました。この変更は、ソフトウェア特許の制限のために行われました。
解凍は比較的高速であるため、bzip2のパフォーマンスは非対称です。圧縮に必要な長いCPU時間に動機付けられて、マルチスレッドをサポートするpbzip2と呼ばれる変更バージョンが2003年に作成され、マルチCPUおよびマルチコアコンピューターでほぼ線形の速度向上を実現しました。 2010年5月の時点で、この機能はメインプロジェクトに組み込まれ
gzipと同様に、bzip2は単なるデータコンプレッサーです。tarやZIPのようなアーカイバではありません。プログラム自体には、複数のファイル、暗号化、またはアーカイブ分割の機能はありませんが、UNIXの伝統では、これらのタスクをtarやGnuPGなどの個別の外部ユーティリティに依存しています。
grepベースのbzgrepツールは、直接第1のコンテンツを解凍することなく、圧縮されたテキストを検索することを可能にします。

も参照してください

 無料のオープンソースソフトウェアポータル
アーカイブ形式の比較
ファイルアーカイバの比較
アーカイブ形式のリスト
ファイルアーカイバのリスト
rzip

参考文献
^ bzip2 / README、 1996年7月18日（バージョン0.15）
^ “”bzip2：ホーム””。ジュリアン・スワード。なぜ使いたいのですか？それはオープンソース（BSDスタイルのライセンス）であり、私が知る限り、特許がないからです。
^ 「タグbzip2の付いた記事」。people.gnome.org。
^ “”bzip2およびlibbzip2、バージョン1.0.8″”。sourceware.org。
^ 「BZIP2フォーマット仕様」（PDF）。
^ 「 bzip2圧縮ファイルの分割サポートを提供する」。Apache SoftwareFoundation。2009 。
^ 「7-zipvsbzip2vsgzip」。
^ 「bzip2ホームページ」。1998年7月4日にオリジナルからアーカイブされました。-セクション「以前のオファリング（bzip-0.21）とどのように関連していますか？」 ^ “”compressionratings.com”。ww1.compressionratings.com。
^ 「Linuxのbzgrepコマンドと例」。GeeksforGeeks。

外部リンク
bzip2コマンド-Linux情報プロジェクト（LINFO）による
Windows用のbzip2
Windows用のグラフィカルbzip2（WBZip2）
MacBzip2（Classic MacOSの場合; Mac OS Xでは、標準のbzip2はコマンドラインで利用できます）
利用可能なさまざまな種類の並列bzip2実装の機能比較とベンチマーク
2006年10月18日にデータ圧縮ニュースブログのウェイバックマシンでアーカイブされた4つの並列bzip2実装
オリジナルのbzipコンプレッサー-特許によって制限される場合があります”