GolangでBloomFilterを実装してみた

2018/02/17追記
Goらしくレシーバを使うようリファクタリングしました。 実装が少し変わっていますが、考え方自体は本記事から変わりありません。 リファクタリング後の実装は以下のGithubのとおりです。

github.com

前回調べたBloomFilterをGolangで実装してみました。

要素を蓄えるBloomFilterの用意

BloomFilterをサイズm[bit]のboolean配列として用意します。
実装中ではmをsizeという変数にしているので、適宜読み替えてください。 今回はBloomFilter型を用意します。

gistf2f5c87d2ca403d6f1b3deacb4d52ab4

使用するハッシュ関数

要素の追加および要素の有無を検証するときに、k個のハッシュ関数を用意する必要があります。 今回はハッシュ関数としてMD5を用いることにします。

gist4c6a2e7a9d80775c78c209540a9d90ed

最適なハッシュ関数の数

k個のハッシュ関数と述べましたが、kはどのように決定すればよいのでしょうか。 結論からいうと最適なハッシュ関数の数kは以下のように得ることができます。

k = \frac{m}{n} ln{2} \tag{1}

ここでnはBloomFilterに蓄える要素の数です。

導出

式(1)は偽陽性確率を最小化するようにkを決定することで得られます。
Wikipedia にも記載されていますが、まずm[bit]の配列において、あるbitを、あるハッシュ関数でマッピングした場合を考えます。そのbitが0(false)のままである確率は以下のようになります。

\displaystyle 1 - \frac{1}{m} \tag{2}

k個の独立なハッシュ関数を用いてマッピングしても、そのbitがまだ0(false)のままである確率は、式(2)をk回の独立な試行を繰り返すことになるので以下です。

\displaystyle \bigl(1 - \frac{1}{m} \bigr)^{k} \tag{3}

さらに、n個の要素を追加してなお、そのbitが0(false)のままである確率は

\displaystyle \bigl(1 - \frac{1}{m} \bigr)^{nk} \tag{4}

です。よってそのbitが1(true)になっている確率は1から式(4)を引けばよいので

\displaystyle 1 - \bigl(1 - \frac{1}{m} \bigr)^{nk} \tag{5}

として得られます。ここまでをBloomFilterに要素を蓄え終わった状態と考え、新たな要素が上記までで蓄えたBloomFilterに含まれているかを検証します。
このとき偽陽性確率は、新たな要素に対してk個のハッシュ値を計算し、そのマッピング先が既にすべて1(true)になっている場合です。つまり偽陽性確率は以下のように表されます。

\displaystyle \Bigl(1 - \bigl(1 - \frac{1}{m} \bigr)^{nk} \Bigr)^{k} \tag{6}

これを近似すると以下が得られます。

\displaystyle \bigl(1 - e^{- \frac{kn}{m}} \bigr)^{k} \tag{7}

上記に対して、m,nを固定してkの極値を求めることで最適なハッシュ関数の数 k = \frac{m}{n} ln{2}を求めることができます。 そもそもkはハッシュ関数の数なので整数ですし、離散最適化で考える必要があるような気もしましたが、Adamらの論文でも以下の記載があるので、実装上kを整数で丸めることにしました。

k must be an integer, and a smaller, suboptimal k might be preferred, since this reduces the number of hash functions that have to be computed.

gistcdae885488a6c951035e3aba4c3eed68

Double Hashing法

次に悩むポイントが、k種類のハッシュ関数をどのように用意すればいいのかです。Adamらの素敵な提案によると2つのハッシュ関数 h_{1}(x), h_{2} (x)を用いて新しいハッシュ関数 g_{i}(x), i = 1, 2, \cdots , kを以下のように得ることができます。

\displaystyle g_{i}(x) = h_{1}(x) + i h_{2}(x) \tag{8}

今回ハッシュ関数として用いたMD5の戻り値は128[bit]となるので、これを前半後半64[bit]ずつで分けて h_{1}(x), h_{2} (x)とします。
ただし、これをそのままint64の変数として扱おうとすると式(8)を計算する際にoverflowしてしまいます。 そこで多倍長計算を行うためにmath/bigパッケージを使用します。
C言語でいうところのGMPライブラリですね。

giste254088e7a699d3955f1ba1d101c13a6

要素の追加

BloomFilterに要素を追加する関数です。

gist6b13fac1db57d676e72bb39d258e6888

追加したい要素からハッシュ値を計算し、それを半分に分けて、Double Hashing法でk個のハッシュ値を求めます。
さらにそれをBloomFilterに蓄えるために、k個のハッシュ値を配列BloomFilterのindexとして、対応する箇所をtrueとしてマッピングします。

要素の検証

BloomFilterに要素が含まれているかを検証する関数です。

gistab1072fe99b8250e0783334a6ea99c7c

Addと同様に、ハッシュ値を前半後半の2つに分けて、Double Hashing法でk個のハッシュ値を求めます。 k個のハッシュ値を配列BloomFilterのindexとして、値がひとつでもfalseであれば、要素は含まれていないと判断します(全部trueのときは偽陽性の可能性あり)。

使い方

[1, 2, 3, 4, 5]をBloomFilterに追加して、要素が含まれているか、検証してみます。

gist24ff41df156b37c624f28d0cb15406b4

確かに偽陽性は起こりうる(上の例だと999のとき)ことがわかります。
一方で、偽陰性はなく、1, 2, 3, 4, 5はすべてtrueになっていることがわかります。

コードはGithubにあげてあります。
ハッシュ関数の計算は並列で行っても問題ないため、goroutineで並列化したものも別ブランチで実装してみました。
goroutineの起動コストもあるらしいので、どっちがいいかは、ちゃんとベンチマークとりたいですね。

最後に

最近データ構造アルゴリズムを実装して遊んでいるので、試すためによさげなデータ・セットが欲しいこの頃です。
(ベンチマーク取るにしても良いデータじゃないと意味なさそう...)

Wikipedia にも載っていますが、要素の削除を可能にしたCounting filterやBloomFilterのリストを作り、scalableにしたBloomier filterなどBloomFilterの亜種がたくさん存在しているようなので、そっちも実装していきたいです。

参考