http2
huffman
HTTP2Day 16

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

More than 3 years have passed since last update.


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" が正しい呼び方です。