Bloom filterって夏の匂いがするよな
Bloom filterとは
tags: 情報
近況報告
どうも.最近家の近くの公園で毎週土曜日に在野ラップ大会が開かれていることに気付いたピカチュウです.
今回は確率的データ構造で色々と使われているらしいが弊学科の授業で扱われていないBloom filterについてまとめていきたいと思います.
(Youtuber風)
そもそもBloom filterとは
上で述べたようにBloom filterとはハッシュ関数を使った確率的データ構造です.
ある要素がある集合に属するかどうかを調べるためにハッシュ関数を用いています.
ハッシュ関数ってなんだっけ?という人のためにハッシュ関数の説明をします.
ハッシュ関数
ここでは重要な特性だけを言います.
入力を「ある範囲に」,「一様に分布する」ように,「一意」に写像する関数です.(決定的であるのは関数であることから明らかだと思っているのですが違いますかね?)
つまり,ある値からある値までに(無限に異なる値を入力したら)等確率に写像します
具体的な実装(の説明)
話を戻して,具体的にどのように実装をしているかを話します(ゆるふわです)
以下出てくる値は全て整数です
挿入
- まず,長さmの配列とk個のハッシュ関数を用意します($k<m$とします).ハッシュ関数は$[0,m-1]$の値を出力します
- 配列の要素を全て0で初期化します
- 与えられた入力を$k$個のハッシュ関数に通し,$k$個の出力を得ます
- 出力された添字の配列要素を1とします(フラグを立てます)
検索
- 入力を$k$個のハッシュ関数に通します
- 出力された添字の配列要素に0があれば,その要素は集合に含まれない.なければ集合に含まれるとします
例
長さ10で全ての要素が0である配列を用意します.
ハッシュ関数として$f(x) = x % 7$と$g(x) = x % 6$を用意します
5と16を挿入してみます.
- $5 \% 7 = 5$
- $5 \% 6 = 5$
- $15 \% 7 = 1$
- $15 \% 6 = 3$
なので,配列の添字が1, 3, 5となっている要素を1にします(フラグを立てます)
32が挿入されているか調べます.
- $32 \% 7 = 4$
- $31 \% 6 = 2$
なので添字が2, 4となっている部分を調べますが1ではありません.挿入されていないとわかります.
今度は41を例に,偽陽性が本当にされるかを見てみます.
$41\%5 = 1$, $41\%6 =5$なので入っていることに!!!
偽陽性ですね
メリット・デメリット
メリット
- 高速な検索・挿入が可能です
- ハッシュ関数の数,つまりkに比例した計算量が必要です
デメリット
偽陽性 | 偽陰性 |
---|---|
AでないのにAであると判定すること | AであるのにAでないと判定すること |
- 削除ができない
- Bloom filterの実装からわかるようにある値の削除をすると他の値の削除までしてしまう可能性が有ります
どんなところで使われているか
Mediumの記事の属性判定や,Bitcoinのトランザクションなどで使っているらしいです.
前者は記事を読みましたが,Bitcoinはまだ論文を読んだことがないので事実かどうか判定ができないです