kakts-log

programming について調べたことを整理していきます

確率的データ構造・ブルームフィルタについてのまとめ

概要

特定のデータが、ある集合やリストに含まれるかどうかを判定するために、線形探索や二分探索など、いくつかのサーチアルゴリズムがありますが、
本稿ではメモリの使用効率、探索の際の計算量が優れているブルームフィルタを用いたアルゴリズムについてまとめます。

ブルームフィルタとは

ブルームフィルタとは確率的データ構造の一種で、あるデータが集合に属するかどうかを判定する際に使われます。
特徴としては、メモリの空間消費が少なくすみ、非常に効率的にデータの存在判定ができます。
デメリットとしては、false-positive(偽陽性)によるデータの誤判定の可能性があり、集合に存在しないデータを存在すると誤判定してしまう場合があります。このような誤判定が許されないような状況においては、ブルームフィルタは使えません。 逆に、false-negative(偽陰性)による誤判定はないため、データは実際にあるのに存在しないと判定することはありません。

ブルームフィルタ - Wikipedia

ブルームフィルタのデータ構造について

ハッシュベースサーチは集合Cのすべての要素をリンクトリストもしくはオープンアドレスハッシュテーブルHに格納する どちらのケースにおいても、多くの要素がハッシュテーブルに格納され、要素の格納に係る時間は、要素数が増えるに従い増えていく。 実際、この振る舞いは他のサーチアルゴリズムにも共通したもので、要素の探索にかかる比較時間とのトレードオフとなる。

ブルームフィルターはビット配列Bを提供し、集合CからBに追加することと、特定の要素EがBに存在するかどうかの判定は定数時間で行うことができ、驚くことに、これは既にBに格納されたデータ数とは独立しています。
しかし、ブルームフィルターにおいては、要素がBに存在するか判定する際に、 false-positiveである場合があります。 つまり、実際には存在しないのに、存在すると判定してしまう場合があります(日本語で言うと偽陽性

False-positiveになる簡単な例

例 下記のテーブルは、u,v,w,zの4つのデータに対して、ハッシュ関数3つそれぞれで得られたハッシュ値をまとめています。

ハッシュ値1 ハッシュ値2 ハッシュ値3
u 1 3 8
v 2 4 8
w 1 2 6
z 1 2 3

u, v, wの3つのデータを集合Cに追加したときのビット配列は 下記の通りになるとします。

配列のインデックス 0 1 2 3 4 5 6 7 8 9
ビット 0 1 1 1 1 0 0 0 1 0

このとき、このビット配列をもとに、u, v, w, zのそれぞれが集合Cに存在するかを判定します。

各データに対して計算された 3つのハッシュ値をビット配列のインデックスとみなし、ビット配列の各インデックスの値をチェックします。
データuについて見てみると、インデックスは 1, 3, 8となります。 ビット配列の 1, 3, 8番目の値をみると、それぞれ1となるので、データuが集合Cに存在すると判定されます。 これは、実際にデータuは集合Cに追加されているので、正しい振るまいです。データv, wにおいても同様に存在すると判定されます。

ここで、実際に集合Cに追加されていないデータzについて見てみます。 3つのインデックスは 1, 2, 3となりますが、それぞれビット配列の要素を調べてみると、どれも1となり、データzは集合Cに存在していないに、存在すると判定されます。 これがfalse-positiveの一例です。
言うまでもなく、ブルームフィルタの実装において、このfalse-positiveの割合が低ければ低いほど、ブルームフィルタの精度が高くなります。
この精度向上のためには、ハッシュ値を均等に出力するハッシュ関数をどう実装するか、さらにはビット配列の長さをどうするかも重要になります。

pythonですが簡単な実装は以下の通りになります。

Best, Average Worst: O(k)

create(m)
    return bit array of m bits
end

add (bits, value)
    # Kビットある場合、ビット毎にの桁を計算するためK個分のハッシュ関数がある
    foreach hashFunction hf
        ## << left シフトオペレータをつかって2^(hf)を効率的に計算できる
        setbit = 1 << hf(value)
        bits |= setbit
end

search(bits, value)
    foreach hashFunction hf
        checkbit = 1 << hf(value)
        # もしチェックビットが0だったら求める値は存在しない
        if checkbit | bits = 0 then
            return false

         # false-positiveすべてのビットがセットされているが求める値は追加されていない
    return true
end

ブルームフィルタの入出力

ブルームフィルタはデータをハッシュベースサーチのように処理する。 アルゴリズムはmビットのすべてが0になっているビット配列Mからスタートする。 データが追加される時、k個のハッシュ関数が、Mの配列内のビットの位置を計算する。

ブルームフィルタのコンテキスト

ブルームフィルタは、メモリの使用量が少なくすみ、非常に効率的ですが、利用可能な条件があり、 それは先程説明したfalse-positiveに関して許容されるときです。

有効的な活用法としては、探索コストの高いデータ探索(diskドライブへのアクセスが行われる場合)などに、前段として ブルームフィルタを導入し、false-positiveなケースはあるが、事前にデータ存在判定を行う事が挙げられます。

solution

ブルームフィルタは mビットのデータが必要です。 下記の実装は

class bloomFilter:
    def __init__(self, size = 1000, hashFunctions=None):
        """
        指定したサイズのビット数をもつブルームフィルタを作成する。
        同時にハッシュ関数も作成する
        """

        self.bits = 0
        self.size = size

        if hashFunctions is None:
            self.k = 1
            self.hashFunctions = [lambda e, size : hash (e) % size]
        else:
            self.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):

        """
        valueがブルームフィルタに存在するか判定する。
        ブルームフィルタの性質上 false-positiveな状態が発生しうる
        この場合、実際にデータは存在しないのにtrueを返してしまう。
        しかし false-negativeは起こり得ない
        """
        for hf in self.hashFunctions:
            if self.bits & 1 << hf(value, self.size) == 0:
                return False

            return True

この実装は、k個のハッシュ関数が存在していることを前提としており、各ハッシュ関数

データが追加されるときは毎回、k個のビットが、ハッシュ関数によって計算されたビット位置に対してセットされます。

分析

ブルームフィルタに必要なメモリ容量は mビットで固定されている。
このメモリ容量は、追加されるデータ量に応じて増加することはありません。

さらに、このアルゴリズムはデータの探索と追加毎にk回操作しか行わないため、O(k)時間で1回の操作が完了します。 kは数値なので、定数時間で処理ができるためかなり速いです。

各データに対して、偏りなく効率的にビット値を計算するアルゴリズムを設計するのは非常に難しいことで、ビット配列のサイズは定数だが、false-positiveが発生するレートを極力下げる必要があります。

さらに重要な特徴としては、ブルームフィルタはデータを削除することは仕組み上できないです。
例をあげると、もし1つのデータを消す場合 k個のハッシュ関数によって(1, 3, 5 ,8, 9)というハッシュ値を持っていた場合、他のデータで(1, 3, 5 ,8, 9)のハッシュ値のうちどれか1つでも持っているデータに関する情報もブルームフィルタから消えてしまうため、判定できなくなるためです。

まとめ

ブルームフィルタのデータ構造、探索ロジックについて簡単ですがざっくりとまとめました。
ブルームフィルタを利用する上で考慮すべき、false-positiveの発生確率については、また別記事でまとめたいと思います。