CodeKataやってみた記事、第五弾です。
今回は、Kata05: Bloom Filtersをやっていきます。
概要
今回の問題ですが、Bloom Filterというアルゴリズムを実際に書くものです。
まずはWikipediaの説明を見るのが良いと思います。
頑張って訳したのですが、結局Bloom Filterの説明がほとんどだったため、要点をまとめます。
Google翻訳に頼りましたが、自分で訳した部分と混在しています。誤りがあったらごめんなさい。
やりたいこと
何かが、集合に含まれるか調べる必要がある、という状況は数多くあるが、それはアルゴリズムで解決できる。
要素の集合に、ある要素が含まれているか知りたい。
たとえば、スペルチェックを行う際、その語句が集合に入っていたら、それは問題ないスペルであると判断できる。
要素数が少ない場合、bitmapを使う。
多くなってきた場合は、hashを使うとよい。
限界
hashが、大きい要素に対して使えるとはいえ、限界はある。
環境によって（PDA、携帯電話等を例示）は、スペルチェックのために25万語の語句をメモリ上に展開するのは難しいかもしれない。
Bloom Filterの特徴
要素が、集合への所属しているか、テストする方法。
特徴として、
- 集合を表現するための領域が大幅に削減される
- 集合に含まれないものを「ある」と報告することがある（偽陽性）
反対は成り立たない。フィルターが、集合に無いと言っているのなら、それが無いことははっきりわかる（偽陰性はない） - 精度を制御できる（より多くのメモリを確保すればいい）
フィルターの構築
フィルターは単純。
- 大きなbit配列を0で初期化する
- 辞書から検索語句を取得する
- 単語ごとに、複数のハッシュ値を生成する
- 各ハッシュ値の、ビット配列内の対応するビットを1に設定する
別の単語から、同一のハッシュ値が生成される場合はあるが、それは問題ない。
単語の検索
単語が辞書上にあるかどうか確認する。
- ビットマップの読み込みに使用したのと同じハッシュを実行
- これらのハッシュ値に対応する各ビットが設定されているかどうかを確認
- いずれかのビットが設定されていない場合、その言葉をロードしていない
偽陽性について
Bloom Filterは、ある単語のハッシュの集合が、他の単語によって以前に設定されている場合、偽陽性を報告する。
→その単語はロードしていないのに、ロードしたものとして報告してくる。
実際、ビットマップが1になっているものが多くなければ、そんなに起こらない。
→すなわち、ビットマップを大きくとると、それだけ発生可能性が下がる。
問題
上記の説明を踏まえ、Bloom Filterをベースとしたスペルチェッカーを作成しましょう。
作成する要素は、
- 何らかのbitmap（bitの配列）
- ハッシュ化関数
- 辞書からのシンプルな読込
- 単語のチェック
となります。
ハッシュ関数については、かなり長いハッシュ（MD5など）を生成するものを常に使用してから、結果からビットのシーケンスを抽出してより小さいハッシュ値を取ることができることに注意してください。
追加問題
適当な5文字を生み出す。それをスペルチェッカーに渡す。それがOKだと言う単語ごとに、元の辞書で調べてください。あなたが得る偽陽性の数を確認してください。
解答に進む前に
私の英語力のなさ故に、上の説明を見ても、何を作ればよいか理解できませんでした。
Wikipedia見て、ようやく理解できました。
手順としては、
上の作業を、登録する単語数だけ繰り返すと、辞書（= ビット配列）の完成です。
あとは、検索時に、
- 辞書作成時に使用したハッシュ方式で、ハッシュ値を取得（ここでも、複数のハッシュ値が得られる）
- 各ハッシュ値をインデックスとして、ビット配列を検索する
- 各ハッシュ値が示す、ビット配列のすべての要素が立っていたら、その要素は「ある」と判定される
となります。
いつものように、続きは一応隠します。（直接見ると隠れません）
続きを読む