Bloomフィルターについて調べた

Posted bysiguniangPosted inalgorithmTags:, , ,

Eric Redmond & Jim R. Wilson 著の”Seven Databases in Seven Weeks” を読んでいたところ、Ch.8 Redis の Day2 で書籍名の重複チェックに Bloom Filter という確率的データ構造(アルゴリズム?)が利用されていた。本ではさらっとしか触れられていなかったので調査。

処理の流れ

材料

  • ビット配列(m ビット)
  • ハッシュ関数(k個。整数1からm のどれかをかえす)

作り方

下ごしらえ

  • ビット配列の各ビットは予め0で初期化しておく。
  • 各初期データをk個のハッシュ関数に食わせ、ハッシュ関数のかえすビットを立てる。

重複チェック

  • 重複チェックしたい入力値をk個のハッシュ関数に食わせる
  • ハッシュ関数のかえすビットがビット配列で立っているかチェック
    すべてのビットが立っていれば、重複と判定。
    一つでも立っていないビットがあれば、重複していないと判定。

処理の流れの具体例

下ごしらえ

※ m = 16, k = 3

  1. まず、ステップ1でビット配列を0で初期化
  2. ステップ2では入力”a”のハッシュ値 2, 6, 13 のビットを立てる
  3. ステップ3では入力”b”のハッシュ値 4, 10, 11 のビットを立てる
  4. ステップ4では入力”c”のハッシュ値 6, 11, 12 のビットを立てる
    (6ビット目、11ビット目はすでに立っているが、そのまま立てておく。このようにデータの数に対して m が小さいと特定のビットを複数の入力値が共有しやすくなる)

重複チェック
ビットの立ち方を3パターン考える

  1. 5a の場合、15ビット目がもともと立っていなかったので重複でないと判定できる(false negative にはならない)
  2. 5b の場合、すべてのビットが立っているので重複と判定できる。
    ステップ1から処理を追っていくと、”a” と “b” の2つの入力で立ったビットなので、実際は重複ではなく偽判定(false positive)。しかしBloom filter は最新のビット列しか持っておらず、各入力値とビットのペアを持っているわけではないので、このような偽判定が起こる。
  3. 5c の場合、すべてのビットが立っているので重複と判定できる。
    ビットの立ち方はステップ3の”b”と同じだが、入力値は別だけれどもk個のハッシュ値がたまたま衝突したのか、それとも、入力値が同じだったのかは判断がつかない。

以上から、 false positive はあり得るけれども、false negative はあり得ない という性質を持つ

インタラクティブに動作を確認したいという方は、次の URL をどうぞ。ハッシュ関数は2個(k=2)で KNV(Fowler–Noll–Vo) と murmur を採用している。

http://llimllib.github.com/bloomfilter-tutorial/

Python での実装

Python には pybloom という Bloom フィルターのライブラリがある。
これを利用するという手もあるけれども pybloom が依存している bitarray ライブラリのサンプルコードに Bloom filter のミニマルなわかりやすい実装があったので、これを元に解説。
bitarray のインストールは $ pip install bitarray でOK

https://github.com/ilanschnell/bitarray/blob/master/examples/bloom.py

import hashlib
from bitarray import bitarray

class BloomFilter(object):

    def __init__(self, m, k):
        self.m = m
        self.k = k
        self.array = bitarray(m)
        self.array.setall(0)

    def add(self, key):
        for i in self._hashes(key):
            self.array[i] = 1

    def contains(self, key):
        return all(self.array[i] for i in self._hashes(key))

    def _hashes(self, key):
        """
        generate k different hashes, each of which maps a key to one of
        the m array positions with a uniform random distribution
        """
        h = hashlib.new('md5')
        h.update(str(key))
        x = 0
        for _ in xrange(self.k):
            if x < self.m:
                h.update('.')
                x = long(h.hexdigest(), 16)
            x, y = divmod(x, self.m)
            yield y

メソッドは次の4つ

  • __init__(コンストラクター)
  • add(追加)
  • contains(重複チェック)
  • _hashes(ハッシュ値)

__init__ では m, k を指定し、mビットのビット列を0で初期化している。
add ではハッシュ値の返す各ビットを立てている。
少し込み入っているのは _hashes

md5 のハッシュ値(x)を順次ビット配列のサイズ(m)で割り、余りのビットを立てるようにしている。

bits = []
for k 回:
  x = r * m + y  # y ビット目を立てる
  bits.add(y)
  x = r

m = 16, k = 3, x = 654321 の場合

654321 = 16 * 40895 + 1
40895  = 16 * 2555  + 15
2555   = 16 * 159   + 11

となるので 1, 15, 11 のビットを立てる。実用上は、k個のハッシュ関数をどう選ぶのかというのは、処理速度やハッシュ関数の性能の点で重要になる。
False Positive 率

wikipedia によると ハッシュ関数が一様乱数であるという前提で、理論上の false positive 率はたかだか

目的に応じて、データ数 n と許容できる false positive 率を元に、m,  k を調整する必要がある。

利用例

wikipedia によると

  • Google BitTable のキーのルックアップ
  • Chrome のセーフブラウズURLチェック
  • Squid のキャシュのダイジェスト値

などで利用されている。分散 NoSQL の Riak も 1.2 以降から検索時のキーの存在チェックで利用するようになっている。組込み型KVS の LevelDB も 1.4 以降から riak と同様の理由で組み込まれている。

PyCon 2011では Michigan State Univ の Titus Brown の発表 “Handling ridiculous amounts of data with probabilistic data structures“で Bloom Filter が紹介されている。

Counting Bloom Filter

Bloom Filter の削除操作
Bloom Filter において、追加と同じ手順で削除すると false negative が起こりうる。
たとえば、ビットの立ち方が

  • ‘a’ : [0,1,1,0,0]
  • ‘b’ : [0,1,1,0,1]

の場合、’a’, ‘b’ を追加すると [0,1,1,0,1] になる。
追加と同じ手順で ‘a’ を削除すると、アレイ [0,1,1,0,1] は [0,0,0,0,1] になる。
このアレイに対して ‘a’, ‘b’ の存在チェックをすると、両方とも False になり、後者は False Negative。

もっと自明な例として、’a’, ‘b’ でビットの立ち方が同じ([0,1,1,0,0])だった場合、’a’, ‘b’ を追加すると [0,1,1,0,0]。
‘a’ を削除すると[0,0,0,0,0]。
‘a’, ‘b’ の存在チェックをすると、両方とも False になり、後者は False Negative。

single bit から N-bit bucket への拡張

1 bit で管理されているアレイの各値を N bit(のbucket) にデータサイズを増やし、追加があるたびに値をインクリメントする。削除の場合はデクリメントする。

  • ‘a’ : [0,1,1,0,0]
  • ‘b’ : [0,1,1,0,1]

の場合、’a’, ‘b’ を追加すると [0,1,2,0,1] になる。
追加の逆操作で ‘a’ を削除すると、アレイ [0,1,2,0,1] は [0,0,1,0,1] になる。
このアレイに対して ‘a’, ‘b’ の存在チェックをすると、それぞれ False/True で期待通り。

‘a’, ‘b’ でビットの立ち方が同じ([0,1,1,0,0])だった場合、’a’, ‘b’ を追加すると [0,2,2,0,0]。
‘a’ を削除すると[0,1,1,0,0]。
‘a’, ‘b’ の存在チェックをすると、それぞれ True(false positive)/True で false negative は発生しない。
このデータ構造を “Counting Bloom Filter” という。

Counting Bloom Filter の注意点

bucket サイズを大きくすれば、フィルターのデータサイズも大きくなる。
1 bit array が N bit array になれば、データのサイズは N 倍になる。

Counting Bloom Filter の実装
Bloom Filter のコードをベースにした Counting Bloom Filter を実装してみる

  • 追加/削除はそれぞれ add/remove メソッドで行う。
  • bitarray の代わりに list(または SciPy の array) で管理。
# http://en.wikipedia.org/wiki/Bloom_filter#Counting_filters
# http://www.michaelnielsen.org/ddi/why-bloom-filters-work-the-way-they-do/
import hashlib
class BloomFilter(object):
def __init__(self, m, k):
self.m = m
self.k = k
self.array = [0 for i in range(m)]
#import scipy # if scipy installed
#self.array = scipy.zeros(m, dtype=int)
def __str__(self):
return self.array.__str__()
def add(self, key):
for i in self._hashes(key):
self.array[i] += 1
def remove(self, key):
if self.contains(key):
for i in self._hashes(key):
self.array[i] -= 1
def contains(self, key):
return all(self.array[i] for i in self._hashes(key))
def _hashes(self, key):
"""
generate k different hashes, each of which maps a key to one of
the m array positions with a uniform random distribution
"""
h = hashlib.new('md5')
h.update(str(key))
x = 0
for _ in xrange(self.k):
if x < self.m:
h.update('.')
x = long(h.hexdigest(), 16)
x, y = divmod(x, self.m)
yield y
def test_bloom(m, k, n):
b = BloomFilter(m, k)
for i in xrange(n):
b.add(i)
assert b.contains(i)
print b
b.remove(3)
print b
if __name__ == '__main__':
test_bloom(100, 3, 10)
view raw counting_bloom_filter.py hosted with ❤ by GitHub

References

Leave a comment