Golomb-coded setについて調べてみた

Oku KazuhoさんのHTTP/2の課題と将来を拝見していたらGolomb-coded setなるものが登場したのでいろいろ調べたメモです。

BloomFilterについてもそのうち記事にするかもしれないです。
むしろBloomFilterを先に書くべきでは。

前提、やりたいこと

やりたいことの例としてhttp2のcache-aware server pushを考える。
clientからserverへリクエストするとき、htmlよりcssを先にpushするといったような優先度付けをしたい。
一方で、既にclientでcacheしていたら、改めてserverからpushするのは無駄。
そこでclientからのリクエスト中のcookieにcache済みのjsやcssといったasset情報埋め込んでserverに教えてあげる。

とはいえ、そのままassetごとにpath/file名とか書くと無駄が大きいし、file名は変わらないけど中身が変わっていたりすると区別ができなくてつらい。
→ハッシュして送る。

ここで偽陽性はある程度許容する。
やりたいことは、すでにcache済みだったら送らない(≒送る数を減らしたい)なので、確実にcacheされてないと言えるなら送る。
(偽陽性で、cache済みと判断したけど実はcacheされてないやつはclientが改めてGETする)
→BloomFilterのような確率的データ構造が適している。

BloomFilterの空間効率性

A. PaghらによるとBloomFilterにデータを格納するために必要なbit数は以下。

BloomFilterで使うbit数:  N log_2 \frac{1}{p} \times log_2 e

確率的データ構造に使うbit数(理論値):  N log_2 \frac{1}{p}

 N: 貯めておく要素数
 p: 偽陽性確率

 log_2 e ≒ 1.44 なので44%程度、BloomFilterは理論値より空間効率が悪い。

挿入するデータの分布に適した方法でデータを格納すれば理論値に近づく。
→Golomb-coded setは、ハッシュ値の均一性を利用し、幾何分布のときにHuffman符号と同じ効率になるGolomb符号により理論値に近づける。

Golomb-coded set

※例は以下の参考文献のなぞり。

変数はさっきと一緒。

 N: 貯めておく要素数
 P: 偽陽性確率

例題として以下のフォネティックコード( N = 26)を考える。

['alpha', 'bravo', 'charlie', 'delta', 'echo', 'foxtrot', 'golf', 'hotel', 'india', 'juliet', 'kilo', 'lima', 'mike', 'november', 'oscar', 'papa', 'quebec', 'romeo', 'sierra', 'tango', 'uniform', 'victor', 'whiskey', 'xray', 'yankee', 'zulu']

許容する偽陽性確率を P = \frac{1}{64}とする。

要素は適当なハッシュ取ってから mod (N \times \frac{1}{P} (= 1664)する。

※cache-aware server pushで使う場面では、sha-2にするというようなセキュリティ性は担保しなくてよく、均一性と速度のほうが重要なのでMD5sha-1で十分。

 [0, (N \times \frac{1}{P} ) ] = [0, 1664]でハッシュ値が分布する。
ここで N(= 26)要素をハッシュ計算してからソートする。
十分に均一なハッシュならソート後の要素列のi番目とi+1番目の差は \frac{1}{P} (=64)くらいになる(ことが多いと期待される)。
 \frac{1}{P} (=64)で割ると、商は0 or 1になることが多い。
→これ幾何分布となるのでGolomb符号使うと効率がよい。

符号化は以下の表のように行う。

符号化
0 0
1 10
2 110
3 1110
4 11110

余りはそのまま2進数でくっつける。
例) 68 / 64 = 1 ... 4 → 68 = 0b(10 100)
※10と100の間のblankは便宜的に入れてるだけ。

これでフォネティックコードを符号化すると以下になる(197 bits)。

11001011 10101001 00100000 11110111 10000000 01100110 00111010 00000110 00011111 00100000 01100101 00011001 10001010 10110001 00000011 00101101 01100010 01001100 01010000 00110011 00011110 01100110 10101110 10011000 00011

それぞれデータの格納に必要なbit数は以下のようになるので、BloomFilterより理論値に近くなっていることがわかる。

理論値: 156 bits  
BloomFilter: 225 bits (最適なハッシュ関数の数で同じ偽陽性確率を許容する場合)  
Golomb-coded set: 197 bits  

参考