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

3. プレフィックスコードの圧縮表現 (Compressed Representation of Prefix Codes)

3. プレフィックスコードの圧縮表現 (Compressed Representation of Prefix Codes)​

3.1. プレフィックス符号化入門 (Introduction to Prefix Coding)​

プレフィックス符号化 (Prefix Coding) は、事前に既知のアルファベットからのシンボルを、ビットシーケンス (Codes) で表現します。各シンボルに 1 つのコードが割り当てられます。異なるシンボルは異なる長さのビットシーケンスで表現される場合がありますが、パーサーは常にエンコードされた文字列をシンボルごとに明確に解析できます。

プレフィックスコードを二分木 (Binary Tree) の観点から定義します。各非リーフノード (Non-leaf Node) から降りる 2 つのエッジは 0 と 1 のラベルが付けられ、リーフノード (Leaf Nodes) はアルファベットのシンボルと 1 対 1 で対応します。シンボルのコードは、ルートからそのシンボルでラベル付けされたリーフまでのエッジ上の 0 と 1 のシーケンスです。例:

           /\              Symbol    Code
          0  1             ------    ----
         /    \                A     00
        /\     B               B     1
       0  1                    C     011
      /    \                   D     010
     A     /\
          0  1
         /    \
        D      C

パーサーは、ルートからツリーを下りることで、圧縮ストリームから次のシンボルをデコードできます。各ステップで、次の圧縮データビットに対応するエッジを選択します。

既知のシンボル頻度を持つアルファベットが与えられた場合、ハフマンアルゴリズム (Huffman Algorithm) は最適なプレフィックスコード（そのシンボル頻度を持つ文字列を、そのアルファベットの可能なプレフィックスコードの中で最も少ないビット数で表現するもの）の構築を可能にします。このようなプレフィックスコードはハフマンコード (Huffman Code) と呼ばれます。（ハフマンコードの詳細については [HUFFMAN] を参照してください。）

brotli フォーマットでは、さまざまなアルファベットのプレフィックスコードが特定の最大コード長を超えてはならないことに注意してください。この制約により、シンボル頻度からコード長を計算するアルゴリズムが複雑になります。詳細については、再度 [HUFFMAN] を参照してください。

3.2. Brotli フォーマットにおけるプレフィックス符号化の使用 (Use of Prefix Coding in the Brotli Format)​

brotli フォーマットの各アルファベットに使用されるプレフィックスコードは、正規プレフィックスコード (Canonical Prefix Codes) であり、次の 2 つの追加ルールがあります:

  • 特定のビット長のすべてのコードは、それらが表すシンボルと同じ順序で、辞書順に連続した値を持つ。

  • より短いコードは、より長いコードより辞書順に前に来る。

アルファベットの順序が ABCD であると仮定して、上記の例をこのルールに従うように再コーディングできます:

Symbol  Code
------  ----
A       10
B       0
C       110
D       111

つまり、0 は 10 より前に来て、10 は 11x より前に来て、110 と 111 は辞書順に連続しています。

このルールが与えられると、アルファベットの各シンボルのコードのビット長を順番に与えるだけで、アルファベットの正規プレフィックスコードを定義できます。これは実際のコードを決定するのに十分です。この例では、コードはビット長のシーケンス (2, 1, 3, 3) によって完全に定義されます。次のアルゴリズムは、最上位ビットから最下位ビットへ読み取ることを意図した整数としてコードを生成します。コード長は最初に tree[I].Len にあり、コードは tree[I].Code に生成されます。

1) 各コード長のコード数をカウントする。bl_count[N] を
   長さ N のコードの数とする (N >= 1)。

2) 各コード長の最小コードの数値を見つける:

   code = 0;
   bl_count[0] = 0;
   for (bits = 1; bits <= MAX_BITS; bits++) {
      code = (code + bl_count[bits-1]) << 1;
      next_code[bits] = code;
   }

3) すべてのコードに数値を割り当てる。同じ長さのすべての
   コードに連続した値を使用し、ステップ 2 で決定された
   基本値を使用する。使用されないコード（ビット長が
   ゼロ）には値を割り当ててはならない。

   for (n = 0; n <= max_code; n++) {
      len = tree[n].Len;
      if (len != 0) {
         tree[n].Code = next_code[len];
         next_code[len]++;
      }
   }

例:

アルファベット ABCDEFGH を、ビット長 (3, 3, 3, 3, 3, 2, 4, 4) で考えます。ステップ 1 の後、次のようになります:

N      bl_count[N]
-      -----------
2      1
3      5
4      2

ステップ 2 は次の next_code 値を計算します:

N      next_code[N]
-      ------------
1      0
2      0
3      2
4      14

ステップ 3 は次のコード値を生成します:

Symbol Length   Code
------ ------   ----
A       3       010
B       3       011
C       3       100
D       3       101
E       3       110
F       2       00
G       4       1110
H       4       1111

3.3. アルファベットサイズ (Alphabet Sizes)​

プレフィックスコードは brotli フォーマットでさまざまな目的に使用され、各目的には異なるアルファベットサイズがあります。リテラルコード (Literal Codes) の場合、アルファベットサイズは 256 です。挿入およびコピー長コード (Insert-and-Copy Length Codes) の場合、アルファベットサイズは 704 です。ブロックカウントコード (Block Count Codes) の場合、アルファベットサイズは 26 です。距離コード (Distance Codes)、ブロックタイプコード (Block Type Codes)、およびコンテキストマップの圧縮に使用されるプレフィックスコードの場合、アルファベットサイズは動的であり、後のセクションで定義されるパラメータに基づいています。次の表は、さまざまなプレフィックスコードのアルファベットサイズと、それらが定義されているドキュメントのセクションをまとめたものです。

+-----------------+-------------------------+------------+
| Prefix Code     | Alphabet Size           | Definition |
+-----------------+-------------------------+------------+
| literal         | 256                     |            |
+-----------------+-------------------------+------------+
| distance        | 16 + NDIRECT +          | Section 4  |
|                 | (48 << NPOSTFIX)        |            |
+-----------------+-------------------------+------------+
| insert-and-copy | 704                     | Section 5  |
| length          |                         |            |
+-----------------+-------------------------+------------+
| block count     | 26                      | Section 6  |
+-----------------+-------------------------+------------+
| block type      | NBLTYPESx + 2,          | Section 6  |
|                 | (where x is I, L, or D) |            |
+-----------------+-------------------------+------------+
| context map     | NTREESx + RLEMAXx       | Section 7  |
|                 | (where x is L or D)     |            |
+-----------------+-------------------------+------------+

3.4. 簡単なプレフィックスコード (Simple Prefix Codes)​

各プレフィックスコードの圧縮表現の最初の 2 ビットは、簡単なプレフィックスコード (Simple Prefix Code) と複雑なプレフィックスコード (Complex Prefix Code) を区別します。この値が 1 の場合、このセクションで説明されているように簡単なプレフィックスコードが続きます。それ以外の場合、セクション 3.5 で説明されているように複雑なプレフィックスコードが続きます。

簡単なプレフィックスコードは、非ゼロコード長を持つ最大 4 つのシンボルを持つことができます。簡単なプレフィックスコードの形式は次のとおりです:

2 bits: 値 1 は簡単なプレフィックスコードを示す
2 bits: NSYM - 1、ここで NSYM = コード化されたシンボルの数

NSYM 個のシンボル、それぞれ ALPHABET_BITS ビットを使用してエンコード

1 bit:  tree-select、NSYM = 4 の場合のみ存在

ALPHABET_BITS の値はプレフィックスコードのアルファベットに依存します。アルファベット内のすべてのシンボルを表現できる最小のビット数です。たとえば、リテラルバイトのアルファベットの場合、ALPHABET_BITS は 8 です。上記の NSYM 個のシンボルの各値は、ALPHABET_BITS 幅の整数値の値です。整数値がアルファベットサイズ以上の場合、または値が以前の値と同一の場合、ストリームは無効として拒否されるべきです。

NSYM 個のシンボルはソート順で提示されない場合があることに注意してください。同じビット長のプレフィックスコードは、ソート順でシンボルに割り当てる必要があります。

シンボルの（非ゼロ）コード長は次のように再構築できます:

  • NSYM = 1 の場合、1 つのシンボルのコード長はゼロです。このプレフィックスコードを使用して圧縮データストリームでこのシンボルをエンコードする場合、実際のビットは発行されません。同様に、このプレフィックスコードを使用してシンボルをデコードする場合、ビットは読み取られず、1 つのシンボルが返されます。

  • NSYM = 2 の場合、両方のシンボルのコード長は 1 です。

  • NSYM = 3 の場合、シンボルのコード長は、簡単なプレフィックスコードの表現に現れる順序で 1, 2, 2 です。

  • NSYM = 4 の場合、コード長（デコードされたシンボルの順序で）は tree-select ビットに依存します: 2, 2, 2, 2（tree-select ビット 0）、または 1, 2, 3, 3（tree-select ビット 1）。

3.5. 複雑なプレフィックスコード (Complex Prefix Codes)​

複雑なプレフィックスコード (Complex Prefix Code) は、セクション 3.2 で説明したように、コード長のシーケンスによって定義される正規プレフィックスコードです。さらに大きなコンパクト性のために、コード長シーケンス自体がプレフィックスコードを使用して圧縮されます。コード長のアルファベットは次のとおりです:

 0..15: コード長 0..15 を表す
    16: 前の非ゼロコード長を 3..6 回コピーする。
        次の 2 ビットが繰り返し長を示す
              (0 = 3, ... , 3 = 6)
        これが最初のコード長の場合、またはすべての前の
        コード長がゼロの場合、コード長 8 が
        3..6 回繰り返される。
        16 の繰り返しコード長コードは、前のコードの
        繰り返しカウントを次のように変更する:
           repeat count = (4 * (repeat count - 2)) +
                          (次の 2 ビットの 3..6)
        例:  コード 7, 16 (+2 bits 11), 16 (+2 bits 10)
              は 22 個のコード長 7 に展開される
              (1 + 4 * (6 - 2) + 5)
    17: コード長 0 を 3..10 回繰り返す。
        次の 3 ビットが繰り返し長を示す
              (0 = 3, ... , 7 = 10)
        17 の繰り返しコード長コードは、前のコードの
        繰り返しカウントを次のように変更する:
           repeat count = (8 * (repeat count - 2)) +
                          (次の 3 ビットの 3..10)

直前の 16 に続く 16 のコードは、前の繰り返しカウントを変更し、それが新しい繰り返しカウントになることに注意してください。17 に続く 17 についても同じです。3 つ以上の 16 コードが連続している、または 3 つ以上の 17 コードが連続している場合も可能で、毎回カウントを変更します。最終的な繰り返しカウントのみが使用されます。変更は同じコードが続く場合にのみ適用されます。16 の繰り返しは直前の 17 のカウントを変更せず、その逆も同様です。

コード長 0 は、アルファベット内の対応するシンボルが圧縮データに出現しないことを示し、前述のプレフィックスコード構築アルゴリズムに参加すべきではありません。複雑なプレフィックスコードには、少なくとも 2 つの非ゼロコード長が必要です。

コード長アルファベット上のプレフィックスコードのビット長は、次の可変長コード (Variable-Length Code) で圧縮されます（圧縮データに現れるように、ビットは右から左に解析されます）:

Symbol   Code
------   ----
0          00
1        0111
2         011
3          10
4          01
5        1111

複雑なプレフィックスコードの形式を次のように定義できます:

  • 2 bits: HSKIP、スキップされたコード長の数、値は 0、2、または 3 を取ることができます。スキップされた長さはゼロと見なされます。（HSKIP が 1 の場合は簡単なプレフィックスコードを示します。）

  • 上記で与えられたコード長アルファベット内のシンボルのコード長、順序: 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15。HSKIP が 2 の場合、シンボル 1 と 2 のコード長はゼロであり、最初のコード長はシンボル 3 用です。HSKIP が 3 の場合、シンボル 3 のコード長もゼロであり、最初のコード長はシンボル 4 用です。

    コード長シンボルのコード長は 0 から 5 の間であり、上記の可変長コードに従って 2..4 ビットで表現されます。コード長 0 は、対応するコード長シンボルが使用されないことを意味します。

    HSKIP が 2 または 3 の場合、それぞれの数の先頭コード長は暗黙のゼロであり、上記のコード長シーケンスには存在しません。

    少なくとも 2 つの非ゼロコード長がある場合、末尾のゼロコード長は省略されます。つまり、シーケンスの最後のコード長は非ゼロでなければなりません。この場合、すべての非ゼロコード長に対する (32 >> code length) の合計は 32 に等しくなければなりません。

    コード長アルファベット全体の長さが読み取られ、非ゼロコード長が 1 つだけだった場合、プレフィックスコードには長さゼロのコードを持つ 1 つのシンボルがあります。この場合、そのシンボルは圧縮器によってビットが発行されず、展開器によってビットが消費されません。この単一のシンボルは、このコードがデコードされるとすぐに返されます。これが発生する例は、表現されるコード全体が長さ 8 のシンボルを持つ場合です。たとえば、すべてのリテラル値を等確率で表すリテラルコード。この場合、単一のシンボルは 16 であり、これは前の長さを繰り返します。前の長さは、コード長コード長が読み取られる前に 8 と見なされます。

  • コード長シンボルのシーケンス。アルファベットのサイズを最大とし、コード長プレフィックスコードを使用してエンコードされます。末尾の 0 または 17 は省略する必要があります。つまり、最後にエンコードされたコード長シンボルは 1 から 16 の間でなければなりません。16 の繰り返しコードを使用してエンコードされたものを含む、アルファベット内のすべての非ゼロコード長に対する (32768 >> code length) の合計は 32768 に等しくなければなりません。前の長さを繰り返す回数またはゼロの長さを繰り返す回数が、アルファベット内のシンボルの数よりも合計で多くの長さになる場合、ストリームは無効として拒否されるべきです。

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

に最終更新