アルゴリズムクイックリファレンス 第2版

130

■

5

章 探索

5.4.3

 解

ブルームフィルタ

は、

m

ビットストレージを必要とする。例 5-10の実装では、

Python

のどれほど大きな「

bignum

」値

＊

1

でも扱える能力を使用する。

例

5-10

 

Python

ブルームフィルタ

class bloomFilter:

def __init__(self, size = 1000, hashFunctions=None):

"""

size

個のビット

(

デフォルトは

1000)

と関連ハッシュ関数でブルームフィルタを作る。

"""

self.bits = 0

self.size = size

if hashFunctions is None:

self.k = 1

self.hashFunctions = [lambda e, size : hash(e) % size]

else:

sel

f.k = len(hashFunctions)

self.hashFunctions = hashFunctions

def add(self, value):

"""

ブルームフィルタに値を挿入する

"""

for hf in self.hashFunctions:

self.bits |= 1<<hf(value, self.size)

def __contains__(self, value):

"""

値があるかどうか決定する。値が存在しなくても偽陽性を返すことがある

しかし、偽陰性は決して返さない（すなわち、要素があれば

true

を返す）