bloom filter とは
bloom filter とは、ざっくりいうと ある集合において、低コストにある要素が存在しないことがわかる データ構造です。
どのくらいコストが低いかというと、要素の登録や存在確認がともに O(k) です(kは利用するハッシュの数)。
集合の最大要素数や、実際に登録されているデータ数に影響されずに固定時間で結果を返せます。
特徴としては
なので、偽陽性が許容できる場合においては高速な存在確認としてつかえます。
想定できる使い方としては、探索コストが高いデータを検索する前にbloom filterをつかう、など。
しくみ
一言でいうと単語を複数のbit列のindex値に変換して、そのindex番目のbitがすべて立ってるかチェックして、立ってれば存在している、一つでも立っていなければ存在しない！と判断させるだけです。
単語をbit列のindex値に変換するときにhashを使います。(bit列内でonにするindex値を十分に分散させるため。ここに偏りがあると偽陽性率があがる。はず。)
以下の説明では
- bit列の長さ8
- hashの数は1
のものを利用して説明します
(実際にはbit列の長さが小さすぎると衝突の可能性がますのでこんなに短いbit列を使うことはほぼないはずだし、hashの数は要素数やbit列長によって最適な数がもとめられるので1個であることはあまりないはず。まあ説明のための例なので細かいところは気にしないですすめる)
登録
ある単語の登録は、その単語をhash関数にかけてbit列のindex値を取得し、そのbitをたてます。
たとえば apple という文字列をhash化した結果が 5 だったとすると、bit列の5番目のbitをたてます
| index | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| bit | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
存在確認
ある単語の存在確認は、その単語をhash関数にかけてbitのindex値を取得し、そのbitが立っているか確認します。
apple の存在確認をしてみます。
apple はhash化すると 5 になるのでした。
先程追加したbit列を確認すると、5番目のbitは立っているので、 apple は存在していると判断できます。
| index | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| bit | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
つぎに orange の存在確認をしてみます。
orange はhash化すると 7 になりました。
このbit列から7番目の値を確認すると0です。bitが立っていないので、 orange は存在していないと判断できます。
| index | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| bit | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
つぎに banana の存在確認をしてみます。
banana はhash化すると 5 になりました。
bit列から5番目の値を確認すると、bitが立っているので banana は存在していると判断されます！
実際には banana はまだ追加されていないので、これは偽陽性のパターンです。
| index | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| bit | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
かんたんな実装
以下に実装を交えて説明します。実装はGo
試せるコードをplaygroundにもおいておきます
(割とtimeoutします。playgroundの機嫌が良ければ実行できます。素朴に実装してるためmd5を12回振ってるので大変なのかな...ハッシュ生成コスト的には、本来はダブルハッシュ法などをつかったほうがいいです)
ある長さを持ったbit列をつくります。(ここでは例として長さは8)
Goなら以下でOK
var bits uint8
ある単語を登録するには、その単語をハッシュ化してbitのindexをとります。
bit列の長さが8なので、0~7の範囲になるようなhash関数を準備します
今回はかませるhashの数は3つとします。bit列の長さや追加する要素数によって最適なhash数はもとめることができますが、今回はそのあたりは考慮しません。
func hash(s string) (idxes [3]uint8) { // md5結果の終端byteの上位3bitの値(0~7)をbitsのindex値として返す // 最終的に分散された3bit値が取れればいいので、8の剰余をとってもどちらでもよい。 // ことなるハッシュがとりたいので適当にsaltをふる idxes[0] = md5.Sum([]byte(s+"1"))[15] >> 5 idxes[1] = md5.Sum([]byte(s+"2"))[15] >> 5 idxes[2] = md5.Sum([]byte(s+"3"))[15] >> 5 return idxes }
bit列に値を追加したいときは、ハッシュを使ってindexを取得し、そのindex番目のbitを立てます。
idx番目のbitをとるにはidxぶんだけ1を左シフトすればよいです。
func add(s string) { idxes := hash(s) for _, idx := range idxes { // idx番目のbitを立てる bits |= 1<<idx } }
bit列の値を存在チェックしたいときも同じくハッシュを使って、index番目のbitが立っているか確認すればよいです。
すべてのindex番目のbitがたっていれば その要素は存在していると判断できます。
func exists(s string) bool { idxes := hash(s) for _, idx := range idxes { // idx番目のbitが立っていないケースを判定 if 1<<idx != 1<<idx & bits { return false } } return true }
準備はできたので、てきとうにそれらを呼び出してみましょう。
bit列に単語を登録したり、単語が存在するかbit列を確認したりしてみます。
func main() { add("test1") fmt.Printf("added bits: %b\n\n", bits) // 存在する fmt.Printf("is exists 'test1': %t\n\n", exists("test1")) // 存在しない fmt.Printf("is exists 'test2': %t\n\n", exists("test2")) // 存在しないのに存在すると判定している(偽陽性) fmt.Printf("is exists 'test12': %t\n\n", exists("test12")) }
今までの実装にlogなどを適宜仕込みつつ実行すると以下のように出力されます
bit on: 10000000 bit on: 1 bit on: 10 added bits: 10000011 bit check: 10000000 bit check: 1 bit check: 10 is exists 'test1': true bit check: 100000 is exists 'test2': false bit check: 1 bit check: 10 bit check: 10000000 is exists 'test12': true
