Huffman Encode の原理とメリット・デメリット
この記事は HTTP2 Advent Calendar 2014 の 16 日目の投稿です。
HTTP2 では、通信の遅延を小さくするために、ヘッダのサイズを小さくする機構を備えています。
その仕様は HPACK と呼ばれ、下記の組み合わせで構成されます。
- Literal
- ASCII Encoding
- 非圧縮のエンコーディングと言える。
- Huffman
- 今回の主人公。
- 出現頻度が高い文字ほど、小さいデータサイズで表現。
- Index
- 「Static Table に事前定義されている値」または「既にインデックス化した値」を番号で指定する。
- 圧縮に大きく寄与する。
今回は、Huffman Encoding の原理とメリット／デメリットを解説します。
gzip じゃダメなんですか？
HTTP/1.1 では、Body を gzip エンコードすることでサイズを圧縮することが出来ます。ヘッダも同じように gzip すればよいのでは？と思われるかもしれませんが、残念ながらそう簡単にはいきません。
理由は、CRIME という攻撃手法の存在です。
gzip は、インプットに同じパターンが出現したとき、2 回目以降のパターンを「最初の出現場所」と「パターンの長さ」に置換することでサイズを小さくします。
HTTPS で暗号化されていても、送信したデータサイズを隠すことは出来ないため、script を使って、埋め込むパターンを変えながら何度も試行させると、内部に含まれているパターンを推測出来てしまいます。
攻撃の仕組みを詳しく知りたい方は、Rizzo, J. と T. Duong の資料 をご覧ください。HPACK 仕様書からも引用されているスライドです。
ヘッダには認証情報を含むケースが多いため、簡単に推測するチャンスを与えるわけにはいきません。そこで、Huffman Encode を使った圧縮の登場です。
Huffman Encoding の原理
Huffman Encode は、出現頻度の高い文字を少ない bit 列で表現できる手法です。
実際に変換ルールを作ってみましょう。
文字 A, B, C, D, E, F のみを使うとし、その出現頻度が下記の場合を考えます。
| 文字 | 出現頻度 |
|---|---|
| A | 15 |
| B | 13 |
| C | 6 |
| D | 5 |
| E | 4 |
| F | 3 |
ここから 2 分木を作っていきます。
1. 最も出現頻度の低い文字 2 つを子に持つノードを作る
E と F の出現頻度が最も低いですね。
E と F を子に持つノード作り、E&F と呼ぶことにします。
E&F
/ \
E F
2. 頻度テーブルを更新
先ほど取り出した E と F の頻度を合算するのがミソです。
| 文字 | 出現頻度 |
|---|---|
| A | 15 |
| B | 13 |
| C | 6 |
| D | 5 |
| E&F | 4 + 3 = 7 |
3. 最も出現頻度の低い文字を 2 つ取り出す。
次は C と D の頻度が低いですね。
C と D を子に持つノード C&D を作ります。
C&D E&F
/ \ / \
C D E F
4. 1 〜 3 を繰り返す
同じ操作をあと 3 回ほど繰り返します。
時間がない方は手順 5 に飛んでください。
4-1
| 文字 | 出現頻度 |
|---|---|
| A | 15 |
| B | 13 |
| C&D | 6 + 5 = 11 |
| E&F | 7 |
次は、C&D と E&F の頻度が最も低い。
この 2 つを子とするノード C&D&E&F を作ります。
C&D&E&F
/ \
C&D E&F
/ \ / \
C D E F
4-2
| 文字 | 出現頻度 |
|---|---|
| A | 15 |
| B | 13 |
| C&D&E&F | 11 + 7 = 18 |
今度は A と B の頻度が最も低い。
ノード A&B を作る。
A&B C&D&E&F
/ \ / \
A B C&D E&F
/ \ / \
C D E F
4-3
| 文字 | 出現頻度 |
|---|---|
| A&B | 15 + 13 = 28 |
| C&D&E&F | 18 |
残り 2 つです。A&B と C&D&E&F を子に持つノードを作ります。
A&B&C&D&E&F
/ \
A&B C&D&E&F
/ \ / \
A B C&D E&F
/ \ / \
C D E F
ﾃﾞｷﾀｰ(ﾟ∀ﾟ)!!
5. 枝に bit を割り当てる
Huffman Tree が出来ました。枝に bit を割り当てます。
根っこから順に、
- 左下へ向かう枝に 0
- 右下へ向かう枝に 1
を割り当てます。
0 と 1 を逆にしても圧縮率は同じです。
根(A&B&C&D&E&F)
0 / \ 1
A&B C&D&E&F
0 / \ 1 0 / \ 1
A B C&D E&F
0 / \ 1 0 / \ 1
C D E F
再帰的に割り当てて、上の図のようになりました。
A という文字は 根 → 0 → 0 → A というルートで辿ることが出来ます。
D という文字は 根 → 1 → 0 → 1 → D というルートで辿ることができます。
なので、この木構造を知っていると、次のような変換ルールを定義できます。
| 文字 | bit 列 |
|---|---|
| A | 00 |
| B | 01 |
| C | 100 |
| D | 101 |
| E | 110 |
| F | 111 |
出現頻度が最も高い A は 2 bit で表現でき、
出現頻度の最も低い F は 3 bit で表現しています。
以上が Huffman Encoding の核心部分です。
具体例として、"CAFE" という文字をエンコードする場合は、先頭から bit を連結させて 10000111110 という bit 列になります。
デコードするときは、先頭 bit から見ていけば一意に文字を決定できます。
HTTP2 における Huffman Tree
文字の出現頻度は、インプットにするデータごとに違います。ですので、Huffman Tree は用途ごとに定義するのが一般的です。
HTTP2 では、膨大な HTTP リクエスト／レスポンスのログから、ヘッダ内の文字の出現頻度を集計し、1 つの Huffman Tree を決めています。
実際に、HPACK のバージョンごとに bit の割当が若干違いますし、HPACK version 05 までは、リクエストとレスポンスで別々に Huffman Tree を定義していました。
執筆時点の最新版の定義は HPACK-10 Appendix-B に記載されています。
圧縮率はどれくらい？
HPACK-10 では、bit 数が最も少ない文字は 5 bit で表現できます。
a, i, e, o など母音になる文字に少ない bit が割り当てられており、直感と一致しているように思います。
Literal (ASCII) だと 1 バイト = 8 bit 必要なので、最大で 5 / 8 = 62.5% まで圧縮可能です。
しかし、めったに出現しない \ (バックスラッシュ) を表現するためには、19bit 必要なので、Literal より大きなサイズになってしまいます。
ですので、盲目的に Huffman Encoding を使えばよい、というわけではありません。実際に nghttp2 では、Literal と Huffman の結果を比較して、より小さいサイズになった Encoding を採用して送信する、といった工夫がなされています。
まとめ
HPACK で導入されている Huffman Encoding について解説しました。
bit 列から元の文字を複合するには、文字によって bit 数が違うので、tree を再帰的に辿る処理を書くことになるでしょう。
Huffman Encode/Decode を高速化するための工夫は @kazu_yamamoto さんの こちらの資料 が詳しいです。
(この資料は、前回の Reference Set 解説記事でも引用しています。恐るべし。。)
余談
本記事では、"Huffman Encoding" と表記しましたが、一般的には Huffman Coding (ハフマン符号化) と呼ばれているようです。両者は同じものを指します。
また、現在の仕様では "HTTP/2.0" ではなく、"HTTP2" または "HTTP/2" が正しい呼び方です。