メインコンテンツまでスキップ

7. コンテキストモデリング (Context Modeling)

7. コンテキストモデリング (Context Modeling)​

セクション 2 で説明したように、リテラルバイト (Literal Byte) または距離コード (Distance Code) をエンコードするために使用されるプレフィックスツリー (Prefix Tree) は、ブロックタイプ (Block Type) とコンテキスト ID (Context ID) に依存します。このセクションでは、特定のリテラルと距離コードのコンテキスト ID を計算する方法と、<block type, context ID> ペアをリテラルおよび距離プレフィックスコードの配列内のプレフィックスコードのインデックスにマップするコンテキストマップ (Context Map) をエンコードする方法を指定します。

7.1. リテラルのコンテキストモードとコンテキスト ID 検索 (Context Modes and Context ID Lookup for Literals)​

次のリテラルをエンコードするためのコンテキスト (Context) は、ストリーム内の最後の 2 バイト (p1, p2、ここで p1 は最新のバイト) によって定義されます。これらのバイトが非圧縮メタブロック、後方参照 (Backward References)、静的辞書参照 (Static Dictionary References)、またはリテラル挿入 (Literal Insertions) によって生成されたかどうかに関係ありません。ストリームの開始時に、p1 と p2 はゼロに初期化されます。

コンテキスト ID を計算するために、コンテキストモード (Context Modes) と呼ばれる 4 つの方法があります:

  • LSB6: コンテキスト ID は p1 の 6 最下位ビットの値です。

  • MSB6: コンテキスト ID は p1 の 6 最上位ビットの値です。

  • UTF8: コンテキスト ID は p1, p2 の複雑な関数で、テキスト圧縮用に最適化されています。

  • Signed: コンテキスト ID は p1, p2 の複雑な関数で、符号付き整数のシーケンスの圧縮用に最適化されています。

UTF8 および Signed コンテキストモードのコンテキスト ID は、次のルックアップテーブル Lut0, Lut1, Lut2 を使用して計算されます。

Lut0 :=
  0,  0,  0,  0,  0,  0,  0,  0,  0,  4,  4,  0,  0,  4,  0,  0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
  8, 12, 16, 12, 12, 20, 12, 16, 24, 28, 12, 12, 32, 12, 36, 12,
 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 32, 32, 24, 40, 28, 12,
 12, 48, 52, 52, 52, 48, 52, 52, 52, 48, 52, 52, 52, 52, 52, 48,
 52, 52, 52, 52, 52, 48, 52, 52, 52, 52, 52, 24, 12, 28, 12, 12,
 12, 56, 60, 60, 60, 56, 60, 60, 60, 56, 60, 60, 60, 60, 60, 56,
 60, 60, 60, 60, 60, 56, 60, 60, 60, 60, 60, 24, 12, 28, 12,  0,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3

Lut1 :=
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1,
  1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1,
  1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Lut2 :=
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7

各テーブルのバイトシーケンスとしての長さと CRC-32 チェック値（付録 C を参照）は次のとおりです:

Table    Length    CRC-32
-----    ------    ------
Lut0     256       0x8e91efb7
Lut1     256       0xd01a32f4
Lut2     256       0x0dd7a0d6

p1 が最後の非圧縮バイトで、p2 が最後から 2 番目の非圧縮バイトであるとき、コンテキスト ID は次のように計算できます:

For LSB6:    Context ID = p1 & 0x3f
For MSB6:    Context ID = p1 >> 2
For UTF8:    Context ID = Lut0[p1] | Lut1[p2]
For Signed:  Context ID = (Lut2[p1] << 3) | Lut2[p2]

上記で定義されたルックアップテーブルとコンテキスト ID を計算する操作から、リテラルのコンテキスト ID は 0..63 の範囲にあることがわかります。

コンテキストモード LSB6, MSB6, UTF8, Signed は、それぞれ整数 0, 1, 2, 3 で示されます。

コンテキストモードは各リテラルブロックタイプに対して定義され、メタブロックヘッダーの連続したビット配列に格納されます。常にブロックタイプごとに 2 ビットです。

7.2. 距離のコンテキスト ID (Context ID for Distances)​

距離コードをエンコードするためのコンテキスト (Context) は、距離に対応するコピー長 (Copy Length) によって定義されます。コンテキスト ID は、コピー長 2, 3, 4, および 4 より大きい場合にそれぞれ 0, 1, 2, 3 です。

7.3. コンテキストマップのエンコーディング (Encoding of the Context Map)​

コンテキストマップは 2 つあり、1 つはリテラル用、もう 1 つは距離用です。コンテキストマップのサイズは、リテラルの場合は 64 * NBLTYPESL、距離の場合は 4 * NBLTYPESD です。コンテキストマップの各値は、次のリテラルまたは距離をエンコードするときに使用されるプレフィックスコードのインデックスを示す 0 から 255 の間の整数です。

コンテキストマップは 2 次元行列で、1 次元配列としてエンコードされます:

CMAPL[0..(64 * NBLTYPESL - 1)]
CMAPD[0..(4 * NBLTYPESD - 1)]

ブロックタイプ BTYPE_x とコンテキスト ID CIDx を持つリテラルまたは距離コードをエンコードするためのプレフィックスコードのインデックスは:

index of literal prefix code = CMAPL[64 * BTYPE_L + CIDL]
index of distance prefix code = CMAPD[4 * BTYPE_D + CIDD]

コンテキストマップの値は、ゼロ値のランレングスエンコーディング (Run Length Encoding) とプレフィックス符号化の組み合わせでエンコードされます。RLEMAX をランレングスコードの数とし、NTREES をコンテキストマップの最大値に 1 を加えたものとします。NTREES は、コンテキストマップ内の異なる値の数に等しくなければなりません。言い換えれば、コンテキストマップ内の異なる値は [0..NTREES-1] 区間でなければなりません。プレフィックスコードのアルファベットには、次の RLEMAX + NTREES 個のシンボルがあります:

0: 値ゼロ
1: ゼロを 2〜3 回繰り返す、繰り返し長のために 1 ビットを読み取る
2: ゼロを 4〜7 回繰り返す、繰り返し長のために 2 ビットを読み取る
...
RLEMAX: ゼロを (1 << RLEMAX) から (1 << (RLEMAX+1))-1 回繰り返す、
        繰り返し長のために RLEMAX ビットを読み取る
RLEMAX + 1: 値 1
...
RLEMAX + NTREES - 1: 値 NTREES - 1

RLEMAX = 0 の場合、ランレングス符号化は使用されず、アルファベットのシンボルは直接コンテキストマップ内の値です。コンテキストマップの形式を定義できます（リテラルおよび距離コンテキストマップに同じ形式が使用されます）:

1..5 bits: RLEMAX、0 は 1 つの 0 ビットでエンコードされ、
           値 1..16 はビットパターン xxxx1 でエンコードされます
           (したがって 01001 は 5)

アルファベットサイズ NTREES + RLEMAX のプレフィックスコード

上記のプレフィックスコードとゼロ値のランレングス符号化を使用して
エンコードされたコンテキストマップサイズの値。ランレングスが
コンテキストマップのサイズよりも合計で多くの長さになる場合、
ストリームは無効として拒否されるべきです。

1 bit:  IMTF ビット、設定されている場合、コンテキストマップの値に
        逆移動前面変換 (Inverse Move-to-Front Transform) を実行して
        プレフィックスコードインデックスを取得します。

RLEMAX は、ゼロ値の最長シーケンスを表すのに必要な値よりも大きい場合があることに注意してください。また、NTREES 値は、セクション 9.2 で説明されているように、コンテキストマップの直前にエンコードされます。

この仕様で使用される逆移動前面変換 (Inverse Move-to-Front Transform) を、次の C 言語関数で定義します:

void InverseMoveToFrontTransform(uint8_t* v, int v_len) {
   uint8_t mtf[256];
   int i;
   for (i = 0; i < 256; ++i) {
      mtf[i] = (uint8_t)i;
   }
   for (i = 0; i < v_len; ++i) {
      uint8_t index = v[i];
      uint8_t value = mtf[index];
      v[i] = value;
      for (; index; --index) {
         mtf[index] = mtf[index - 1];
      }
      mtf[0] = value;
   }
}

逆移動前面変換は、[0..NTREES-1] 区間外の値を生成しないことに注意してください。

出典 (Source): RFC 7932, Section 7
公式テキスト (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt

に最終更新