HTTP2のヘッダ圧縮 Huffman Encode の原理とメリット・デメリット

# Huffman Encode の原理とメリット・デメリット
この記事は [HTTP2 Advent Calendar 2014](http://qiita.com/advent-calendar/2014/http2) の 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 の資料](https://docs.google.com/a/twist.com/presentation/d/11eBmGiHbYcHR9gL5nDyZChu_-lCa2GizeuOfaLU2HOU/edit?pli=1#slide=id.g1d134dff_1_222) をご覧ください。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](http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-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](https://github.com/tatsuhiro-t/nghttp2) では、Literal と Huffman の結果を比較して、より小さいサイズになった Encoding を採用して送信する、といった工夫がなされています。

# まとめ
HPACK で導入されている Huffman Encoding について解説しました。
bit 列から元の文字を複合するには、文字によって bit 数が違うので、tree を再帰的に辿る処理を書くことになるでしょう。

Huffman Encode/Decode を高速化するための工夫は @kazu_yamamoto さんの [こちらの資料](http://www.mew.org/~kazu/material/2014-hpack.pdf) が詳しいです。
(この資料は、前回の Reference Set 解説記事でも引用しています。恐るべし。。)

# 余談
本記事では、"Huffman Encoding" と表記しましたが、一般的には Huffman Coding (ハフマン符号化) と呼ばれているようです。両者は同じものを指します。

また、現在の仕様では "HTTP/2.0" ではなく、"HTTP2" または "HTTP/2" が正しい呼び方です。