2. 圧縮表現の概要 (Compressed Representation Overview)
2. 圧縮表現の概要 (Compressed Representation Overview)
圧縮データセット (Compressed Data Set) は、ヘッダー (Header) と一連のメタブロック (Meta-blocks) で構成されます。各メタブロックは、入力バイトのシーケンスを圧縮します。ヘッダーには、事前にわかっている場合は非圧縮データのサイズが含まれ、それ以外の場合はゼロが含まれます。したがって、ヘッダーバイトがゼロの圧縮ストリームを持つことは合法です。
メタブロックは、メタブロックヘッダー (Meta-block Header) とメタブロックデータ (Meta-block Data) で構成されます。メタブロックヘッダーは、データ部分をどのように解釈すべきかを記述します。データ部分のサイズと、データが非圧縮か最後のメタブロックかを示す 2 ビットが含まれます。メタブロックデータの解釈は、これらのビットに依存します。
メタブロックの非圧縮サイズはゼロでもかまいません。たとえば、非圧縮タイプの前のメタブロックの後に空のメタブロックが送信されたり、単にデータの終了を通知したりする場合があります。
メタブロックには 3 つの異なる種類があります:
圧縮メタブロック (Compressed meta-blocks): これらのメタブロックには、LZ77 プレフィックスコード化されたデータ (LZ77 Prefix-Coded Data) が含まれます。各圧縮メタブロックは、プレフィックスコードセクション (Prefix Code Section) とデータセクション (Data Section) に分割されます。プレフィックスコードセクションには、データセクションで使用されるプレフィックスコードが含まれます。データセクションには、LZ77 後方参照 (LZ77 Backward References)、リテラル (Literals)、および静的辞書参照 (Static Dictionary References) のシーケンスが含まれます。各 LZ77 後方参照は ⟨length, distance⟩ ペアであり、length はコピーするバイト数を示し、distance は非圧縮データストリーム内でコピーを開始する位置が何バイト後方かを示します。distance が 1 の場合、最後のバイトが distance 回コピーされることを意味します。distance は静的辞書内の位置にも変換できます。静的辞書参照は特別に処理される後方参照です。詳細はセクション 8 を参照してください。リテラルと後方参照は、挿入およびコピー長コード (Insert-and-Copy Length Code) と呼ばれる同じデータ構造に格納されます。このように、1 つの値が挿入長 (Insert Length)（コードの直後に続くリテラルの数）とコピー長 (Copy Length)（次の後方参照の長さ）を決定します。後方参照の距離は、次の距離コード (Distance Code) によって決定されます。最後の挿入およびコピー長コードのコピー長は 0 でもかまいません。この場合、データの最後のシンボルはリテラル値です。
非圧縮メタブロック (Uncompressed meta-blocks): これらのメタブロックには、非圧縮データ (Uncompressed Data) が含まれます。
メタデータメタブロック (Meta-data meta-blocks): これらのメタブロックは将来の使用のために予約されています。デコーダーによってスキップされます。本ドキュメントでは、これらのメタブロックの形式を定義していません。必要に応じて、アプリケーションがそのような形式を定義できます。
圧縮メタブロックの構造は次のとおりです:
-
リテラル、挿入およびコピー長、距離の 3 つのカテゴリーそれぞれのブロックタイプ (Block Type) とブロックカウント (Block Count)。ブロックタイプは小さな整数値を持ち、次のブロックカウント値に使用されるプレフィックスコードのセットを識別します。ブロックカウントは、現在のブロックタイプのプレフィックスコードとコンテキストモデル (Context Models) が使用されるシンボルの数です。
-
リテラルのブロックタイプ用のプレフィックスコード (
BTYPE-L)。 -
リテラルのブロックカウント用のプレフィックスコード (
BLEN-L)。 -
挿入およびコピー長のブロックタイプ用のプレフィックスコード (
BTYPE-I)。 -
挿入およびコピー長のブロックカウント用のプレフィックスコード (
BLEN-I)。 -
距離のブロックタイプ用のプレフィックスコード (
BTYPE-D)。 -
距離のブロックカウント用のプレフィックスコード (
BLEN-D)。 -
場合によっては、距離パラメータ
NPOSTFIXとNDIRECT（メタブロックが最初の場合は 0 に設定され、それ以外の場合は任意の非負の値に設定できます。セクション 4 を参照）。 -
リテラルブロックタイプの数
NBLTYPES-Lとコンテキストモードの数CMODE（NBLTYPES-Lが 0 の場合は 1 として解釈されます）。 -
NBLTYPES-L個のリテラルブロックタイプのそれぞれについて:- リテラルのコンテキストモード（0、1、または 2）。
- 場合によっては、リテラルコンテキストマップ (Literal Context Map)（
NBLTYPES-Lが 1 の場合、コンテキストマップをエンコードする必要はありません。その場合、コンテキスト ID は常に 0 です）。
-
挿入およびコピーブロックタイプの数
NBLTYPES-I（0 の場合は 1 として解釈されます）。 -
場合によっては、挿入およびコピーコンテキストマップ (Insert-and-Copy Context Map)（
NBLTYPES-Iが 1 の場合、コンテキストマップをエンコードする必要はありません。その場合、コンテキスト ID は常に 0 です）。 -
距離ブロックタイプの数
NBLTYPES-D（0 の場合は 1 として解釈されます）。 -
場合によっては、距離コンテキストマップ (Distance Context Map)（
NBLTYPES-Dが 1 の場合、コンテキストマップをエンコードする必要はありません。その場合、コンテキスト ID は常に 0 です）。 -
リテラル用のプレフィックスコードのシーケンス。数は
NBLTYPES-Lに異なるコンテキスト ID の数を掛けたものに等しくなります（各リテラルブロックタイプで最大 64）。これらのコードは、次のコマンドのリテラルに使用されます。 -
挿入およびコピー長用のプレフィックスコードのシーケンス。数は
NBLTYPES-Iに異なるコンテキスト ID の数を掛けたものに等しくなります（各挿入およびコピーブロックタイプで最大 256）。これらのコードは、次のコマンドに使用されます。 -
距離用のプレフィックスコードのシーケンス。数は
NBLTYPES-Dに異なるコンテキスト ID の数を掛けたものに等しくなります（各距離ブロックタイプで 4）。これらのコードは、次のコマンドの距離に使用されます。 -
ブロック切り替えコマンド (Block-Switch Commands)、リテラル、挿入およびコピー長、距離を含むデータストリーム (Data Stream)。
ブロック構造 (Block Structure) は、入力をブロックタイプで個別のアルファベット分布 (Alphabet Distributions) に分割することで圧縮を支援します。リテラルと距離のブロックタイプは、コンテキストを使用してさらに異なる分布に分割される場合があります。ブロックタイプごとのコンテキストマップは、異なるコンテキストで使用されるプレフィックスコードを制御します。
ブロック切り替え (Block Switching) の背後にある直感は、入力の異なる領域は異なる統計を持つ可能性が高いということです（たとえば、Web ページの HTML と JavaScript）。各カテゴリー（リテラル、挿入およびコピー長、距離）の特定のメタブロックに複数のブロックタイプが存在する可能性があるため、新しいメタブロックを開始せずにプレフィックスコード分布を適応させるためにブロック切り替えを使用できます。各ブロックタイプは、コンテキストモデリング (Context Modeling) に基づいて、リテラルと距離に対して複数のプレフィックスコード分布を持つことができます。
出典 (Source): RFC 7932, Section 2
公式テキスト (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt