ブルームフィルタ

例えば、ブルームフィルタを使って空間効率の良いスペルチェックを行うことができる。正しい単語を集めた辞書に対するブルームフィルタは、辞書に登録されている全単語を受容し、登録されていない単語はほとんど受容しない。つまり若干不正確ではあるが、それで十分な場合もある。偽陽性の発生率を考慮すると、単語当たり 1バイト程度でデータ構造を構築できる。

このスペルチェッカーの面白い特性として、そのデータ構造からは正しい単語のリストを取り出すことができないことが挙げられる。どんなに努力しても、正しい単語のリストとさらにおびただしい偽陽性の単語のリストが得られるだけである（そのうちのどれが正しいものであるかはわからない）。これを望ましい機能であるととらえるならば、たとえばディスク内に残っている重要な番号（クレジットカード番号など）を探し出すとか、大量の電子メールから特定の（他人に知られたくない）アドレスを含むものを探し出すといった用途が考えられる。これは完全に安全な方法ではないが、偽陽性は別の手段で取り除くことができるだろう。

空のブルームフィルタは全てのビットが 0 に設定された m ビットのビット配列である。また、同時に k 個のハッシュ関数が定義されており、それぞれがキー値を m 個の配列位置のいずれかにマッピングする。

幅広い出力をする良いハッシュ関数では、その生成するハッシュ値の各ビットの値は相互の関連がほとんどないはずなので、ハッシュ値を適当なビット位置で分割して複数の異なるハッシュ関数として使うことができる。あるいは、ハッシュ関数の内部で使われる初期値をk 個の異なる値（例えば 0, 1, …… k-1）にしたり、それらの値をキー値に加算（あるいは連結）することで k 種類のハッシュ関数としたりできる。

要素を追加するには、それを k 個のハッシュ関数に入力して k 個の配列インデックスを得る。そして、それらの位置のビットを全て 1 にする。

ある要素がその集合に含まれるかどうかを調べる（クエリ）には、それを k 個のハッシュ関数に入力して k 個の配列への添字を得る。それらの位置にあるビット群のどれかひとつでも 0 である場合は、その要素はその集合には含まれていない。逆にそれらの位置にある全てのビットが 1 であれば、その要素はその集合に含まれているか、またはそれらのビットは他の要素を追加したときにたまたま全部 1 になった（偽陽性）ものであると考えられる。

この単純なブルームフィルタからは要素を削除することはできない。要素は k 個のビットにマッピングされており、そのうちの一箇所でもビットを 0 にすれば削除できる。しかし、異なる要素についても同じビットが 1 になることで表されている可能性があるので、ビットを 0 にすると他の要素までも削除してしまうことになる。そうしていまのデータ構造だけからではそのような衝突が発生しているのかどうかは判定できない。したがって無理やり削除すると、本来であれば発生しないはずの偽陰性が発生してしまう。

それでも、キー値すべてを列挙するようなデータ構造を用いたのでは巨大になりすぎる場合にはブルームフィルターは役に立つ。要素を追加していって偽陽性発生率が高くなりすぎた場合には、ブルームフィルタを再生成する必要が生じるが、これは比較的まれな事象である。

偽陽性のリスクはあるが、ブルームフィルタは同様の集合的データ構造（平衡2分探索木、trie、ハッシュテーブル、単純な配列、線形リスト）に比べると遥かに空間効率が良い。それらのほとんどはどれも少なくとも要素のデータ自体を保持する必要があり、要素データが小さな整数ならば少なくて済むが、文字列のように任意長のデータであればそれなりのメモリ領域を必要とする（trie は例外である。trie ではたとえば文字列の同じ位置が同じ文字であればそれを共有することができる）。リンクを持つデータ構造はポインタを格納するための追加のメモリ領域を必要とする。これに対して、誤り率 1% で k の値が最適化されているブルームフィルタであれば、1要素当たり 9.6 ビットの格納領域があればよい。これは要素のデータそのもののサイズとは無関係な値である。この利点は配列を利用している点と確率的特徴から生じている。1% の偽陽性率が高いという場合には、要素ごとに 4.8 ビットの領域を追加するごとに、誤り率をさらに 10分の1 にできる。

しかし、取りうる要素の種類が少なく、その多くが集合に含まれている場合には、ブルームフィルタよりも確定的なビット配列の方が効率が良い。確定的なビット配列では、取りうる要素あたり１ビットにより表すことができるのだから。また、衝突の発生率を無視するならハッシュテーブル（ただし、配列には値が入っているか否かの情報のみを格納する）も時間的・空間的に有利であり、これは実質的に、k = 1 のブルームフィルタと同じものとなる。

ブルームフィルタの珍しい特徴は、要素の追加も要素の有無の質問も O(k)の固定時間しかかからず、格納されている要素数には全く影響されないことである。固定サイズのデータ構造でこのような特徴を持つデータ構造はないが、衝突のない疎なハッシュテーブルはブルームフィルタよりも高速である場合がある。ブルームフィルタをハードウェアで実装すると、k 個のハッシュ関数を論理回路化して並行動作できるため、高速化が容易である。

空間効率を理解するために、k = 1 のブルームフィルタの場合を考えて見よう。k = 1 のときに偽陽性発生率を十分低くするには、ビットが 1 となる割合を十分少なくしなければならない。つまり、ビット配列はかなり大きくなり、その内容のほとんどは 0 になる。このときの配列のもつ情報量もサイズに比較して低くなる。通常の（k が 1 より大きい）ブルームフィルタでは、1 となるビット数が増えても同程度の偽陽性発生率を維持できる。従って k と m というパラメータの組み合わせを適切にすれば、ほぼ半分程度のビットが 1 となるようにでき、ちょうど情報量を最大にして冗長性を最小にできる。

Summarize Timeline Fact Check

ハッシュ関数は配列上の各位置を同じ確率で選択するものとする。要素をひとつ追加する際、あるビットが特定のハッシュ関数で 1 にセットされない確率は次のようになる。

${\displaystyle 1-{\frac {1}{m}}}$.

従って k 個のハッシュ関数のいずれによっても、1つのビットが 1 にセットされない確率は次のようになる。

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}}$.

n 個の要素を追加した状態で、あるビットがいまだに 0 である確率は次のようになる。

${\displaystyle \left(1-{\frac {1}{m}}\right)^{kn}}$;

したがって、逆に 1 となっている確率は次のとおり。

${\displaystyle 1-\left(1-{\frac {1}{m}}\right)^{kn}}$.

ある要素ではないと分かっているデータに対してそれが集合の要素であるかどうかをテストしたとする。このときハッシュ関数で得られる k 個のビットそれぞれが 1 となっている確率は上記の通りである。全てが 1 となっている確率、すなわちブルームフィルタがそのデータが集合の要素であると誤って判定してしまう確率は次のようになる。

${\displaystyle \left(1-\left(1-{\frac {1}{m}}\right)^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}}$.

明らかに、m（配列のビット数）が大きければ偽陽性の発生率は低くなり、n（追加する要素数）が多くなれば偽陽性の発生率は高くなる。いま m と n が決まっているとき、偽陽性発生率を最小にする k（ハッシュ関数の個数）は次のようになる。

${\displaystyle k={\frac {m}{n}}\ln 2\approx {\frac {9m}{13n}}\approx 0.7{\frac {m}{n}}}$,

このときの偽陽性の発生確率は次の通り。

${\displaystyle \left({\frac {1}{2}}\right)^{k}\approx {0.6185}^{m/n}}$.

• ハッシュテーブルとは大きく異なり、長さが一定のブルームフィルタにより任意の要素数を持つ集合が表現できる。つまり要素をいくらでも追加できる。要素の追加は単にデータ構造を徐々に 1 で埋めていくだけであるので失敗することは無い。ただし要素数が増えるにつれて偽陽性の発生率も増加する。

• 2つの集合から、同じハッシュ関数群を使って同じサイズのブルームフィルタをそれぞれ作ったとしよう。それら2つのブルームフィルタのビットごとの OR で得られる m ビットの配列は、2つの集合の和集合を表現するブルームフィルタと一致する。いっぽうでこれら2つのブルームフィルタのビットごとの AND により、2つの集合の積集合を表すブルームフィルタ（のようなもの）を作ることができるが、そのようにして得られるものは、最初から積集合に対して作成されたブルームフィルタに比べれば偽陽性の確率が大きくなる。