ブルームフィルタとは - 少ないメモリで「たぶん在る・確実に無い」を判定する確率的データ構造

数百万件のブラックリストや、巨大なキャッシュに「このキーはもう見たか」を毎回問い合わせたい。しかし全要素をメモリに載せるにはデータが大きすぎる。ディスクやリモートに毎回問い合わせれば遅い。この「巨大な集合に対する所属判定を、全要素を持たずに高速・省メモリで行いたい」という悩みに、驚くほど小さなメモリで答えるのがブルームフィルタ（Bloom filter）です。前提として、キーから位置を求めるハッシュテーブルの仕組みを軽く押さえておくと理解が早くなります。ブルームフィルタは、そのハッシュの発想を「所属判定だけに割り切る」ことで極限まで省メモリ化した確率的データ構造です。

ブルームフィルタとは

ブルームフィルタは、ある要素が集合に含まれるかどうかを判定する確率的データ構造です。1970年に Burton H. Bloom が論文「Space/Time Trade-offs in Hash Coding with Allowable Errors」（Communications of the ACM, 13巻, 422-426ページ）で提案しました。半世紀以上前のアイデアですが、今もデータベースやネットワーク機器の内部で現役です。

最大の特徴は、判定に一方向の誤りだけを許すことです。

• 偽陽性（false positive）はあり得る: 本当は入っていないのに「たぶん入っている」と答えることがある
• 偽陰性（false negative）は無い: 入っているものを「入っていない」と答えることは絶対にない

つまりブルームフィルタが返すのは「たぶん含む（probably in）」か「確実に含まない（definitely not in）」の2つだけです。「確実に含まない」と言われたら100%信じてよく、「たぶん含む」と言われたら念のため本体を確認する、という使い方になります。この非対称性こそが、省メモリと高速性を成り立たせる肝です。

なお、基本のブルームフィルタは要素の削除ができません。追加した情報が他の要素と共有されているため、単純にビットを戻すと別の要素まで壊れてしまうからです。削除したい場合は後述の変種を使います。

仕組み: mビットとk個のハッシュ

ブルームフィルタの中身は、たった2つの部品でできています。

1. mビットのビット配列。最初はすべて0で初期化します。
2. k個の独立なハッシュ関数。それぞれが要素を受け取り、0 から m-1 の範囲の位置を返します。

追加（add）のときは、要素をk個のハッシュ関数にかけ、得られたk個の位置のビットをすべて1にします。すでに1なら何もしません。

問い合わせ（query）のときは、同じくk個の位置を計算し、そのビットを見ます。k個すべてが1なら「たぶん含む」、1つでも0があれば「確実に含まない」と答えます。

なぜ偽陰性が起きないかは、この手順から明らかです。ある要素を追加したら、その要素に対応するk個のビットは必ず1になっています。あとから他の要素を追加してもビットは1のまま（0に戻ることはない）なので、追加済みの要素を問い合わせれば必ずk個すべてが1になり、「含まない」と誤答することはありません。

逆に偽陽性が起きるのは、別々の要素たちが立てたビットが、たまたまある未知の要素のk個の位置を全部埋めてしまうときです。この要素自身は追加していないのに、k個の位置がすべて他の誰かによって1にされていると、「たぶん含む」と誤答します。

偽陽性率と最適なkの求め方

ブルームフィルタの美点は、偽陽性率を数式でコントロールできることです。導出の要点を追います。

ハッシュ関数が位置を一様ランダムに選ぶと仮定します。1回のビット設定で、特定のビットが1にされない確率は 1 - 1/m です。要素をn個追加すると、それぞれk箇所を設定するので合計 kn 回の設定が行われます。したがって、あるビットが0のままである確率は次のように近似できます。

(1 - 1/m)^{kn} ≈ e^{-kn/m}

逆に、そのビットが1である確率は 1 - e^{-kn/m} です。偽陽性はk個の位置がすべて1のときに起きるので、偽陽性率はおおよそ次の式になります。

p ≈ (1 - e^{-kn/m})^k

ここで面白いのは、kを増やすと2つの効果が競合する点です。kが大きいほど問い合わせで見るビットが増えて誤判定しにくくなりますが、同時に追加のたびに立てるビットも増え、配列が早く埋まってしまいます。この綱引きを最小化する最適なkは、微分して整理すると次のきれいな形になります。

k = (m/n) ln 2

このとき配列のちょうど半分のビットが1になっている状態が最適、という直感とも一致します。さらに、目標の偽陽性率 p を決めたときに必要なビット数mは近似で次のように求まります。

m = -(n ln p) / (ln 2)^2

1要素あたりに直すと、必要なビット数は約 -1.44 log2(p) ビットです。

数値で実感してみます。偽陽性率を1%（p = 0.01）に設定したい場合、1要素あたり必要なビット数は -1.44 × log2(0.01) ≈ 9.6 ビットです。つまり1要素あたり約9.6ビット（1.2バイトほど）で1%の精度が得られます。100万件なら約1.2MB。実データが1件あたり数十バイトあっても、フィルタはその数十分の一で済むわけです。このときの最適なkは k = (m/n) ln 2 ≈ 9.6 × 0.693 ≈ 6.6 なので、ハッシュ関数は7個前後が目安になります。

Pythonで実装してみる

考え方を確かめるため、ビット配列とk個のハッシュで add と contains を実装してみます。ここでは1つのハッシュ関数にシード（連番）を混ぜることで、k個の独立なハッシュを模しています。

import hashlib
import math
 
 
class BloomFilter:
    def __init__(self, n, p):
        # n: 想定する要素数, p: 目標の偽陽性率
        # 必要ビット数 m と最適なハッシュ個数 k を式から決める
        self.m = max(1, int(-(n * math.log(p)) / (math.log(2) ** 2)))
        self.k = max(1, round((self.m / n) * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)  # m ビットを確保
 
    def _positions(self, key):
        data = key.encode("utf-8")
        # シードを変えて k 個の独立なハッシュ位置を得る
        for i in range(self.k):
            h = hashlib.sha256(data + i.to_bytes(2, "big")).digest()
            yield int.from_bytes(h[:8], "big") % self.m
 
    def add(self, key):
        for pos in self._positions(key):
            self.bits[pos // 8] |= (1 << (pos % 8))  # 該当ビットを1に
 
    def contains(self, key):
        # 1つでも0なら「確実に含まない」、全て1なら「たぶん含む」
        return all(
            self.bits[pos // 8] & (1 << (pos % 8))
            for pos in self._positions(key)
        )
 
 
bf = BloomFilter(n=10000, p=0.01)
bf.add("apple")
bf.add("banana")
print(bf.contains("apple"))   # True（追加済みなので必ずTrue）
print(bf.contains("grape"))   # ほぼ False。まれに True（偽陽性）

contains が False を返したら、そのキーは絶対に追加されていません。True のときだけ本体（データベースなど）を確認すればよい、というのが基本の使い方です。

計算量とハッシュテーブルとの比較

追加も問い合わせも、やることは「k個のハッシュを計算してk個のビットを触る」だけです。要素数nには一切依存しないので、時間計算量は O(k)（kを定数とみなせば O(1)）です。計算量の記法はビッグオー記法を参照してください。

ハッシュテーブル（ハッシュセット）と比べると、性質の違いがはっきりします。

ブルームフィルタは、正確さと引き換えにメモリを桁違いに節約するデータ構造だと分かります。要素そのものを保持しないので、キーを列挙したり取り出したりはできません。「所属を確率的に判定するだけ」に用途を割り切っているからこそ、この省メモリが実現できています。

どこで使われているか

ブルームフィルタは、遅い操作を避けるための「事前フィルタ」として広く使われています。特に多いのが、ディスクI/Oやネットワーク往復を減らす用途です。

LSMツリー系ストレージ。Apache Cassandra や RocksDB / LevelDB、Google Bigtable などのストレージエンジンは、SSTable（ディスク上のソート済みファイル）ごとにブルームフィルタを持ちます。あるキーを読むとき、まずフィルタに問い合わせて「このファイルには確実に無い」と分かれば、そのファイルのディスク読み込みをまるごとスキップできます。RocksDB のドキュメントでも、フィルタは存在しないキーの探索でディスクI/O・CPU・ブロックキャッシュの消費を減らすためのものだと説明されています。この考え方はデータベースインデックスによる探索の高速化とも相補的です。

Webキャッシュ / CDN。「一度しかアクセスされないコンテンツをキャッシュしても無駄」という判断に使えます。ブルームフィルタで「過去に見たURLか」を軽く判定し、初回は素通し、2回目以降だけキャッシュに載せる、といった設計です。キャッシュ制御そのものはCache-Controlとs-maxageの話になりますが、何をキャッシュするかの前段フィルタとして相性が良いです。

その他。分散システムでのメンバーシップ判定、ネットワーク機器のルーティング、ビットコインの軽量クライアント（BIP37で関連トランザクションの絞り込みに使われたとされる）など、応用は多岐にわたります。ブラウザの不正URL判定でも、Google Chrome のセーフブラウジングがかつてブルームフィルタを使っていたと言われますが、現在の実装は変わっているとされ、公開情報の範囲では断定を避けるのが無難です。

変種: Counting / Scalable / Cuckoo

基本形の弱点（削除できない・容量を後から増やせない）を補う変種が提案されています。概要を押さえておきます。

Counting Bloom filterは、各セルを1ビットではなく小さなカウンタにした変種です。追加でカウンタを増やし、削除でカウンタを減らすことで、削除に対応します。代わりにメモリはカウンタのビット幅ぶん（例えば4倍）増えます。

Scalable Bloom filterは、要素数が事前に読めないときに動的に容量を拡張できる変種です。既存フィルタが埋まってきたら、より大きく偽陽性率を絞った新しいフィルタを継ぎ足していき、全体の偽陽性率を目標内に保ちます。

Cuckoo filterは近年よく比較される代替で、要素の指紋（fingerprint）を Cuckoo ハッシュ的に格納します。削除が可能で、低い偽陽性率の領域ではブルームフィルタより空間効率が良い場合があるとされます。

使いどころと注意点

導入時に踏みがちな点を整理します。

削除が必要なら基本形を避ける。基本のブルームフィルタは削除できません。要素が入れ替わるユースケースでは、Counting Bloom filter や Cuckoo filter、あるいは定期的にフィルタを作り直す運用を検討します。

容量は先に見積もる。偽陽性率は「実際に入れた要素数n」に対して決まります。想定より多く詰め込むとビット配列が埋まり、偽陽性率が急激に悪化します。m = -(n ln p) / (ln 2)^2 から必要ビット数を先に計算し、想定の上限nで設計してください。要素数が読めないなら Scalable Bloom filter が選択肢です。

偽陽性のコストを設計に織り込む。ブルームフィルタは万能の正解ではなく、「確実に無い」を高速に判定して本体アクセスを減らす前段です。偽陽性が出ても、そのあと本体を確認すれば正しい答えは得られます。逆に言えば、偽陽性が出たときのフォールバック（本体確認）が用意できる場面でこそ真価を発揮します。フォールバックが無い場面には向きません。

まとめ

ブルームフィルタは、mビットの配列とk個のハッシュだけで、巨大な集合への所属判定を省メモリ・高速に行う確率的データ構造です。要点を振り返ります。

• 答えは「たぶん含む」か「確実に含まない」の2つ。偽陽性はあるが偽陰性は無い
• 追加はk個のビットを1にし、問い合わせはk個のビットを見るだけ。計算量は要素数に依存せず O(k)
• 偽陽性率は p ≈ (1 - e^{-kn/m})^k、最適なkは k = (m/n) ln 2、必要ビット数は m = -(n ln p) / (ln 2)^2
• 1%の偽陽性率なら1要素あたり約9.6ビットで済む
• Cassandra・RocksDB などのストレージエンジンがディスクI/O回避に使うなど、実運用で広く使われている
• 削除や動的拡張が必要なら Counting / Scalable / Cuckoo などの変種を選ぶ

「巨大な集合に何度も所属を問い合わせたいが、全部はメモリに載せられない」という悩みに出会ったら、それはブルームフィルタの出番です。1970年のシンプルなアイデアが、今もストレージの奥で静かにディスクを守り続けています。

参考リンク

• Bloom, B. H. (1970) "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM, 13(7), 422-426（ACM Digital Library）
• Bloom filter - Wikipedia
• RocksDB Bloom Filter（公式Wiki）
• Apache Cassandra Documentation: Bloom filters