概要
特定のデータが、ある集合やリストに含まれるかどうかを判定するために線形探索や二分探索などいくつかのサーチアルゴリズムが使われますが、
本稿ではメモリの使用効率、探索の際の計算量が優れているブルームフィルタを用いたアルゴリズムについてまとめます。
ブルームフィルタとは
ブルームフィルタとは確率的データ構造の一種で、あるデータが集合に属するかどうかを判定する際に使われます。
特徴としては、メモリの空間消費が少なくすみ、非常に効率的にデータの存在判定ができます。
デメリットとしては、false-positive(偽陽性)によるデータの誤判定の可能性があり、集合に存在しないデータを存在すると誤判定してしまう場合があります。このような誤判定が許されないような状況においては、ブルームフィルタは使えません。
逆に、false-negative(偽陰性)による誤判定はないため、データは実際にあるのに存在しないと判定することはありません。
ブルームフィルタのデータ構造について
ハッシュベースサーチは集合Ｃのすべての要素をリンクトリストもしくはオープンアドレスハッシュテーブルHに格納する どちらのケースにおいても、多くの要素がハッシュテーブルに格納され、要素の格納に係る時間は、要素数が増えるに従い増えていく。 実際、この振る舞いは他のサーチアルゴリズムにも共通したもので、要素の探索にかかる比較時間とのトレードオフとなる。
ブルームフィルターはビット配列Bを提供し、集合ＣからBに追加することと、特定の要素EがＢに存在するかどうかの判定は定数時間で行うことができ、驚くことに、これは既に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は集合Ｃに追加されているので、正しい振るまいです。データ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)
# もしチェックビットが０だったら求める値は存在しない
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の発生確率については、また別記事でまとめたいと思います。
