初めて学ぶブルームフィルタ

「システム設計の面接試験」という本を読んでいます。
さまざまなアーキテクチャが載っていて非常に面白い本です。
https://www.amazon.co.jp/dp/4802614063

その中でブルームフィルタが面白かったので、仕組みについて学びたいと思います。

ブルームフィルタを学ぶ前に、そもそもどういう場面で使うものなのかを考えましょう。
ブルームフィルタは、ある要素が集合に含まれるかどうか判定するときに使われます。

といってもイメージしにくいですよね。なので問題を考えます。

• 現在の野球選手に山田太郎という名前の選手はいますか？

この問題を考えようと思ったら、野球選手の名簿を作成して、名前を確認していかなければいけません。
野球選手は1000人弱いるのでなかなか大変な作業です。

ブルームフィルタは、このようなある要素（山田太郎）が、集合（現在の野球選手）に含まれるかどうかを判定するときに役立ちます。

では、ブルームフィルタが実際にどういう仕組みなのか、どうやって要素が集合に含まれるかどうか判定するのか見ていきましょう。

シンプルなブルームフィルタ

適当なハッシュ関数を選び、選手をリストに登録していきます。

現在のブルームフィルタ（サイズ10）は、1,3,5,6,9番がTRUEになっています。
このとき、山田太郎が存在するか調べてみます。

このようにブルームフィルタを使うと要素が存在するかどうか判定することができます。
なんでわざわざこんな方法を取るんでしょうか？どんなメリットがあるんでしょうか？

ブルームフィルタのメリット

• ブルームフィルタは要素自体を保持しているわけではないので、軽量。
  • 単純計算だが、選手全員分のデータを取得するとなると選手一人の情報が1KBだとすると、1000人弱で１MB弱になる。しかしブルームフィルタならサイズ分のビットですむ
• 「存在しない」の判定が早い。全員のデータを検査するわけではなく、ハッシュ関数の計算結果を見ればいいので楽。重複チェックなんかで便利

ここら辺がブルームフィルタのメリットとして考えられます。

さて、お気づきかと思いますが、この考え方は問題があります。
それは

ブルームフィルタの問題

• 存在しない要素を「存在します」と判定する可能性がある。（偽陽性といいます）

先ほどのブルームフィルタをもう一度使いますが、

これは仕組みとして仕方ないと思います。
存在しない要素に対して、「存在します」と返すかもしれない、という問題があるとしても、メリットが上回れば採用するもんです。

では、逆はどうなんだ？（存在する要素を「存在しません」と判定する可能性、つまり偽陰性はあるのか？）というと、それはありません。存在する以上、登録する際にブルームフィルタの対応する番号をTRUEにしているからです。

つまりブルームフィルタは、「ある要素が存在するかもしれません」または「存在しません」と返すもの、というわけです。

というわけでまとめです。

まとめ

• ブルームフィルタは、ある要素が集合に存在するかどうか判定するときに使う
• ブルームフィルタは、ある要素が「存在するかもしれません」、または、「存在しません」と返す
• ブルームフィルタが、存在する要素に対して「存在しません」と返すことはない
• 一意なランダムな値を登録するときなんかに便利

ブルームフィルタ by Go

package main

import "fmt"

type BloomFilter struct {
	bitSet []bool
	size   int
}

func NewBloomFilter(size int) *BloomFilter {
	return &BloomFilter{
		bitSet: make([]bool, size),
		size:   size,
	}
}

func (bf *BloomFilter) Add(item string) {
	index1, index2 := bf.hash(item)
	bf.bitSet[index1] = true
	bf.bitSet[index2] = true
}

func (bf *BloomFilter) Contains(item string) bool {
	index1, index2 := bf.hash(item)
	return bf.bitSet[index1] && bf.bitSet[index2]
}

// 適当すぎるハッシュ関数
func (bf *BloomFilter) hash(item string) (int, int) {
	hash1 := 0
	hash2 := 0
	for i := 0; i < len(item); i++ {
		hash1 = (hash1*17 + int(item[i])) % bf.size
		hash2 = (hash2*23 + int(item[i])) % bf.size
	}
	return hash1, hash2
}

func main() {
	bf := NewBloomFilter(10)

	bf.Add("Hello")
	bf.Add("Hi")
	bf.Add("Good Morning!!!")

	fmt.Printf("%v\n", bf.Contains("Hello"))
	// Helloは登録しているのでtrue
	
	fmt.Printf("%v\n", bf.Contains("hungry"))
	// hungryは登録していないが、trueになる。偽陽性
}