Bzip2は、圧縮技術の複数のレイヤーを積み重ねて使用します。これは、圧縮時には次の順序で、解凍時には逆の順序で発生します。
- 初期データのランレングスエンコーディング（RLE）。
- Burrows–Wheeler変換（BWT）、またはブロックソート。
- Move-to-front（MTF）変換。
- MTF結果のランレングスエンコーディング（RLE）。
- ハフマンコーディング。
- 複数のハフマンテーブルからの選択。
- 単一のベース1エンコーディング。ハフマンテーブル選択の例。
- ハフマンコードのビット長のデルタエンコーディング（Δ）。
- 使用されているシンボルを示すスパースビット配列。
初期ランレングスencodingEdit
4〜255の連続する重複シンボルのシーケンスは、最初の4つのシンボルと、0〜251の繰り返し長に置き換えられます。したがって、シーケンスAAAAAAABBBBCCCDはAAAA\3BBBB\0CCCDに置き換えられます。ここで、\3と\0は、それぞれバイト値3と0を表します。シンボルのランは、ランレングスがゼロに設定されている場合でも、変換を可逆に保つために、常に4つの連続するシンボルの後に変換されます。
最悪の場合、1.25の拡張が発生する可能性があります。最良の場合、< 0.02に削減します。仕様では理論的には長さ256〜259のランをエンコードできますが、参照エンコーダーはそのような出力を生成しません。
bzip2の作成者は、RLEステップは歴史的な誤りであり、意図されたものにすぎないと述べています。元のBWT実装を病理学的ケースから保護するため。
Burrows–Wheeler transformEdit
これは、リバーシブルブロックソートです。 bzip2の中核です。ブロックは完全に自己完結型であり、入力バッファと出力バッファは同じサイズのままです。bzip2では、このステージの動作制限は900kBです。ブロックソートの場合、（概念的な）行列が作成され、行iにはバッファー全体が含まれ、i番目のシンボルから開始するように回転されます。ローテーションに続いて、マトリックスの行はアルファベット（数値）の順序でソートされます。ブロックが変換されていないときの開始位置を示す24ビットポインタが格納されます。実際には、完全なマトリックスを作成する必要はありません。むしろ、ソートはバッファ内の各位置のポインタを使用して実行されます。出力バッファは、行列の最後の列です。これにはバッファ全体が含まれますが、同じシンボルの大量の実行が含まれる可能性が高くなるように並べ替えられます。
前面に移動するtransformEdit
繰り返しますが、この変換は処理されたブロックのサイズを変更しません。ドキュメントで使用されている各記号は、配列に配置されます。シンボルが処理されると、そのシンボルは配列内のその位置（インデックス）に置き換えられ、そのシンボルは配列の先頭にシャッフルされます。その結果、すぐに繰り返されるシンボルはゼロシンボルに置き換えられ（したがって、任意のシンボルの長い実行はゼロシンボルの実行になります）、他のシンボルはローカル頻度に従って再マップされます。
多くの「自然な」データ限られた範囲内で繰り返される同一の記号が含まれています（テキストが良い例です）。 MTF変換は、頻繁に再表示されるシンボルに低い値を割り当てるため、これにより、低整数範囲の多くのシンボルを含むデータストリームが生成され、それらの多くは同一になります（異なる繰り返し入力シンボルは実際には同じ出力シンボルにマップできます）。このようなデータは、従来の圧縮方法で非常に効率的にエンコードできます。
MTFresultEditのランレングスエンコード
Move-to-Front変換の出力でのゼロの長い文字列（ BWTの出力で繰り返されるシンボルに由来する）は、ランレングスを2進数として表す2つの特別なコードRUNAとRUNBのシーケンスに置き換えられます。実際のゼロが出力にエンコードされることはありません。唯一のゼロはRUNAになります。 （実際、このステップはMTFと同時に実行されます。MTFがゼロを生成するたびに、代わりにカウンターを増やしてRUNAおよびRUNBでエンコードします。）
シーケンス0, 0, 0, 0, 0, 1はRUNA, RUNB, 1として表されます。 RUNA, RUNBは、以下で説明するように値5を表します。ランレングスコードは、別の通常のシンボルに到達することによって終了します。このRLEプロセスは、任意の長さの整数をエンコードできるため、最初のRLEステップよりも柔軟性があります（実際には、これは通常、ブロックサイズによって制限されるため、このステップは900000バイトを超える実行をエンコードしません）。ランレングスは次のようにエンコードされます。シーケンスの最初のビットに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
HuffmancodingEdit
このプロセスは、使用頻度に基づいて、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バイトを暗黙的に繰り返す）との終わりで構成されます。 -値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バイト）が必要です。 。
スパースビットarrayEdit
ビットマップは、ブロック内で使用され、ハフマンツリーに含める必要のあるシンボルを示すために使用されます。バイナリデータはバイトで表現可能な256個のシンボルすべてを使用する可能性がありますが、テキストデータは使用可能な値の小さなサブセットのみを使用し、おそらく32〜126のASCII範囲をカバーします。256個のゼロビットを格納することは、ほとんど使用されていない場合は非効率的です。スパース法が使用されます。256個のシンボルが16個の範囲に分割され、そのブロック内でシンボルが使用されている場合にのみ、16ビット配列が含まれます。これらの16の範囲のそれぞれの存在は、前面に追加の16ビットビット配列によって示されます。
ビットマップ全体は、32〜272ビットのストレージ（4〜34バイト）を使用します。対照的に、DEFLATEアルゴリズムは、ランレングスエンコーディングと追加のハフマンコーディングを使用してシンボルをゼロビット長としてエンコードすることにより、シンボルが存在しないことを示します。