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にあった実装を参考にさせていただきました。

参考
- Bloom filterのシンプルな実装
- Bloomフィルターについて調べた

次回は二分探索木です。