ブルームフィルタ：「確実にない」と「たぶんある」

単語を登録すると、m個並んだビットのうちk個が1になります。検索で調べるのも、同じk個のビットです。0が一つでもあれば、その単語は確実に未登録。すべて1でも、登録されているとは限りません。単語を順に登録してから、自分でも単語を入力してみましょう。

計算例 — ブルームフィルタ：「確実にない」と「たぶんある」

値が1のビット数	64中20（31.3%）
単語あたりのビット数	8.00
標準的な推定式による最適なk	5.55
偽陽性率の標準的な推定値	3.06%
実際に1になったビット数からの推定値	3.05%
未登録の10,000個の文字列での実測値	10,000中335（3.35%）
登録済みなのに「確実にない」と判定された単語数	8中0

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

ブルームフィルタは、m個のビットとk個のハッシュ関数を使い、要素が集合に含まれるかどうかを判定します。要素を登録すると、ハッシュ値が指すkか所のビットを1にします。検索で調べるのも同じkか所です。0が一つでもあれば、その要素は集合に確実に含まれません。すべて1なら、たぶん含まれます。この「たぶんある」という判定が誤っている場合を偽陽性と呼びます。n個の要素を登録したとき、偽陽性率の標準的な推定値は(1 − e^−kn/m)^kです。これはブルームが1970年に示した式を指数関数で近似したもので、k = (m/n) ln 2のとき最小になります。

各記号の意味

m: フィルタのビット数
k: ハッシュ関数の個数。各単語の登録で1にするビット数、検索で調べるビット数でもある
n: 登録する単語数
X: n語すべてを登録した時点で、値が1になっているビット数

前提: 各単語に対応するkか所は、二重ハッシュ法で、二つのハッシュ値から求めます。位置iは(h₁ + i·h₂) mod mです。h₁には単語のFNV-1aハッシュ値を、h₂にはdjb2ハッシュ値をさらに混ぜ合わせて奇数にした値を使います。mは2の累乗なので、同じ単語に対応するkか所は必ず互いに異なります。標準的な推定式は、knか所の位置がそれぞれ独立に無作為に選ばれると仮定します。二重ハッシュ法を使うことやmが小さいことが、実際のフィルタとの差につながります。偽陽性率は、文字列0から9999の10,000個について測定しています。この文字列群に対しては正確な値ですが、あらゆる単語に対する値ではありません。

ハッシュ関数は16個より1個のほうがよい 🖖

ハッシュ関数5個を押し、結果の下にある表を見てください。128ビットに16語を登録したとき、ハッシュ関数が1個なら、未登録の文字列の12.82%が「たぶんある」と判定されます。5個では2.50%で、この列の最小値。16個では32.01%と、1個のときより悪くなります。関数を一つ増やすと、検索時に調べるビットが一つ増えるので、誤判定を抑えられます。一方、登録のたびに1にするビットも一つ増え、誤判定を招きやすくなります。1個から5個までは偽陽性率が下がり続け、その先は15個のところで少し下がるほかは上昇します。ブルームは1970年に、この転換点が、ビットの約半分が1になるところにあると見いだしました。ハッシュ関数が5個のとき、ここでは128ビット中60ビットが1です。標準的な推定式で求めた最適なkは、(m/n) ln 2 = 8 × 0.693 = 5.55となります。

1の個数から、標準的な推定式より正確に予測できる 🖖

ハッシュ関数16個を押してください。標準的な推定値は9.76%ですが、実際には32.01%が「たぶんある」と判定されます。推定式では、1になるビット数を128 × (1 − e⁻²) = 110.7と見積もります。ところが、この16語では119ビットが1になりました。実際に1になった割合を16乗すると、(119/128)¹⁶で31.15%。実測値に近づきます。kがこれほど大きいと、1のビットが少し増えるだけで結果が大きく変わります。検索で調べる16ビットすべてが1である必要があるからです。このページで偽陽性が生じる設定は全部で6,051通り。そのうち5,356通りでは、実測値に対する比で比べると、実際に1になったビット数から求めた推定値のほうが近くなります。実際のフィルタでも、自分のビットの1を数えれば、標準的な推定式よりよく偽陽性率を見積もれます。また、この16種類の動物は、たまたま結果の悪い組合せでもあります。別の16語の組を150組使うと、同じ大きさのフィルタでの平均は14.4%。それでも標準的な推定値を上回ります。

ある単語を削除すると、別の単語まで消えてしまう 🖖

owlを削除を押し、最後まで進めてください。owlは位置37、58、15のビットを1にしました。次に登録されたfoxに対応する位置は14、15、16で、位置15はすでに1でした。owlのビットを0に戻すと、foxが使う位置15も0になります。そのため、登録されているfoxを検索しても「確実にない」と返ってきます。これが偽陰性です。ブルームフィルタが起こさないと保証している、まさにその誤りです。ビットに残るのは、何かの単語がそこを1にしたという情報だけ。どの単語だったかはわからず、安全に0へ戻すことはできません。この64ビットのフィルタでは、8語のうち6語は、削除すると別の単語も検索できなくなります。よく使われる対策は、各位置のビットを小さなカウンタに置き換え、登録で1を足し、削除で1を引く方法です。その分、メモリが必要になります。

ブルームの1970年の分綴用フィルタは、どこまで小さくできるか 4 ステップ
ブルームが1970年に挙げた例は、500,000語の分綴位置を決めるプログラムでした。分綴とは、行末などで単語を分ける際の、ハイフンを入れられる位置を決めることです。450,000語は簡単な規則で処理できますが、残る50,000語はディスク上の辞書で調べる必要があります。ブルームは、この50,000語のフィルタを主記憶に置き、規則で処理できる単語の16語に1語で無駄なディスク参照が起こることを許容しようと提案しました。必要なビット数とハッシュ関数の個数はいくつでしょう。ディスク参照は何回に減るでしょうか。このページでも単語あたりのビット数をそろえて、測ってみましょう。

この問題をツールで開く
1. kを最適に選ぶと、標準的な推定式で必要になるのは単語あたりlog₂(1/p) / ln 2ビットです。p = 1/16なら、4 / 0.6931 = 5.77ビット。したがって、フィルタ全体では50,000 × 5.77 = 288,539ビットとなります。ブルーム自身は「300,000ビット未満」と記しています。最適なkは5.77 × ln 2 = 4です。ハッシュ関数が4個のとき、ビットの半分が1になると見込まれます。
  
  $\frac{lo g _{2} 16}{ln 2} = \frac{4}{0.6931} = 5.77 bits per word, 50000 \times 5.77 = 288539 bits, k = 5.77 \times ln 2 = 4$
2. 辞書を必要とする50,000語は、すべてディスクを参照します。加えて、規則で処理できる単語の16語に1語でも参照が起こるので、450,000 / 16 = 28,125回が加わります。合計は500,000語中78,125回、15.6%です。ブルームはこれを78,000回と丸め、すべての単語でディスクを参照する場合に比べて84%削減できるとしました。
  
  $50000 + \frac{450 000}{16} = 78125 disk reads of 500000 (15.6%)$
3. この計算に、単語の長さは出てきません。「cat」でも「incomprehensibilities」でも、フィルタに必要なのは単語あたり5.77ビットです。一方、通常のハッシュ表で各単語を表すには、平均で少なくとも19ビット必要だとブルームは見積もりました。pを半分にするたびに、単語あたり1 / ln 2 = 1.44ビットが加わります。偽陽性を64語に1語に抑えるなら、6 / 0.6931 = 8.66ビットです。
  
  $\frac{1}{l n 2} = 1.44 bits per halving of p, \frac{6}{0.6931} = 8.66 for p = \frac{1}{64}$
4. このページで扱えるのは最大64語ですが、推定値を決めるのはm/nとkだけです。m = 256、n = 44（単語あたり5.82ビット）、k = 4に設定してください。256ビット中122ビット、47.7%が1になります。未登録の10,000個の文字列のうち、「たぶんある」と判定されるのは535個で、偽陽性率は5.35%。設計の目標だった1/16 = 6.25%を下回ります。このフィルタの標準的な推定値は6.11%です。
  
  $\frac{256}{44} = 5.82 : \frac{535}{10 000} = 5.35% < \frac{1}{16} = 6.25%$
解答

288,539ビットと4個のハッシュ関数が必要で、ディスク参照は500,000回から78,125回に減ります。 このページで256ビットに44語を登録すると、実測値は5.35%で、目標を満たします。ただし、これは44語を登録した一つのフィルタでの結果です。288,539ビットに50,000語を登録しても、同じように1/16に近い値になるかどうかは、最大64語のこのページでは確かめられません。

$288539 bits, k = 4, 78125 disk reads$

学習の道すじ

参考文献 (1)

The method itself, the turning point at half the bits set in the first insight, and the hyphenation example the worked problem recomputes: Burton H. Bloom, "Space/time trade-offs in hash coding with allowable errors," Communications of the ACM 13(7), July 1970, pp. 422–426.

42Math チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。

ブルームフィルタ：「確実にない」と「たぶんある」

理論 — ブルームフィルタ：「確実にない」と「たぶんある」

各記号の意味

ハッシュ関数は16個より1個のほうがよい 🖖

1の個数から、標準的な推定式より正確に予測できる 🖖

ある単語を削除すると、別の単語まで消えてしまう 🖖

全プロセスの詳細解説

データ構造が得意なこと