Bloom Filterを書いてみた

Pythonで

• Bloom filter - Wikipedia

Bloom Filterはデータが入ってるかどうかを問い合わせるもの。一種のSetのようなものだが、確率的に誤検出の可能性がある。特徴は、保持するデータが固定長のビットフィールドで元データが不要であり、ビット和で足し合わせられること。前者は通信で送ったりするのに便利だし、後者は分散処理(させてまとめる)などで使える。

import hmac

class BitFields(object):
    def __init__(self):
        self.bits = 0 
        pass
    def __getitem__(self, index):
        return (self.bits & (1 << index)) != 0

    def __setitem__(self, index, bool):
        if bool:
            self.bits = self.bits | (1 << index)
        else:
            self.bits = self.bits & ~(1 << index)
            pass
        pass

    def __add__(self, other):
        ret = BitFields()
        ret.bits = self.bits | other.bits
        return ret
    pass

class BloomFilter(object):
    def __init__(self, size=1024, max=100):
        self.size = size
        self.max = max
        self.k = int(0.7 * size / max)
        self.space = BitFields()
        pass

    def __add__(self, other):
        if self.size != other.size or self.k != other.k:
            raise Exception("size not matched")
        ret = BloomFilter(self.size, self.max)
        ret.space = self.space + other.space
        return ret

    def push(self, data):
        for index in self._indexes(data):
            self.space[index] = True
            pass
        pass

    def include(self, data):
        for index in self._indexes(data):
            if not self.space[index]:
                return False
            pass
        return True

    def _indexes(self, data):
        datastr = repr(data)
        func = lambda a, b: ((a << 8) + b) % self.size
        for i in xrange(self.k):
            digest = hmac.new(str(i), datastr).digest()
            index = reduce(func, (ord(ch) for ch in digest)) % self.size
            yield index
            pass
        pass
    pass

if __name__ == "__main__":
    bf = BloomFilter()
    bf.push("foo")
    bf.push("bar")
    print "expect: True True False False"
    print bf.include("foo")
    print bf.include("bar")
    print bf.include("buzz")
    print bf.include("bas")

    bf2 = BloomFilter()
    bf2.push("taro")
    bf2.push("jiro")
    print "expect: True True False False"
    print bf2.include("taro")
    print bf2.include("jiro")
    print bf2.include("saburo")
    print bf2.include("bas")

    bf3 = bf2 + bf
    print "expect: True True True True False False False"
    print bf3.include("taro")
    print bf3.include("jiro")
    print bf3.include("foo")
    print bf3.include("bar")
    print bf3.include("buzz")
    print bf3.include("bas")
    print bf3.include("saburo")
    pass

最初、data.__hash__()をk分割するものをハッシュ関数につかってみたけど、上記の例でbf3のbasで誤検出されてしまった。そこでhmacを使うことにしたしだい。

digest値をindexにするのにreduceをつかったけど、こういう場合はreduceよりもfoldlのほうが使いやすいなあ。