やわらかテック

興味のあること。業務を通して得られた発見。個人的に試してみたことをアウトプットしています🍵

トップ > Algorithm > pythonでブルームフィルターを作って覚える

pythonでブルームフィルターを作って覚える

Algorithm Python データベース

ブルームフィルター(Bloom Filter)とは

ブルームフィルターというのは1970年にブルームさんが作った確率的データ構造と呼ばれるデータ構造の1つです。
データ構造というのは

  • 配列
  • 連想配列
  • リスト

などをイメージしてもらえば良いのですが、確率的データ構造という言葉はあまり聞き馴染みがありません。

確率的データ構造というのは簡単に言えば「値がデータ構造に入っているか、いないかをを知ることが出来るデータ構造」のことをいいます。 以下の例では5の値がlstに含まれているかを判定したいとします。pythonであればsearch_val in lstとすれば5の値がlstに含まれているかを簡単に判定することが出来るので、リスト(lst)は確率的データ構造の1つであるといえます。

search_val = 5
lst = [1,2,3,4,5,6,7,8,9]

ブルームフィルターの最大の特徴としては含まれていないものを含んでいる(偽陽性)と誤判定してしまうことがあるが、含まれていないものを含まれていない(偽陰性)と誤判定することはないという点です。

つまり、含まれていると判定されたとしても本当は含まれていないということはありますが、含まれていないと判定された場合に、その値は必ず含まれていないことが保証されます。

ブルームフィルターの仕組み

そんな確率的データ構造の1つであるブルームフィルターはMビットの配列とN個のハッシュ関数によって作られます。今回は実装の都合上、Mビットの配列はM個の要素を持つリストとして話を進めていきます。

まずはじめにM個の要素を持つリストとN個のハッシュ関数が用意されます。今回は10個の要素と2つのハッシュ関数が用意されていると仮定します。
補足として、ハッシュ関数とはデータを別のデータに変換する関数で、変換されたデータは元のデータに戻すことは出来ません。ハッシュドポテトからじゃがいもに戻すことが出来ないとイメージしてもらうと分かりやすいかと思います。

bloom_filter = [0, 0, 0, 0 ,0, 0, 0, 0, 0, 0]

# 何かしらのハッシュ処理A
def hash_a(val):
  return hashed_val

# 何かしらのハッシュ処理B
def hash_b(val):
  return hashed_val

次にブルームフィルターに登録したい値("hello world")を用意して、それぞれのハッシュ関数を使って値をハッシュ化します。ハッシュ関数は必ずブルームフィルター(リスト)のインデックスに対応する値を返します(今回の場合だと0 ~ 9)。

val = "hello world"
a_hashed = hash_a(val) # 1
b_hashed = hash_b(val) # 4

これでa_hashedとb_hashedの2つの値を得ることが出来ました。それぞれのインデックスに対応する値を0から1に更新します。

bloom_filter[a_hashed] = 1
bloom_filter[b_hashed] = 1
# bloom_filter
[0, 1, 0, 0, 1, 0, 0, 0, 0, 0]

同じ操作を別の値で何度か繰り返します。最終的にブルームフィルターは以下のようになったとしましょう。

# bloom_filter
[1, 1, 0, 0, 1, 0, 0, 1, 1, 1]

しばらくして、"hello world"がブルームフィルターに登録されているかを忘れてしまったので判定することになりました。ブルームフィルターの手順に従って値が登録されているかを確認します。

値を登録した時と同様に"hello world"を2つのハッシュ関数を使ってハッシュ化させます。当然、同じハッシュ関数を使用しているので結果は1, 4になります。

val = "hello world"
a_hashed = hash_a(val) # 1
b_hashed = hash_b(val) # 4

得られた値をインデックスとしてブルームフィルターを参照してみると、全ての値が1になっていることが分かるので値はブルームフィルターに登録されていたということが分かります。

bloom_filter[a_hashed] # 1
bloom_filter[b_hashed] # 1

逆にハッシュ関数から得られたインデックスで参照した値が全て1ではないということはブルームフィルターに値は登録されていません。これは先ほど説明したように登録されていないことは必ず保証されます。

なぜ含まれていない値が含まれていると判定されてしまうのか

すでにお気づきの方もいるかと思いますが、ブルームフィルターのサイズが小さかったり、ハッシュ関数が異なる値に対して同じ値を返してしまったりするとブルームフィルターのインデックスが重複するケースが発生します。

そうなると異なる値であっても同じインデックスに対して0 -> 1の更新を行うため、含まれていない値を含まれていると判定してしまいます。

val1 = "hello world"
a_hashed = hash_a(val1) # 1
b_hashed = hash_b(val1) # 4
:
# bloom_filter
[0, 1, 0, 0, 1, 0, 0, 0, 0, 0] 

val2 = "hello worlddd"
a_hashed = hash_a(val2) # 2
b_hashed = hash_b(val2) # 4
:
# bloom_filter
# 4が重複した!
[0, 1, 1, 0, 1, 0, 0, 0, 0, 0]

また、この特性上、一度、登録した値を取り除くことが出来ませんので注意が必要です。

作ってみる

さっそくコードを書いて見ます。まずはM個の要素を持つ配列を作るようにします。
※どんどん手を加えていくのでクラスで実装していきます

# 後で使うので先にimport
import functools

class BloomFilter:
  def __init__(self, filter_size):
    self.filter_size = filter_size
    self.bloom_filter = [0 for _ in range(filter_size)]

次は受け取った値をハッシュ化する関数を作っていきます。今回は簡単にPythonに実装されているhashを使って文字列から19桁の数値を作成して、都合上、各桁を足し合わせる関数と2倍にして足し合わせる関数を作成します。

この関数はハッシュ関数であれば何でも良いので自由に作ってみてください。

val = "hello world"
hashed = abs(hash(val)) # 4008655217928885438 負の数になることがあるためabsで正の数に変換
a_hashed = 4 + 0 + 0 + 8 + ... + 3 + 8
b_hashed = abs(4 - 0 - 0 - 8 - ... - 3 - 8) # 負の数になることがあるためabsで正の数に変換

それぞれハッシュ関数の値がインデックスに対応するようにMを超過しないようにします。ハッシュ関数のコードと合わせて以下のようになります。

import functools

class BloomFilter:
  def __init__(self, filter_size):
    self.filter_size = filter_size
    self.bloom_filter = [0 for _ in range(filter_size)]
  
  def set_v(self, val):
    indexes = self.n_hash(val)
    for index in indexes:
      self.bloom_filter[index] = 1
  
  def n_hash(self, val):
    hashed = abs(hash(val))
    d_list =  [int(n) for n in str(hashed)]
    return [
      self._hash_common(lambda acc, d: acc + d, d_list),
      self._hash_common(lambda acc, d: acc + 2 * d, d_list),
    ]
  
  def _hash_common(self, func, d_lst):
    execed = abs(functools.reduce(func, d_lst, 0))
    while execed >= self.filter_size:
      execed = execed / self.filter_size
    return int(execed)

結果を見て見ます。ブルームフィルターのサイズは適当に10としました。

bf = BloomFilter(10)
print(bf.n_hash(3)) # [3, 6]

更新をするブルームフィルターのインデックスを求められるようになったので、該当するインデックスの値を更新する処理を追加します。

class BloomFilter:
  # 割愛
  def set_v(self, val):
    indexes = self.n_hash(val)
    for index in indexes:
      self.bloom_filter[index] = 1

更新されていることが分かります。

bf = BloomFilter(10)
print(bf.bloom_filter) # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
bf.set_v(3)
print(bf.bloom_filter) # [0, 0, 0, 1, 0, 0, 1, 0, 0, 0]

最後にブルームフィルターに値が格納されているかどうかを調べるexist_vという関数を追加します。

class BloomFilter:  
  def exist_v(self, val):
    indexes = self.n_hash(val)
    for index in indexes:
      if self.bloom_filter[index] == 0:
        return False
      return True

問題なく判定されました。

bf = BloomFilter(10)
bf.set_v(3)
print(bf.exist_v(3)) # True
print(bf.exist_v(10)) # False

検証

ブルームフィルターのサイズをもう少し大きくしていくつか適当な値を追加してみます。どのような結果になるか楽しみです。

bf = BloomFilter(30)
selected_number = [1,3,4,7,9,12,16,20,24,27,33,39,41,44,47,50]
for n in selected_number:
  bf.set_v(n)
print(bf.bloom_filter)
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]

まずは格納されている値が必ず格納されていると判定されることを確かめます。

# allでリストの要素が全てTrueかを判定。全て含まれていればTrueになるはず
print(all([bf.exist_v(n) for n in selected_number]))
# True

次に、偽陰性を検証するためにブルームフィルターに格納済みの値を取り除いた1~100の数値でexist_vが`Trueになる値がないか見てみます。

not_exist_numbers = list(set([n for n in range(1, 101)]) - set(selected_number))
# anyでリストの要素に1つでもTrueかを判定。1度でも含まれていると判定されていればTrueになるはず
print(any([bf.exist_v(n) for n in not_exist_numbers]))
# True

偽陰性を確認することができました。こうしてみると、結構な数の値が含まれていると誤判定されてしまっています。

print(len(not_exist_numbers)) # 84
print(len([n for n in not_exist_numbers if bf.exist_v(n)])) # 72

ブルームフィルターのサイズが小さい、ハッシュ関数の個数が少ない、ハッシュ化の処理が不適切など、チューニングすべき箇所はいくらでもありそうです。

参考文献