アルゴリズムクイックリファレンス 第2版

132

■

5

章 探索

値が

100,000

から

2,000,000

（

10,000

ステップ）の

m

について試行した。

k

＝

3

ハッシュ関数を用いた。結果を図5-6に示す。

M

を変えたときの偽陽性率

ブルームフィルタの

m

ビットのサイズ

語FP

ランダムFP

計算したFP

図5-6　ブルームフィルタによる偽陽性率の例

前もって偽陽性率をある小さな値より小さくしたいとわかっているなら、挿入す

る要素数

n

を推定した後で、

k

と

m

とを設定する必要がある。文献では、

(1

−

(1

−

1/m)

kn

)

を

1/2

に近い値にすることを勧めている。例えば、単語表に対して偽陽性

率を

10

％より小さいと保証するには、

m

を少なくとも

1,120,000

、すなわち全体で

131,250

バイトに設定する必要がある。

5.5

 二分探索木

既に述べたように、メモリ上の配列の

二分探索

は効率的だ。しかし、探索の元の

集まりが頻繁に変化するようだと、整列済み配列では探索の効率性が大幅に低下す

る。動的な集まりに対して、妥当な探索性能を維持するためには、異なるデータ構

造を採用する必要がある。

ハッシュに基づいた探索

は動的な集まりを扱えるが、リ

ソース使用の効率性の観点からハッシュ表のサイズを小さくしすぎてしまう。要素

の個数については前もって何もわからないので、ハッシュ表の適切なサイズが選べ

ないのだ。またハッシュ表では要素を整列順に取り出すことができない。

別の戦略として、探索木を使って動的集合を格納できる。探索木は、メモリ上で