m と k はどう選べばよいですか?

要素数 n と目標の偽陽性率 p が与えられたら、m = -n*ln(p)/(ln(2))^2 ビット、k = (m/n)*ln(2) 個のハッシュ関数です。n=100 万、p=1% なら、m ≈ 960 万ビット(1.2MB)、k ≈ 7 です。フィルターは要素のサイズに関係なく 1.2MB を使います。100 万の文字列を保存するよりはるかに少ないです。

ブルームフィルターから要素を削除できますか?

標準のブルームフィルターからは削除できません。ビットを 0 にすると他の要素に影響する可能性があります。削除をサポートするにはカウンタリングブルームフィルター(ビットの代わりにカウンター)、または Cuckoo フィルター(削除対応、より良い空間効率)を使ってください。ほとんどのユースケース(キャッシュ、重複除去)では、削除非対応が許容されます。

集合の所属判定にブルームフィルタを使う

ブルームフィルタは確率的に集合への所属を判定します。偽陰性はありませんが、偽陽性があり得ます。大きな集合に対して省スペースです。

1

ブルームフィルターは、m ビットのビット配列と k 個のハッシュ関数で構成されます。要素の追加:h1(x)、h2(x)、…、hk(x) の位置のビットを 1 にします。所属判定:k 個の位置すべてが 1 かを確認します。1 つでも 0 なら、その要素は確実に集合にありません。すべて 1 なら、おそらく集合にあります(偽陽性率 p ≈ (1 - e^(-kn/m))^k)。
2

ハッシュ計算ツール →
複数のハッシュ関数(または異なるシードの 1 つのハッシュ)で k 個の位置を計算します。k=7、m=10000 ビット、n=1000 要素の場合、偽陽性率は約 0.8% です。偽陽性を減らすには、m または k を増やしてください。各ハッシュ関数には、異なるソルト付きの SHA-256 を使ってください。
3

Murmur3 ハッシュ →
ブルームフィルターのハッシュには、MurmurHash3(非暗号、高速)を使ってください。ブルームフィルターに暗号学的ハッシュ関数は不要です。必要なのは速度と一様分布です。MurmurHash3、FNV-1a、xxHash が良い選択です。k 個の独立したハッシュ関数(または二重ハッシュ:i = 0..k-1 に対する h1(x) + i*h2(x))を使ってください。

よくある質問

m と k はどう選べばよいですか?: 要素数 n と目標の偽陽性率 p が与えられたら、m = -n*ln(p)/(ln(2))^2 ビット、k = (m/n)*ln(2) 個のハッシュ関数です。n=100 万、p=1% なら、m ≈ 960 万ビット(1.2MB)、k ≈ 7 です。フィルターは要素のサイズに関係なく 1.2MB を使います。100 万の文字列を保存するよりはるかに少ないです。
ブルームフィルターから要素を削除できますか?: 標準のブルームフィルターからは削除できません。ビットを 0 にすると他の要素に影響する可能性があります。削除をサポートするにはカウンタリングブルームフィルター(ビットの代わりにカウンター)、または Cuckoo フィルター(削除対応、より良い空間効率)を使ってください。ほとんどのユースケース(キャッシュ、重複除去)では、削除非対応が許容されます。