Goに慣れるためとアルゴリズムの復習の為に週1ぐらいで更新していきます。アルゴリズムクイックリファレンス 第2版を読んで各種アルゴリズムをGoで実装して行きます。
前回: Goでのアルゴリズムクイックリファレンス第2版(ハッシュに基づいた探索)
今回はブルームフィルタ
ブルームフィルタ（Bloom Filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、要素が集合のメンバーであるかどうかのテストに使われる。偽陽性（False Positive）による誤検出の可能性があるが、偽陰性（False Negative）はない。要素を集合に追加することができるが、削除することはできない（Counting filter を使えば削除できる）。集合に要素が追加されればされるほど、偽陽性の可能性が高くなる。
- アルゴリズム
- 全て 0 に設定された m ビットのビット配列
- k 個のハッシュ関数が定義されており、それぞれがキー値を m 個の配列位置のいずれかにマッピング
package main
import "fmt"
const SIZE = 1999
func hashes(a *[]int) []int {
xs := []int{0, 0, 0}
for _, v := range *a {
xs[0] = xs[0]*137 + v
xs[1] = xs[1]*69 + v
xs[2] = xs[2]*545 + v
}
hashes := make([]int, 3)
for i, _ := range xs {
hashes[i] = xs[i] % SIZE
}
return hashes
}
type BloomFilter struct {
BitArray *[]int
}
func (bf *BloomFilter) add(a *[]int) {
for _, v := range hashes(a) {
(*bf.BitArray)[v] = 1
}
}
func (bf *BloomFilter) query(a *[]int) bool {
for _, v := range hashes(a) {
if (*bf.BitArray)[v] == 0 {
return false
}
}
return true
}
func main() {
ba := make([]int, 0)
for i := 0; i < SIZE; i++ {
ba = append(ba, 0)
}
bf := &BloomFilter{&ba}
ary := []int{1, 2, 3}
bf.add(&ary)
if bf.query(&ary) {
fmt.Println("ok")
}
ary2 := []int{1, 2, 3, 4}
if !bf.query(&ary2) {
fmt.Println("ng")
}
}
西尾さんのblogにあった実装を参考にさせていただきました。
次回は二分探索木です。