Probability and Computing

Twitter連携とmixi連携を付けてみた。
はてなブログの使い方を練習しつつ連投する。

例によってこの本

確率と計算 ―乱択アルゴリズムと確率的解析―

の話の続き。

そういえば。
この本に、バケツソートはある条件下で平均のソートができる、ということが書いてあって面白かった。ソートの下界はなのだが、条件を付ければ線形まで落とせるようだ。詳細はググればすぐに出そうなので書かないけれど、この内容で分割統治の力を再認識した。
分散も分割が基本戦略になると思うのだけれど、分割はいいとしてその統合（MapReduceで言うところのReduce）の実装って実はとても難しいのではないかと思う。統合で知恵を絞れば、賢い分散ができそうだなぁという直感。

さて、この前は確率的データ構造というのが出てきたが、本ではBloomフィルタというのを紹介している。（ちなみに、僕はこのBloomフィルタをこの本を読むまで知らなかった）多数のデータを一列のビット列にハッシュする、というのがコアアイデア。すべてのデータは、1つのビット列になってしまう。なので、どんなデータが入っていたかを取り出すことはできない。えできないの？はいできません。

そんなのを何につかうねん…というと、あるデータがそのデータ構造内に在るか無いかを知りたいときに使います。つまり辞書です。具体的にはスペルチェック辞書などで使われているようです。問題を判定問題へと限定することで、情報の量を極端に減らしたデータ構造と言える。

Bloomフィルタが何であるのかは、この本よりWikipediaの方がわかりやすいのでｗ置いておこう。
こういうデータ構造で問題になるのは、別のデータが同じハッシュに写されてしまうことです。具体的には、本当はBloomフィルタ内に追加されたことは無いデータが、たまたま別のデータと同じハッシュになったというだけで（別のデータと同じハッシュになってしまい）「そのデータは存在する」とreturnしてしまうことがあります。偽陽性と言うそうです。しかしこれは避けられませぬ。

となると、問題はその確率がどのくらいあるのか、ということです。
m個のデータをビット列へハッシュした場合の偽陽性確率を定数内で抑えたい場合、必要なビット数はです。なので、例えばビット数にビットを使うとする。すると、その場合の偽陽性確率を計算すると、1/m未満という結果が得られる。すなわち、全データが2^16=65536個あったとすると、32ビット使えば、偽陽性の確率は1/65536未満となる。32bit機なら、メモリ１列分。

え　こ　れ　す　ご　く　ね　？

Bloomフィルタはハッシュ関数を複数(k個)使うのだが、この数も最適化できる。偽陽性確率fをkの関数として微分すると、結果は。
まぁそんなことはどうでもいい。おもしろいのは、偽陽性確率fを、とあるビットが0である確率pの関数として見た場合。実はpが1/2のときに確率は最小になる。つまり、できあがったBloomフィルタはランダムに0と1が並んだビット列に見える。へーへー。

というわけで、時間があればBloomフィルタを組んでみようと思う。

何でBloomフィルタをこんなに気にしているのかというと、この構造は自分の研究に応用できそうな気がしたから。DNAシーケンスのモチーフ検索はダイナミックプログラミングと近似で得るのが多いが、用途次第ではとても時間が掛かる検索になる。が、Bloomフィルタを使えば、高速なモチーフ検索ができそうである。判定問題なのでモチーフ検索に特化したものになりそうだけど。