Bloom filterのシンプルな実装 - 西尾泰和のはてなダイアリー

Bloom filterは指定されたものがリストに含まれるならばTrue、含まれないならばFalseを返すようなデータ構造である。もちろん、単純にリストを保持するだけでもリストに含まれるかどうかの判定は可能だが、Bloom filterのメリットはオリジナルのリストを保存しておく必要がないという点にある。そのためメモリの消費量を格段に節約することができる。しかし、そのメモリ効率の代償として多少正確性が失われる。Bloom filterは指定されたものがリストにない場合でもたまにTrueを返すのだ。しかし、間違ってTrueを返す確率はあらかじめ計算することができるので、誤差が許容できる範囲であれば問題なく使うことができる。

下記はアルゴリズム勉強用のシンプルな実装である。

SIZE = 1987
def hashes(s):
    xs = [0, 0, 0]
    for c in s:
        o = ord(c)
        xs[0] = xs[0] * 137 + o
        xs[1] = xs[1] * 69 + o
        xs[2] = xs[2] * 545 + o

    return [x % SIZE for x in xs]

class BloomFilter(object):
    def __init__(self):
        self.bitarray = [0] * SIZE

    def add(self, s):
        for x in hashes(s):
            self.bitarray[x] = 1

    def query(self, s):
        return all(
            self.bitarray[x] == 1
            for x in hashes(s))

hashes関数は3つの異なるハッシュ関数を使って3つのハッシュ値を計算して返す。BloomFilterはビットアレイを持つが、ここでは実装の簡潔さのためにリストで代用している。これはBloom filterのメリットを大きく損なうので、実用的な目的でこのコードを使ってはいけない。

下記はPythonのインタラクティブシェルで試した結果である。

>>> bf = BloomFilter()
>>> bf.add("hoge")
>>> bf.query("hoge")
True
>>> bf.query("hoga")
False
>>> bf.add("foo")
>>> bf.add("bar")
>>> bf.add("baz")
>>> bf.query("hoga")
False
>>> bf.query("foo")
True

文字列がaddされたとき、Bloom filterはハッシュ値を計算して、ビットアレイの対応する場所に1を書き込む。文字列がqueryされたときは、またハッシュ値を計算して、対応する場所がすべて1である場合に限りTrueを返す。想像できると思うが、文字列をどんどんaddしていくと、ビットアレイはどんどん1だらけになり、BloomFilterはTrueと答えやすくなる。間違えてTrueと答える確率は簡単に推定できる。ビットアレイのサイズをm、ハッシュ関数の数をk、追加する文字列の数をnとすると、問題の確率は(1 - exp(-float(k * n) / m)) ** kになる。このコードの場合であれば、m は 1987、k は 3である。なのでnが100の時、確率は0.003、nが1000の時、確率は0.47になる。1000個の文字列をaddしたいならビットアレイのサイズを増やす必要がある。

You can see the English version here: NISHIO Hirokazu's blog: [Python]Simple Impl. of Bloom Filter