ブルームフィルタ — 「絶対に無い」だけ即答する門番
「この単語、登録済みリストに入ってる?」を超高速・超省メモリで答えたい。全部のリストを持って1つずつ照合すれば確実ですが、件数が増えると重くなります。そこで登場するのがブルームフィルタ。ほんの少しのビット列だけで、「絶対に無い」を一瞬で言い切れる門番です。
仕組みはシンプル。単語をいくつかのハッシュ関数に通し、出てきた番号のビットを立てるだけ。確認したいときは同じ番号のビットを見て、1つでも0なら「登録されていない」と断言できます。下の図1で単語を登録し、いろいろな単語を問い合わせてみてください。
BIT ARRAY — 16個のビット(登録した単語のハッシュ位置が1になる)
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0(立っていない)
1(立っている)
いま確認中
① 登録するクリックで出し入れ。立つビットが見えます
② 問い合わせる登録した単語も、していない単語も試せます
上の単語を問い合わせると、ここに結果が出ます。
図1 — ブルームフィルタ:ビットが1つでも0なら「確実に無い」
「無い」は確実、「有る」は“たぶん”
ブルームフィルタの答えは2種類。「絶対に無い」と「あるかも」です。確認したビットのどれか1つでも0なら、その単語は一度も登録されていないと100%言い切れます(登録していたら必ず立っているはずだから)。これが偽陰性ゼロ — 「無い」と言ったら本当に無い。
やっかいなのは逆。確認したビットが全部1でも、本当に登録されているとは限りません。別の単語たちがたまたまそのビットを立てていただけ、ということが起こります。これが偽陽性。だからブルームフィルタは「あるかも」までしか言えず、本当に必要なときだけ本体(DBなど)を確認します。登録を増やすほどビットが埋まり、偽陽性は起きやすくなります。
用語ミニ辞書
- 偽陽性
- 登録していないのに「あるかも」と出ること。ブルームフィルタでは起こりうる。
- 偽陰性
- 登録したのに「無い」と出ること。ブルームフィルタでは決して起きない。
- ハッシュ関数
- 単語をビット番号に変換する計算。複数使うほど誤判定を減らせる(ただし埋まりも早い)。
まとめ
ブルームフィルタは「確実に無いものを高速に弾く」ための道具です。わずかなメモリで巨大な集合をふるいにかけ、明らかに無いリクエストを門前払いできます。データベースの存在チェック前のふるい、巨大なキャッシュのミス判定など、「全部を持たずに、無いことだけ確実に言いたい」場面で大活躍します。