Day 147-Q4 | Bloom Filter（ブルームフィルタ）

問題

ビット配列の大きさ $M$ と $K$ 個のハッシュ関数のパラメータ $(a_i,b_i)$ が与えられる。ハッシュ関数は $h_i(x)=(a_i\cdot x+b_i)\bmod M$。はじめ全ビット$0$の配列に、$N$個の整数を順に挿入する（各$i$について$h_i(x)$番目を$1$にセット）。

すべての挿入後、$Q$個の整数についてクエリする。$h_1(y),\dots,h_K(y)$の$K$箇所すべてが$1$ならMAYBE、1箇所でも$0$ならNOを出力する。さらに「実際には挿入されていないのにMAYBEと判定された」偽陽性の個数を求めよ。

入力形式

M K
a_1 b_1
:
a_K b_K
N
x_1 ... x_N
Q
y_1 ... y_Q

制約

$1 \le M \le 64$

$1 \le K \le 5$

$1 \le a_i,b_i \le 20$

$1 \le N,Q \le 20$

入出力例

入力例1

出力例1

MAYBE
NO
MAYBE
0

概念図：16ビット配列とK=3ハッシュ

ヒント（段階的開示）

ヒント1（方向性）

Bloom Filterは実際の要素を保持しないため、要素数がどれだけ多くても使用メモリは$M$ビットで一定。代償として複数要素のハッシュ値が偶然重なることで偽陽性が起こりうる。まずは挿入・クエリの手続きをそのまま実装する。

ヒント2（アプローチ）

ビット配列を`bool`のリストで持てば挿入・クエリは素直な二重ループで済む。偽陽性の判定には、実際に挿入した集合を別途`set`として保持し、クエリ結果が`MAYBE`かつ真の集合に含まれない場合にカウントする。

ヒント3（誘導）

def build_filter(M, hash_params, xs):
    bits = [False] * M
    for x in xs:
        for a, b in hash_params:
            bits[(a * x + b) % M] = True
    return bits

def query(bits, hash_params, M, y):
    return all(bits[(a * y + b) % M] for a, b in hash_params)

`query`が`True`でも本当に挿入されたとは限らない（偽陽性の可能性）。`False`なら絶対に挿入されていない（偽陰性なしの性質）。

模範解答 (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1

    hash_params = []
    for _ in range(K):
        a = int(data[idx]); idx += 1
        b = int(data[idx]); idx += 1
        hash_params.append((a, b))

    N = int(data[idx]); idx += 1
    xs = [int(data[idx + i]) for i in range(N)]
    idx += N

    Q = int(data[idx]); idx += 1
    ys = [int(data[idx + i]) for i in range(Q)]
    idx += Q

    bits = [False] * M
    for x in xs:
        for a, b in hash_params:
            bits[(a * x + b) % M] = True

    true_set = set(xs)
    false_positive = 0
    out = []
    for y in ys:
        maybe = all(bits[(a * y + b) % M] for a, b in hash_params)
        if maybe:
            out.append('MAYBE')
            if y not in true_set:
                false_positive += 1
        else:
            out.append('NO')
    out.append(str(false_positive))
    print('\n'.join(out))


main()

Step-by-Step 解説

1ビット配列の構築
$M=16$の全Falseに$x=5,12,9,20$を挿入。$x=5$なら$h_1(5)=0,h_2(5)=11,h_3(5)=7$の3ビットが立つ。最終的に立つビットは$\{0,3,5,6,7,8,11,12,13,14,15\}$。

2クエリ判定
$y=5$（挿入済み）は全て立っているビットなので`MAYBE`。$y=8$（未挿入）は$h_1(8)=9$が立っていないため即座に`NO`。

3偽陽性のカウント
`MAYBE`判定のうち実際の挿入集合に含まれないものが偽陽性。本問例では$y=5,20$はどちらも挿入済みなので偽陽性0件。

4理論偽陽性率
$p\approx(1-e^{-KN/M})^K$。最適な$K$は$K=\frac{M}{N}\ln2$付近で最小化される。

よくあるミス

ミス	原因	正しい書き方
Pythonの組み込み`hash()`を使う	実行のたびに異なる値を返し再現性がない	問題文の決定的な線形合同式$(a_ix+b_i)\bmod M$を使う
`MAYBE`を「挿入されている」と断定する	偽陽性を理解していない	`MAYBE`はあくまで可能性があるという意味と捉える
`NO`のケースを偽陽性にカウントする	偽陽性は`MAYBE`なのに実在しない場合のみの非対称な概念	カウント対象を`MAYBE`のケースに限定する
K個全てをチェックせず一部だけで判定する	早期に1つ見つけて残りの確認を忘れる	`all(...)`でK箇所全てが1であることを確認する
挿入と別に真の集合を保持し忘れる	Bloom Filter自体は実データを持たないことを忘れる	`true_set=set(xs)`を判定用に別途保持する

次のステップ

発展: $N=20,M=16,K=3$のようにフィルタを詰め込みすぎるパラメータで実験し、偽陽性が実際に発生する例を作れ。理論式との比較をせよ。
次回予告: Max-Cutの脱乱択化（Method of Conditional Expectations）

自己評価

完全理解おおむね理解要復習

Day 147-Q4 — Bloom Filter（ブルームフィルタ・確率的メンバーシップ判定）

問題