今回はCodeKata: Kata Five - Bloom Filtersを訳した。
ブルームフィルタについての練習。
集合の中の要素を見つけなければいけない状況になった場合、たくさんのアルゴリズムを実装しなければいけなくなったりする。
集合が小されば、ビット配列が使える。
集合が大きくなった場合は、便利なテクニックにハッシュがある。でも、集合が大きくなると制限に突き当たる。
例えば、PDAや携帯を動作環境と考えているなら、25万語をスペルチェックのためにメモリに載せておくのは、でかすぎるだろう。
同じく訪問したWebページリストが1千万ページくらいになっているのにメモリに載せておくのは、リソースを使い過ぎだろう。
幸運にも解決法がある。
ブルームフィルタは1970年に考案された要素が集合のメンバーであるかどうかの統計的なテスト法だ。
この方法はかなり必要な使用ストレージ量を減らしてくれるが、犠牲も必要だ。それは実際は要素が集合内に存在しないのに存在すると判定してしまうことだ（この反対は起こり得ない。だって、フィルタが「集合は要素を含まない」と判定したら、その通りだってことは分かる）。
正確さをコントロールできるという利点はある。それは、アルゴリズムに多くのメモリを割けば、false-positive（存在すると判定されたのに間違っている）という結果は減る。
自分は16キロバイトに8万語を収録したPDP11という辞書を用いたスペルチェッカーを書いたが、正しくない単語を極希に発見した。
（アップデート：私は、数字を誤って記憶してしまったに違いない。なぜなら、理論と一致しないからだ。残念なことに、8フロッピーをもう読めなくなってしまったため、正しい数字を得ることができなくなってしまった。スペルチェックに使う相当大きいサイズの辞書だということだけを言っておこう。）
ブルームフィルタはとてもシンプルだ。まず、0で初期化したビット配列を考える。そして探す対象を決める（今回、単語の辞書を用いた）。辞書内の各単語ごとに独立なn個のハッシュ値生成する。それぞれのハッシュ値はビット配列の配列番号だ。
ビットに別な単語が入っているなど時々衝突が起こるが、あまり気にしなくていい。
新しい単語が辞書に入ってるかどうかを調べるために、ビット配列を作成したものと同じハッシュ関数を利用する。
そして、ビットそれぞれが集合のハッシュ値と一致しているかを調べる。
もしビットが一つも立っていない場合、その単語は辞書にないので排除できる。
ブルームフィルタがfalse-postiveを出力してしまうのは、単語に対するハッシュ関数の集合が他の単語によって立てられたビットが全て一致してしまう時である。
実際問題として、ビット配列においてビットが立ちすぎていない限り、これはあまり起こらない。
（もし全てのビットが立っている場合、全ての検索においてfalse-positiveが発生するのは明らかだ。）
ブルームフィルタの数学的な議論は、Bloom Filters - the mathで行われている。
練習パート1
このKataはかなり単純だ。スペルチェッカーのブルームフィルタを実装しよう。これにはビット配列、ハッシュ関数、簡単な辞書の読み込み、単語の有無チェックが必要だ。
ハッシュ関数の場合、かなり長いハッシュ値（MD5とか）を生成するものがいつでも使えるよう記憶しておき、結果のビット列からそれより小さい値を取得する。
Unixユーザなら"/usr/dict/words"（もしくは可能なら"/usr/share/dict/words"）で単語リストを見つけられるだろう。
他の人には単語リストをwordlist.txtに置く。
ハッシュ関数の数やビット配列のサイズを変えて遊んでみよう。
練習パート2
練習パート2はオプションだ。
ランダムの5文字を生成してみよう、そして作成したスペルチェッカーに投げてみよう。
どの単語にも、OKと判定したらオリジナルの辞書を調べてみよう。
そしてfalse-positiveがあるか見てみよう。
実装してみました
# -*- coding:utf-8 -*- from bitarray import bitarray import hashlib import sys class BloomFilter(object): def __init__(self,bitLength): self.bitarr = bitarray(bitLength) # ビット配列 self.bitarr.setall(False) self.bitLength = bitLength # ビット配列の長さ self.salt = ['137','69','545'] def hashing(self,word): '''ハッシュ関数に関しては、saltを変えることによって 複数のハッシュ関数にしました。 ''' hashes = [] for x in self.salt: m = hashlib.md5() m.update(x+word) hashes.append(m.digest()[0]) return [ord(x) % self.bitLength for x in hashes] def append(self,word): '''add some hashes to the bit array''' hashes = self.hashing(word) for x in hashes: self.bitarr[x] = 1 def checkFilter(self,word): '''各ハッシュ関数を通したハッシュの値が、 ビット配列で立っているかチェック''' hashes = self.hashing(word) return all(self.bitarr[x]==1 for x in hashes) if __name__ =='__main__': bf = BloomFilter(10000) bf.append("foo") bf.append("bar") bf.append("baz") print bf.checkFilter("foo") print bf.checkFilter("bal")
