確率的データ構造
わずかな誤りを許す代わりに、とても少ないメモリで答えるデータ構造。ブルームフィルタの偽陽性、HyperLogLog による異なる要素の数の見積もり、Count-Min Sketch による出現回数の見積もりを、理論値と比べながら確かめられます。
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
塗られたマスが 1 のビット。太枠は最後に入れた「いちご」が立てた位置、点線の枠は問い合わせた言葉の位置です。
りんごみかんぶどうももなしいちご
ビットの数 m
ハッシュ関数の数 k
位置 20●・39○・58○ → 確実に入っていない
- 入れた数 n
- 6
- 1 のビットの割合
- 25.0%
- 偽陽性率（理論値）
- 1.5%
- この m と n で最適な k
- 7
理論値 24.5%
(1 − e^(−kn/m))^k
(m/n)·ln 2
線は理論値、○は実際に 6 個入れて、入れていない 4,000 個を問い合わせた結果です。k が少ないと 1 つの位置だけで判定するので外れやすく、多すぎるとビットが埋まって外れやすくなります。
目安: 100 万個の URL を偽陽性率 1% で覚えるには 1.14 MB（1 個あたり約 9.6 ビット）、0.1% でも 1.71 MB で足ります。URL そのものを並べると数十 MB になります。
使い方
- ブルームフィルタ: 言葉を入れるとビットが立ちます。問い合わせ欄に入れていない言葉を書いて、偽陽性（入れていないのに「たぶん入っている」）が起きるかを試しましょう。ビットの数やハッシュ関数の数を変えると、グラフで理論値と実測の偽陽性率を比べられます。
- HyperLogLog: 訪問者を足していくと、レジスタの値と人数の見積もりが変わります。同じ人が再訪しても見積もりは変わりません。レジスタの数を増やすと誤差の帯が細くなります。
- Count-Min Sketch: 検索語の流れを数えたカウンタの表です。下の一覧の語を押すと、その語が足されたマスを示します。列や行の数を変えて、多めに数える量の変化を見てみましょう。
確率的データ構造とは
大量のデータを正確に扱うには、データそのものを覚えておく必要があり、データが増えるほどメモリも増えます。確率的データ構造は、ハッシュ関数で要素をばらまき、決まった大きさの配列だけを覚えることで、ごくわずかな誤りと引き換えにメモリを桁違いに減らします。誤りの大きさは理論的に見積もれるので、許せる誤りから必要なメモリを決められます。
- ブルームフィルタは「入っていない」なら必ず正しく、「入っている」は外れることがあります。データベースがディスクを読む前に、キーが無いことを確かめるのに使います（LSM ツリーの SSTable など）。
- HyperLogLog は、ハッシュ値の先頭に 0 が k 個続くのは 2^k 個に 1 個くらいなので、続いた 0 の最大の数から要素の種類の数を逆算します。Redis の PFCOUNT や、BigQuery の APPROX_COUNT_DISTINCT で使われています。
- Count-Min Sketch は、よく出る検索語やアクセスの多い IP アドレスのように、流れてくるデータの回数を少ないメモリで数えるのに使います。