付録B. ハフマン符号 (Huffman Code)

以下のハフマン符号は、ハフマン符号化で文字列リテラルをエンコードするときに使用されます。この表は、https://github.com/nmathewson/hpack-huffman-gen で見つかるツールを使用して生成されました。

表は次のように構成されています:

• sym: シンボル (バイト値)
• code as bits: シンボルのバイナリコード
• code as hex: コードの16進表現
• len: コードのビット長

文字列リテラルをエンコードするために使用されるハフマン符号は、次の表を使用します:

      sym         code as bits                 code as hex    len
                                                                 (bits)
    (  0)  |11111111|11000                             1ff8  [13]
    (  1)  |11111111|11111111|1011000                7fffd8  [23]
    (  2)  |11111111|11111111|11111110|0010         fffffe2  [28]
    (  3)  |11111111|11111111|11111110|0011         fffffe3  [28]
    (  4)  |11111111|11111111|11111110|0100         fffffe4  [28]
    (  5)  |11111111|11111111|11111110|0101         fffffe5  [28]
    (  6)  |11111111|11111111|11111110|0110         fffffe6  [28]
    (  7)  |11111111|11111111|11111110|0111         fffffe7  [28]
    (  8)  |11111111|11111111|11111110|1000         fffffe8  [28]
    (  9)  |11111111|11111111|11101010               ffffea  [24]
    ( 10)  |11111111|11111111|11111111|111100      3ffffffc  [30]
    ( 11)  |11111111|11111111|11111110|1001         fffffe9  [28]
    ( 12)  |11111111|11111111|11111110|1010         fffffea  [28]
    ( 13)  |11111111|11111111|11111111|111101      3ffffffd  [30]
    ( 14)  |11111111|11111111|11111110|1011         fffffeb  [28]
    ( 15)  |11111111|11111111|11111110|1100         fffffec  [28]
    ( 16)  |11111111|11111111|11111110|1101         fffffed  [28]
    ( 17)  |11111111|11111111|11111110|1110         fffffee  [28]
    ( 18)  |11111111|11111111|11111110|1111         fffffef  [28]
    ( 19)  |11111111|11111111|11111111|0000         ffffff0  [28]
    ( 20)  |11111111|11111111|11111111|0001         ffffff1  [28]
    ( 21)  |11111111|11111111|11111111|0010         ffffff2  [28]
    ( 22)  |11111111|11111111|11111111|111110      3ffffffe  [30]
    ( 23)  |11111111|11111111|11111111|0011         ffffff3  [28]
    ( 24)  |11111111|11111111|11111111|0100         ffffff4  [28]
    ( 25)  |11111111|11111111|11111111|0101         ffffff5  [28]
    ( 26)  |11111111|11111111|11111111|0110         ffffff6  [28]
    ( 27)  |11111111|11111111|11111111|0111         ffffff7  [28]
    ( 28)  |11111111|11111111|11111111|1000         ffffff8  [28]
    ( 29)  |11111111|11111111|11111111|1001         ffffff9  [28]
    ( 30)  |11111111|11111111|11111111|1010         ffffffa  [28]
    ( 31)  |11111111|11111111|11111111|1011         ffffffb  [28]
' ' ( 32)  |010100                                       14  [ 6]
'!' ( 33)  |11111110|00                                 3f8  [10]
'"' ( 34)  |11111110|01                                 3f9  [10]
'#' ( 35)  |11111111|1010                               ffa  [12]
'$' ( 36)  |11111111|11001                             1ff9  [13]

注: 完全なハフマン符号表には257個のエントリ (シンボル0〜255とEOS) が含まれています。スペースの制約により、ここでは一部のみが表示されています。完全な表については、https://www.rfc-editor.org/rfc/rfc7541.txt の公式RFC 7541文書を参照してください。

ハフマン符号は、上記で定義されたコード長を持つ正規ハフマン符号です。デコーディング効率のために、実装はテーブルベースのデコーダーまたはこの特定のコード用に最適化されたツリーベースのデコーダーを使用する必要があります。

ビット整列エンコーディングを可能にするために、文字列終端 (EOS) シンボルがハフマン符号に含まれています。エンコードされた文字列のビット長がオクテット境界に収まらない場合、EOSシンボルを使用してエンコードされた文字列を次のオクテット境界にパディングします。7ビットより長いパディングは、デコーディングエラーとして扱わなければなりません (MUST)。EOSの最上位ビットに対応しないパディングは、デコーディングエラーとして扱わなければなりません (MUST)。

---