要約
Turing Complete FM #13 を聞いていると、ブルームフィルタというデータ構造についての話題がありました。ブルームフィルタというものを知らなかったので色々調べてみると面白そうだったのでGoで実装してみました。
ブルームフィルタとは?
誤解を恐れず言うと、存在可否をすごい早く判定できるけど誤判定する可能性があるデータ構造です。ただ「存在しない」という結果の場合は誤判定はせず 100% 存在しませんが、「存在する」という結果の場合は実際は存在しない場合があります。
| 判定結果 | 実際 |
|---|---|
| 存在しない | 存在しない |
| 存在する | 存在する or 存在しない |
この「存在しなけど存在すると判定する」ことを「偽陽性」というらしいです。
ブルームフィルタの作り方
ブルームフィルタでは存在するもののリストを一つの固定長ビット列に保存します。リストの要素を複数のハッシュ関数でハッシュ化し、そのデータをビット列に重ね書きすることでブルームフィルタが完成します。ただ、ハッシュ化したデータをそのままビット列に書くのではなく、ハッシュ値をインデックスとみなして、インデックスのビットをセットすることで要素を保存していきます。
ハッシュ関数は同じ関数でもよいですが、その場合はそれぞれで別々のハッシュ値を取り出すためにそれぞれに別々のシードをつけてあげる必要があります。
要素の検索
ブルームフィルタを作った後、要素を検索します。検索する要素をフィルタを作った時と同じハッシュ関数にかけて、インデックスを算出します。算出したインデックスのビットがすべて1ならその要素は存在していると判断され、インデックスのビットのうち、どれか一つでも0なら存在しないと判断されます。
誤判定ケース
存在しない要素でも、計算したインデックスが偶然すべて1になると誤判定になります。
誤判定の確率
誤判定の確率はビット配列のサイズ(m)、登録する要素の数(n)、ハッシュ関数の数(k) で決まります。確率を(p)とすると以下の公式になるそうです。
僕はビット配列サイズと確率が固定の場合に最大要素登録数となるハッシュ関数の個数が知りたかったので n を左辺とする式に変形しました。
例えば、m = 8192 で p = 0.01 の場合の n と k の関係をグラフ化すると以下のようになります。
これを見ると、k = 7 の時に n = 854 となり、このラインが 偽陽性 0.01 を超えない最大の格納数となるようです。
使いどころ
誤判定するようなものに使いどころがあるのか？と思ってしまうけど、キャッシュ存在判定によく使われているようです。SQLのテーブル結合でも内部的に使用している場合もあるようです。フィルタというくらいなので、検索要素が多く、その検索が重い場合にその前段にブルームフィルタを置いて、検索要素数を減らしたうえで、本来の検索をする。といったような用途に使うのがいいのかもしれません。
- Kazuho's Weblog: ソート済の整数列を圧縮する件
- pixivでBloomFilterを使うためにやったこと - pixiv inside [archive]
- SQL実行時のブルームフィルタ(Bloom Filter)アルゴリズム | Future Tech Blog - フューチャーアーキテクト
Goで実装してみる。
上記を踏まえて実装したのが以下のコードになります。今回はハッシュ関数に Goの標準パッケージに添付されている hash/fnv を使用しました。また、k個のハッシュ関数を hash/fnv から導くために ダブルハッシュ法を使用しました (参考資料: C++でブルームフィルタを実装する方法 | POSTD) ダブルハッシュ法に関してはよくわかってないですが、ハッシュ値とシード値をダブルハッシュ関数に渡すことでランダムはハッシュ関数がお手軽に手に入れられるもの。という認識です。main() 関数ではランダムな要素を854個登録し、そのあとで、ランダムな要素 百万個を検索したときの偽陽性と登録した要素がすべてマッチするかを調べています。実行の結果、偽陽性に関しては理論値の0.01に近い確率で偽陽性が判定できていて、登録した要素もすべてマッチするので実装としては問題ないかと思っています。
package main import ( "fmt" "hash" "hash/fnv" "io" "math/rand" "time" ) func NewBloomFilter(msize, hsize int, hfunc func() hash.Hash64) *BloomFilter { m := make([]bool, msize) return &BloomFilter{ m, hsize, hfunc, } } type BloomFilter struct { m []bool hsize int hfunc func() hash.Hash64 } func (b *BloomFilter) Set(data string) { hashA, hashB := b.hash(data) for i := 0; i < b.hsize; i++ { ofs := b.nthHash(hashA, hashB, i, len(b.m)) b.m[ofs] = true } } func (b *BloomFilter) IsMatch(data string) bool { hashA, hashB := b.hash(data) for i := 0; i < b.hsize; i++ { ofs := b.nthHash(hashA, hashB, i, len(b.m)) if !b.m[ofs] { return false } } return true } func (b *BloomFilter) hash(data string) (uint32, uint32) { h := b.hfunc() io.WriteString(h, data) hash := h.Sum64() ha := uint32(hash) hb := uint32(hash >> 32) return ha, hb } func (b *BloomFilter) nthHash(ha, hb uint32, n, size int) uint32 { return (ha + uint32(n)*hb) % uint32(size) } func main() { b := NewBloomFilter(8192, 7, fnv.New64) lines := make(map[string]bool, 0) rand.Seed(42) for i := 0; i < 854; i++ { key := fmt.Sprintf("%v", rand.Intn(4294967294)) lines[key] = true b.Set(key) } rand.Seed(time.Now().UnixNano()) total := 0 match := 0 miss := 0 for i := 0; i < 1000000; i++ { key := fmt.Sprintf("%v", rand.Intn(4294967294)) total++ if b.IsMatch(key) { match++ if _, ok := lines[key]; !ok { miss++ } } } fmt.Printf("total:%d, match:%d, miss:%d, p:%v\n", total, match, miss, float64(miss)/float64(total)) total = 0 match = 0 miss = 0 for key := range lines { total++ if b.IsMatch(key) { match++ if _, ok := lines[key]; !ok { miss++ } } } fmt.Printf("total:%d, match:%d, miss:%d\n", total, match, miss) }
まとめ
ブルームフィルタとは何かを理解し、Goで実装してみました。実装も予想していたよりも簡単に実装できたのが意外でした。ただ使いどころがいまいち思いついていなくて、実際の業務に使うことはあまりないのかもしれません。あと、Goではboolの配列(スライス)を作ると1要素に1バイト使用するので無駄なビットが出てしまうことが気になっています。無駄をなくすには別途1バイトにビットを詰めるようなクラス(構造体(?))を作るなどして対応する必要がありそうです。
