空間的/時間的な優位性

ウィキペディア小見出し辞書

空間的/時間的な優位性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/15 00:00 UTC 版)

「ブルームフィルタ」の記事における「空間的/時間的な優位性」の解説

偽陽性のリスクはあるが、ブルームフィルタは同様の集合的データ構造（平衡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 となるようにでき、ちょうど情報量を最大にして冗長性を最小にできる。