存在しない問い合わせを母数にする
Bloom filterは、要素が存在しないことを小さなビット領域で判定する近似的な集合表現です。全ての必要なビットが立っていれば「存在するかもしれない」と答え、どれかが0なら存在しないと答えます。今回の実験では1,000件を挿入し、それらとは重ならない5,000件を問い合わせます。存在しないのに陽性となった件数を、この5,000で割って偽陽性率を求めます。
挿入済みの問い合わせを分母へ混ぜると、実験で見たい条件付きの率が変わります。また、偽陽性はエラーの発生率というだけでなく、後段の正確な検索へ余分に進む費用にも関係します。フィルタだけで削除や認可を決める用途とは分けてください。ここでは固定した入力集合、ビット数m、ハッシュ数kを変え、理論的な近似値と有限標本の観測を比較します。
ビット数とハッシュ数の予測を立てる
独立で一様なハッシュを近似的に仮定すると、n件挿入後の偽陽性率は(1−exp(−kn/m))^kと見積もれます。n=1,000、m=8,000、k=3なら約3.06%です。m=4,000へ減らすと約14.69%、m=8,000のままk=6なら約2.16%となります。これは一回の実験が必ずその率へ一致するという意味ではありません。ハッシュの依存や有限のビット数、標本数によって差が出ます。
kを増やせば常に良くなるわけでもありません。多くの位置を立てるほどビットが飽和し、問い合わせのハッシュ計算費用も増えます。近似的な最適kはm/n×ln2の付近ですが、整数へ丸めることと実装の費用を合わせて判断します。ここでは3条件に絞り、性能の最適化を証明する実験とはしません。予測した式、選んだパラメータ、観測する量を先に固定します。
| n | m | k | 近似偽陽性率 |
|---|---|---|---|
| 1000 | 4000 | 3 | 約14.69% |
| 1000 | 8000 | 3 | 約3.06% |
| 1000 | 8000 | 6 | 約2.16% |
再現できるハッシュと集合を用意する
コードではSHA-256へハッシュ番号の4バイト表現とキーのUTF-8を渡し、得た整数をmで割った余りを位置にします。Pythonの実行ごとに変わり得る組込みhashへ依存しません。異なる番号を付ける方法は再現するための簡単な構成で、完全に独立した数学的なハッシュ族を証明しているわけではありません。SHA-256を使ったから偽陽性がなくなるわけでもありません。
乱数seedを0〜4へ変え、それぞれ重複しない6,000個の整数を選びます。先頭1,000を挿入、残り5,000を問い合わせとし、集合の積が空であることをassertします。問い合わせ用のキーが偶然挿入済みだった場合を、偽陽性へ数えないためです。同じseedの集合を三つのパラメータで使うので、条件間で入力の違いを混ぜずに比較できます。実行にはPythonの標準ライブラリだけを使います。
挿入済みを失っていないことも検査する
各条件でフィルタへ挿入した後、挿入済み全件が陽性になることをassertします。ビットを立てるだけで削除しない今回の方式では、挿入したキーへ陰性を返すなら実装や入力の扱いに問題があります。この検査と、未挿入キーの偽陽性率の観測は別です。陽性の中身を全部正解と数えたり、偽陰性のないことから偽陽性もないと結論したりしないでください。
出力はm、k、seedごとの五つの観測値、近似式の値です。丸めた平均だけへまとめず、ばらつきも残します。統計的な検定を追加する場合は、試行の独立性と検定の目的を別に定めます。今回のassertは確率の近似値への厳密一致を要求せず、集合の分離と挿入済みの保持という決定的な条件を検査します。確率が関わる箇所へ、根拠のない固定の成功基準を置かないためです。
import hashlib,math,random
class Bloom:
def __init__(self,m,k):self.m=m;self.k=k;self.data=bytearray((m+7)//8)
def locations(self,key):
for i in range(self.k):yield int.from_bytes(hashlib.sha256(i.to_bytes(4,'big')+key.encode()).digest(),'big')%self.m
def add(self,key):
for bit in self.locations(key):self.data[bit//8]|=1<<(bit%8)
def contains(self,key):return all(self.data[b//8]>>(b%8)&1 for b in self.locations(key))
for m,k in [(4000,3),(8000,3),(8000,6)]:
observations=[]
for seed in range(5):
rng=random.Random(seed);values=rng.sample(range(1000000),6000);inserted=['x'+str(x) for x in values[:1000]];queries=['x'+str(x) for x in values[1000:]]
assert not set(inserted)&set(queries)
f=Bloom(m,k)
for key in inserted:f.add(key)
assert all(f.contains(key) for key in inserted)
positives=sum(f.contains(key) for key in queries);observations.append(positives/len(queries))
approximation=(1-math.exp(-k*1000/m))**k
print('n=1000 queries=5000 seeds=0..4 m=',m,'k=',k,'observed=',observations,'approximation=',approximation)
print('no false negatives for inserted keys; approximation is not an exact finite-sample guarantee')
削除を足すと前提が変わる
あるキーが使うビットを削除時に0へ戻す案を考えます。他のキーが同じ位置を使っていれば、そのキーの必要なビットまで消え、挿入済みなのに陰性になる可能性があります。通常のビット型Bloom filterへそのまま削除を足してはいけない理由です。カウンタを使う方式や、別の構造には別の更新規則が必要になります。今回の実験は挿入後にビットを消さない条件でのみ解釈します。
フィルタを保存して別プロセスで読む場合は、m、k、ハッシュの入力形式と文字の符号化も保存します。ビット列だけ同じでも、キーから位置へ変換する規則が変われば、挿入済みの検査が失敗します。古い形式を新しいハッシュ数で読むような変更を、互換性があるものとして扱わないでください。集合の意味は、ビット列と位置計算の契約を合わせて成立します。
結果を後段の費用へつなげる
偽陽性率が約3%なら、未挿入の5,000問い合わせのうち、およそ150件が正確な検索へ進むという予測になります。しかし全問い合わせのうち未挿入が何割かによって、実サービスで追加される検索の数は変わります。フィルタを引くCPU時間と、後段のI/Oやネットワークの費用も比べます。偽陽性率が低い方が常に全体も速いとは限りません。
ビット領域を増やすとメモリや転送量が増え、ハッシュ数を増やすと一回の判断の仕事が増えます。評価するなら、存在する問い合わせと存在しない問い合わせの混合率を固定し、後段を含めた正しい最終結果も検査します。今回の出力は率の確認であり、その総合的な時間測定を済ませたものではありません。実験の結果を設計へ使うときも、どの費用まで含めて選んだかを説明してください。
照会の一致を、同じseedで比較する
三条件の偽陽性率を比べる際、同じseedの行では同じ挿入集合と問い合わせ集合を使います。違う問い合わせだけを一方へ与えれば、パラメータの差と入力の差が混ざります。ただし同じデータを使った三条件の観測が、統計的に互いに独立な試行になるという意味ではありません。
削除や並行更新を足した場合は、挿入済みの不在がないという前提も再確認します。ビットの更新が失われる実装なら、数学的なBloom filterの性質とは別のバグで偽陰性が出る可能性があります。今回の単一スレッド・挿入のみという条件を保つことで、近似式と偽陽性の問いへ焦点を絞っています。
分母と誤差を変える課題
課題は未挿入の5,000件で陽性が160件、挿入済み1,000件が全て陽性だった場合の偽陽性率です。解答は160/5,000=3.2%です。陽性の総数1,160で割った率や、全6,000件で割った率は、ここで定義した偽陽性率ではありません。挿入済みが全部陽性だったことは偽陰性の検査で、分母へ加える理由にはなりません。
追加課題では挿入件数を2,000へ増やし、mとkを固定します。近似式ではビットの占有が増えて偽陽性率が上がると予想します。入力を再生成し、挿入と問い合わせが重ならない条件も作り直してください。期待した方向と違う一つの標本を見たときも、直ちに式を否定せず、全seedの結果と標本数、ハッシュの条件を確認します。終了時に外部の資源を消す操作はなく、再現用のコードと結果を残します。