Blog
吉田です。相変わらず乱択アルゴリズム紹介ということで、今日はBloom Filterの話をしたいと思います。今までと違うのはBloom Filterはある問題を解くアルゴリズムではなくデータ構造であるということです。データ構造に乱数を導入するとどういうことが出来るようになるか見てみましょう。
今、\(n\)個の単語\(x_1,\ldots,x_n\)が有り、これに対して
\(\mathrm{lookup}(y)\): 単語\(x_1,\ldots,x_n\)の中に\(y\)が有るか
というクエリをサポートしたいものとします。このようなクエリをサポートするデータ構造をここでは”辞書”と呼ぶことにします。目標は辞書が使うビット数\(m\)を出来るだけ抑えるというものです。
lookupにもし間違いを許さないとすると、単語\(x_1,\ldots,x_n\)を全て保存しなければなりません。これは非常に容量を食うので、まずは単語を保存しなくても良い方法を考えるところから始めます。単語を保存していないと、どうしてもlookupで間違える可能性が出るのですが、その確率を出来るだけ小さくしていくことを考えます。
一番簡単にこれを実現するデータ構造はハッシュだと思います。ハッシュではハッシュ関数\(h: \{\mathrm{strings}\} \to \{1,\ldots,m\}\)を用います。
ハッシュ関数はランダムに振舞うことが期待されています。つまりどんな単語\(x\)に対しても\(h(x)\)は\(\{1,\ldots,m\}\)からランダムに選ばれ、以降\(h(x)\)はその値を返す、というものです。実際にはそのような都合のよい関数を作ることは不可能なので、どのようにしてランダムなハッシュ関数と同等の振る舞いをするハッシュ関数を作るか、というのが一つの大きな研究テーマとなっているのですが、ここではランダムなハッシュ関数が有ると仮定します。またハッシュ関数の計算は定数時間で行えると仮定しましょう。以降、高い確率や平均といった時は全てハッシュ関数の振る舞いに対してです。
間違いを許すが単語そのものは保存しないハッシュは次のようにして実現出来ます。
構築:
\(m\)ビット配列\(A\)を用意する。
ランダムなハッシュ関数\(h\)を用意する。
\(\mathrm{for} i = 1,\ldots,n\)
\(A[h(x_i)] \leftarrow 1\)
\(\mathrm{lookup}(y)\):
\(A[h(y)]=1\)ならYes, そうでなければNoと出力。
さて、上のハッシュはfalse negativeを持ちません。つまり\(y\)が辞書に存在すれば\(\mathrm{lookup}(y)\)は必ずYesと出力します。また、\(\mathrm{lookup}(y)\)の計算時間は\(O(1)\)です。なので問題はfalse positiveが起こる、つまり\(y\)が辞書に存在しないのに\(\mathrm{lookup}(y)\)がYesと出力する確率です。
\(h\)がランダムに振舞うと仮定しているので、これは\(n\)個のボールを\(m\)個のビンに投げる操作と見ることが出来ます。この操作はよく知られていて、各ビンに入るボールの個数はポワソン分布で近似出来ます。ポワソン分布によると、各ビンに入るボールの個数の平均\(\lambda = n/m\)を用いて、\(\Pr[A[i] = 1] = 1 – \exp(-\lambda)\)となります。ここで\(m = n / \log 2 \approx 1.44n\)と置けば、\(\Pr[A[i] = 1] = 1/2\)となります。なので平均的に\(A\)のうち丁度半分が\(1\)になっていることが分かります。さらに(解析的に面倒な部分を飛ばすと)、高い確率(例えば\(99/100\)以上)で、\(A\)のうちほぼ半分のビットが\(1\)になります。よって辞書に無い単語\(y\)に対して\(\mathrm{lookup}(y)\)がYesと出力する確率は(ほぼ)\(1/2\)です。
何故ここが解析的に面倒かについて簡単に触れておきますと、\(A[i]=1\)という事象と\(A[j]=1\)という事象は互いに独立ではない為に、こういう議論に対してよく使われるChernoff Boundが使えなくなるからです。
まとめると、\(n\)個のアイテムを\(1.44n\)ビット使って保存することができ、lookupの計算時間は\(O(1)\)かつfalse positiveが発生する確率は\(1/2\)となります。
次にBloom Filterについて解説します。先に説明したハッシュではハッシュ関数を一つだけ利用していましたが、今回はハッシュ関数を\(k\)個利用します。
Bloom Filterは次のように実現します。
構築:
\(m\)ビット配列\(A\)を用意する。
\(k\)個の独立なハッシュ関数\(h_1,\ldots,h_k\)を用意する。
\(\mathrm{for} i = 1,\ldots,n\)
\(A[h_1(x_i)] \leftarrow 1,\ldots,A[h_k(x)] \leftarrow 1\)
\(\mathrm{lookup}(y)\):
\(A[h_1(x)], \ldots, A[h_k(x)]\)の全てが\(1\)ならYes, そうでなければNoと出力。
解析はハッシュの時とほぼ同様です。まずBloom Filterはfalse negativeを持ちません。つまり\(y\)が辞書に存在すれば\(\mathrm{lookup}(y)\)は必ずYesと出力します。また\(\mathrm{lookup}(y)\)の計算時間は\(O(k)\)です。なので問題はfalse positiveが起こる、つまり\(y\)が辞書に存在しないのに\(\mathrm{lookup}(y)\)がYesと出力する確率です。
さて\(n\)個のアイテムを挿入するのは、\(m\)個のビンに\(kn\)個のボールを入れる操作とみなすことが出来ます。この操作も先ほどと同じようにポワソン分布で近似することが出来ます。今度は\(m = kn / \ln 2\)と選ぶことにしましょう。すると、一つのビンには平均的には\(\lambda = kn/m = \log 2\)個のボールが入ることになります。よって\(\Pr[A[i]=1] \approx 1 – \exp(-\lambda) = 1/2\)となります。
再び解析的に面倒な点を無視すると、高い確率で\(A\)のうちほぼ半分のビットが\(1\)になっていることが分かります。\(y\)が辞書に無い単語とします。すると\(h_1(y),\ldots,h_k(y)\)は互いに独立な\(\{1,\ldots,m\}\)中の乱数となります。よって全てが\(1\)になっている確率は(ほぼ)\(2^{-k}\)であり、Yesと出力する確率も(ほぼ)\(2^{-k}\)となることが分かります。
まとめると、Bloom Filterでは\(n\)個のアイテムを\(1.44kn\)ビット使って保存することができ、lookupの計算時間は\(O(k)\)かつfalse positiveが発生する確率は\(1/2^k\)となります。つまり\(k\)を用いて辞書のサイズと計算時間及びfalse positiveの確率の間にトレードオフが達成出来たことになります。false positiveの確率が指数的に下がるのを見るとこれはかなり良いトレードオフであると言えるでしょう。
単純かつ性能が良いということでBloom Filterは実用的にも広く使われているのではないかと思われます。Bloom Filterはその後多くの拡張がなされており、要素の削除に対応したCounting Filterや、要素に対応する整数値を保存するBloomier Filterなどが知られています。
Tag
