Goでのアルゴリズムクイックリファレンス第2版(ブルームフィルタ)

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フィルターについて調べた

次回は二分探索木です。