この記事はQiitaの記事をエクスポートしたものです。内容が古くなっている可能性があります。
ブルームフィルタとは
探索アルゴリズムのために用いられる確率的データ構造ある。 特定の要素が集合に含まれているかどうかを調べるために使われる。
長所 ハッシュテーブルなどと比較してメモリの使用効率が優れている。 探索の際の計算量も優れており集合への検索、追加ともにO(1)で行われる。
短所 確率的データ構造であり偽陽性による誤検出の可能性がある。(偽陰性はない) [例]
[a, b, c]
という集合があるとき、a
の存在を検索するときは誤ってfalse
を返すことはないが、d
の存在を検索するときは誤ってtrue
を返す可能性もある。
Bloom filter - SlideShareは直感的でわかりやすい。
データ構造
ブルームフィルタはビット配列Bで表される。 mビットの領域、k個のハッシュ関数を用意する。
要素の追加 追加する要素をk個のハッシュ関数に通して0~m-1の範囲の値を得る。 値をビット配列に対する添字とみなし、対応するビットを立てる(1にするなど)。
要素の検索 対象の値に対してk個のハッシュ関数に通して0~m-1の範囲の値を得る。 それぞれが示すビットが全て立っているかで判定する。
具体例で考えてみる。
["beer", "sake", "gin"]
の集合がある。
この集合に対するブルームフィルタをまず作成する。
m=8, k=2
のブルームフィルタを考える。
それぞれのハッシュ値は以下である。
ハッシュ値1 | ハッシュ値2 | |
---|---|---|
beer | 1 | 5 |
sake | 2 | 6 |
gin | 3 | 7 |
whisky | 1 | 7 |
初期のブルームフィルタ
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
ビット | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
例えば、beer
を追加したブルームフィルタ
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
ビット | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
sake
とgin
も追加したブルームフィルタ
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
ビット | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
🍺🍻ブルームフィルタ完成🍶🍸
sake
が含まれているか検索してみる。
ハッシュ値は2,6なので、indexが2,6のところをみると1になっていて集合にsake
が含まれているのがわかる。
whisky
が含まれているか検索してみる。
ハッシュ値は1,7なので、indexが1,7のところをみると1になっていて集合にwhisky
が含まれているということになる。
しかし、これは誤りである。偽陽性である。
実装
Rubyで実装した。 Rubyで文字列で一意にきまるハッシュ値を取得するにあるように、Objectのhashメソッドを使うと実行の度にハッシュ値が変わるので注意。 擬似コードの代わり書くだけなら、hashメソッドでも十分だとおもうが一応sha256を用いた。
require 'digest/sha2' class BloomFilter def initialize(m, k) @bits = Array.new(m, 0) @m = m @k = k end def add(elem) # ビットを立てる @k.times do |i| hash_value = Digest::SHA256.hexdigest(elem + i.to_s).to_i(16) % @m @bits[hash_value] = 1 end end def include?(elem) # ビットが全て立っているか調べる @k.times do |i| hash_value = Digest::SHA256.hexdigest(elem + i.to_s).to_i(16) % @m return false if @bits[hash_value] == 0 end true end end # ブルームフィルタの作成 bf = BloomFilter.new(8, 2) bf.add('beer') bf.add('sake') bf.add('gin') # ブルームフィルタに含まれているか判定 p bf.include?('beer') p bf.include?('sake') p bf.include?('gin') p bf.include?('whisky') # 出力 true true true true
whisky
は含まれていないはずだが、含まれることになってしまっている。
パラメータm,kの選び方によって、偽陽性の割合は変わってくる。
ブルームフィルタの計算量空間量と、偽陽性の割合のトレードオフである。
bitcoinでは、実際にm=36000,k=50が用いられているようだ。 https://github.com/bitcoin/bitcoin/blob/db3cb5c5a686279b220cac13c17b367aa0e4af99/src/bloom.h#L16-L18
どのようにブロックチェーン技術に用いられてるか
ブルームフィルタは、P2Pネットワーク上のSPVノードが受け取るトランザクション(およびそれらを含んでいるブロック)をフィルタリングするために使われる。 SPVノードは、自分のウォレットにあるビットコインアドレスのみにマッチするフィルタを作成する。 ピアにブルームフィルタを送る。 ブルームフィルタにマッチしたトランザクションのみがSPVノードに送られる。
自分がどのアドレスに対するトランザクションを探しているか明らかにすることなく、特定のパターンに適合するトランザクションを確認できる。 正確性とプライバシーのバランスを取ることができる!
SPVノードとは ビットコインのブロックチェーンネットワーク上にはフルブロックチェーンノードと呼ばれるブロックチェーンの情報を全て持っているノードや、自ノードに関する簡単な情報を持っているSPVノードなどさまざまな種類のノードが存在する。SPVは、ブロックチェーンを持たずウォレットなどの情報のみを持つノードである。
参考
http://kakts-tec.hatenablog.com/entry/2017/06/21/004248 https://qiita.com/saka1_p/items/da8f2216d864b0659b8a