今日のお題
圧縮率 と 高速化
HPACKについて
- 圧縮率がよくなるよ
- おもったより圧縮率できないよ
- もっと圧縮しないと…
みたいな悪☆循☆環
- インデックス 初回のみ学習辞書(名前+値)を共有し、次回から圧縮できる
リファレンスセット(インデックスの集合から差分を計算するけど実装が超難しい) Re: Understanding how HPAC draft-02 works from Tatsuhiro Tsujikawa on 2013-09-06 (ietf-http-wg@w3.org from July to September 2013)
ハフマン符号(出現率の高い文字を短く符号化する)
HPACK
- 復号化は一意
- でも符号化はの仕様はすごいふんわりしてる(とりあえず6種類に区分けしてみた)
悲報
ゆーてそんな圧縮できないアルゴリズムがある
高速化
ボトルネック
- インデックスの探索
- ハフマン復号化
- ハフマン符号化
逆インデックス
- ヘッダ名とヘッダ値からインデックスを見つける
- (それすらなかったら)ヘッダ名からインデックスを見つける
- 外側と内側の辞書両方で探索を行う
ハフマン符号
- 符号化は高速O(1)だが復号化は低速O(log N)
- 論文 Fast Prefix Code Processing
- ビット列の連結は遅い
まとめ
- インデックスを使えば高い圧縮率を誇る
- リファレンスセットは結構複雑なのでいくばくか削るべき
- ハフマン符号 圧縮率はそれなり
