ブルームフィルタ?についての正確さが危ういメモ
ホッテントリの
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 – 人力検索はてな
でブルームフィルタ?なるものを知る。
理解した範囲だとこんな感じ*1。
何かを検索した時、｢ない！｣｢ある！｣と返るのが、まあ通常のイメージ。しかしブルームフィルタ?は｢ない！｣｢ある！・・かも｣と返す。つまり、一定の確率で、無いはずのものを｢ある！・・かも｣と判定する。また、素のままでは削除処理ができない。その代わり、処理速度と必要領域の面で優れている。
イメージとしては。
10個のビットを用意して、それぞれを｢あ｣｢い｣｢う｣｢え｣｢お｣｢か｣｢き｣｢く｣｢け｣｢こ｣とする。｢あ｣を格納する時は、｢あ｣のビットと、それから5つ後ろのビットを1にする、既に1のビットはそのままにする、と決める。つまり、｢あい｣を格納した後は1100011000、さらに｢おい｣を格納すると1100100001になる。
さらに｢うお｣｢えい｣のように、部分的に重なる言葉を追加する場合、重ならない部分だけを格納することになるので、領域を食いにくい。また、常に同じ操作をするだけなので、処理速度も一定になる。
検索時に問題があり、｢あい｣｢おい｣が登録されている状態で｢あお｣を検索した場合、｢あ｣｢お｣が共に格納済みなので、｢ある！・・かも｣という結果が得られる。実際は格納されていないのだけど。
削除については、｢あい｣を削除してしまうと、｢おい｣も｢い｣が削除されるので検索できなくなってしまう。よって削除できない。解決策の1つとして｢格納しようとした場所が既に1だった場合は2にする｣、つまりビットではなくビット列を用いるというものがある*2。
もちろん、上記の如き いーかげん な方法ではなくて、
空のブルームフィルタ?は全て 0 に設定された m ビットのビット配列である。また、同時に k 個のハッシュ関数が定義されており、それぞれがキー値を m 個の配列位置のいずれかにマッピングする。
ので、すぐ｢全部が1になりました!｣になったりしない。また格納する値をハッシュ関数でぐちゃぐちゃして、決定した位置に突っ込むor調べるだけなので
ブルームフィルタ?の珍しい特徴として、要素の追加も要素のクエリも O(k)の固定時間しかかからず、格納されている要素数には全く影響されないのである。
No Comments