Bloom filterは、セットメンバーシップに答える空間効率的な確率的構造です。ただし、1つのひねりがあります。偽陽性を持つことができますが、決して偽陰性を持つことはありません。「確実に存在しない」は確実です。「おそらく存在する」は実際の確認が必要です。
動作原理
個のビットと個のハッシュ関数を持つビット配列。アイテムをするには、ハッシュされたビットを設定します。するには、そのビットを確認します — いずれかが0の場合、そのアイテムは確実に存在しません。
Bloom filterは、セットメンバーシップに答える空間効率的な確率的構造です。ただし、1つのひねりがあります。偽陽性を持つことができますが、決して偽陰性を持つことはありません。「確実に存在しない」は確実です。「おそらく存在する」は実際の確認が必要です。
個のビットと個のハッシュ関数を持つビット配列。アイテムをするには、ハッシュされたビットを設定します。するには、そのビットを確認します — いずれかが0の場合、そのアイテムは確実に存在しません。
mkkkbits: [0 0 0 0 0 0 0 0]
add "cat": hash->bits 1,4,6 -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
class BloomFilter:
def __init__(self, m, hashes):
self.bits = [0]*m
self.m, self.hashes = m, hashes # list of hash fns
def add(self, x):
for h in self.hashes:
self.bits[h(x) % self.m] = 1
def __contains__(self, x): # False = certain; True = maybe
return all(self.bits[h(x) % self.m] for h in self.hashes)
| 操作 | 時間 | スペース |
|---|---|---|
| add | O(k) | O(m)ビット |
| query | O(k) | — |
偽陰性はなく、偽陽性率はm（および調整されたk）が増加するにつれて低下します。
Bloom filterは高コストの作業を安価にスキップします。データベース（例：Cassandra、HBase）はそれを使用して、確実にディスク上にないキーのディスク読み取りを回避します。
これは古典的なシステムトレードオフを具現化しています — メモリとI/Oの大幅な削減と引き換えに、小さく制限されたエラー率を受け入れます。