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見て、ようやく理解できました。
手順としては、
上の作業を、登録する単語数だけ繰り返すと、辞書（= ビット配列）の完成です。
あとは、検索時に、
- 辞書作成時に使用したハッシュ方式で、ハッシュ値を取得（ここでも、複数のハッシュ値が得られる）
- 各ハッシュ値をインデックスとして、ビット配列を検索する
- 各ハッシュ値が示す、ビット配列のすべての要素が立っていたら、その要素は「ある」と判定される
となります。
いつものように、続きは一応隠します。（直接見ると隠れません）
自分なりの答え
順番通りではないですが、要素通りに進めます。
ハッシュを取得する（インターフェイス）
from abc import ABCMeta, abstractmethod class hash_maker(metaclass=ABCMeta): """文字列からハッシュを生成します。""" @abstractmethod def make(self, word: str, size: int) -> int: """ハッシュ値を生成します。""" pass
ハッシュ生成クラス
今回は、アルゴリズムとして、MD5、SHA1、SHA224、SHA512を使いました。
これらのアルゴリズムを使う場合、Pythonだとhashlibというモジュールが標準で用意されているため、楽できます。
import hashlib from IHash_Maker import hash_maker class md5_hash_maker(hash_maker): def make(self, word: str, size: int) -> int: m = hashlib.md5(word.encode()) word_bytes = m.hexdigest().encode() sum_ax = 1 for v in word_bytes[0: -1: 2]: if v != 0: sum_ax *= v return sum_ax % size
例として、MD5の場合のハッシュ生成を載せています。これと同じような実装が、SHA1、SHA224、SHA512についても存在します。
問題文通り、ハッシュ生成後に、そのバイト値を使って、ハッシュを再計算しています。
引数sizeは、ビット配列のサイズを表します。
なお、剰余を使っている部分のアルゴリズムが非常に雑です。工夫の余地が大いにあります。
辞書（フィルター）クラス
import numpy as np from IHash_Maker import hash_maker class bloom_filter(object): """辞書探索：Bloom Filterの実装です。""" def __init__(self, size: int, *hashes: hash_maker): self._size = size self._bytes_init() self._hashes = list(hashes) def _bytes_init(self): self._bytes = np.zeros(self._size, dtype=bool) def _get_indexes(self, word: str) -> tuple: hashes = self._hashes return (h.make(word, self._size) for h in hashes) def search(self, word: str): """語句が存在するか判定します。""" indexes = self._get_indexes(word) for i in indexes: if not self._bytes[i]: return False return True def save(self): """現在の辞書を保存します。""" np.save("dict.npy", self._bytes) def load(self): """作成した辞書を読み込みます。""" self._bytes = np.load("dict.npy") def read_words(self): """語句リストから辞書を作成します。""" self._bytes_init() for line in open("wordlist.txt", mode="r", encoding="utf-8").readlines(): indexes = self._get_indexes(line.rstrip('\r\n')) for i in indexes: self._bytes[i] = True
コンストラクタで、ビット配列サイズと、ハッシュ化アルゴリズムを受け取ります。
read_wordsメソッドで、ファイルから辞書を作成しています。
また、一度作った辞書を保存できるようsaveを用意し、呼び出すためのloadも用意しています*2。
ビット配列の実現*3には、numpyを使っています。
初期化方法によってクラスを分けるべきというのは分かっていますが、今回はそのままにさせてください。
呼び出し
from words_dict import bloom_filter from md5_hash import md5_hash_maker from sha1_hash import sha1_hash_maker from sha224_hash import sha224_hash_maker from sha512_hash import sha512_hash_maker def main(): size = 2 ** 20 words = bloom_filter( size ,md5_hash_maker() ,sha1_hash_maker() ,sha224_hash_maker() ,sha512_hash_maker() ) # words.read_words() # words.save() words.load() print(words.search("larbo")) # exist word print(words.search("researcher")) # exist word print(words.search("zzpee")) # not exist word print(words.search("zzz")) # exist word
配列サイズ（2の20乗）と、ハッシュ化アルゴリズムを指定して、bloom_filterを初期化。
loadもしくはread_wordsによって、辞書を作成し、searchを呼び出して語句判定を行っています。
追加問題
ランダムに生成した5文字、ということですが、
def get_random(): n = 5 return ''.join([random.choice(string.ascii_letters) for i in range(n)])
という関数を用意して、生成します。
mainの末尾に
for i in range(5): val = get_random() print("search：" + val + ".exist=" + str(words.search(val)))
というソースを追加して、結果を出します。
結果
search：JWeLV.exist=True search：XjRmm.exist=False search：BFmiZ.exist=True search：OZYCQ.exist=True search：aKlxr.exist=True
はい、ダメすぎます。
ハッシュのところ、もっと工夫しないとダメみたいですね。
アルゴリズムを変える
hash_makerの部分を、ここを参考に書き換えました。
import hashlib from IHash_Maker import hash_maker class md5_hash_maker(hash_maker): def make(self, word: str, size: int) -> int: m = hashlib.md5(word.encode()) word_bytes = m.hexdigest().encode() sum_ax = 1 for i, v in enumerate(word_bytes[0: -1: 2]): sum_ax += v * (127 ** i) return sum_ax % size
127というのは、良くないと思いますが…
これにより、
search：xlUKj.exist=False search：iZXuy.exist=False search：DPEKi.exist=False search：ucPUi.exist=False search：IZseI.exist=False
のように、精度は上がったようです。
ただ、まだまだ工夫の余地はありそうです*4。
おわりに
上のような設計ですが、利点としては、
- ハッシュ化アルゴリズムを独立して修正できる
- 二回目以降は、保存した辞書（バイト配列）をそのまま利用できる
というものが挙げられます。
実際に作るときは、私のようないい加減なハッシュアルゴリズムは使わないようにしましょう。
