Common Lispで動くブルームフィルタ作った

ブルームフィルタとは，そのフィルタに要素が登録されているかを確率的に判定し，そのフィルタに要素が登録されていないことを確実に判定できるデータ構造である．ブルームフィルタは要素が登録されているかを判定することはできるが，その要素を取り出すことはできないという特徴を持っている．なので「フィルタ」である。

今回このブルームフィルタをCommon lispで実装した．実装したとはいっても以下のエントリの実装を真似ただけのものである．

postd.cc

Murmurhash3の実装がなかったので，ハッシュ関数にはひとまずIroncladのadler32を採用した．Ironcladを使った理由は，手頃で一般的なライブラリであること，adler32を使った理由は，そこそこ早いという話をどこかで聞いたからで，大した理由はない．

github.com

インストール

quicklispに登録していないので，bloomを使うにはこれをダウンロードしてASDFのレポジトリに配置するか，以下のようにqlotでダウンロードする．

# qlfile
github bloom windymelt/bloom

使う

さて，使用方法は以下の通り．

(defparameter *bloom* (bloom:make-bloom 256)) ; 256ビット長のブルームフィルタを作成
(bloom:bloom-add "hoge" *bloom*) ; => t ブルームフィルタに"hoge"を追加する
(bloom:bloom-member-p "hoge" *bloom*) ; => t ブルームフィルタに"hoge"があるかどうか確認
(bloom:bloom-clr *bloom*) ; ブルームフィルタを初期化

ブルームフィルタの実態はただのビットベクトルで，各関数はこれを操作しているにすぎない．

(make-bloom 32) ; => #*00000000000000000000000000000000

bloom:*k* を変化させることで，ブルームフィルタに使うハッシュ関数の数を調節できる．

bloom::item-hashは根幹となる部分で，オブジェクトのハッシュ値を求める箇所である．

(defun item-hash (it)
  "Calculate hash of item. Hash is divided to two parts to calc double-hash."
  (let ((hash (digest-sequence :adler32 (integer-to-octets (sxhash it)))))
    (values (subseq hash 0 2) (subseq hash 2)))) ; 2 bytes = 16 bits

ブルームフィルタに使うのは複数個のハッシュ値であるため，これを組み合わせてダブルハッシュ法によりハッシュ値を複数求める．

(defun nth-hash (n hasha hashb filter-size)
  "Calculate composed hash with double-hash method."
  (mod (+ (octets-to-integer hasha) (* n (octets-to-integer hashb))) filter-size))

開発した理由

機械学習の勉強をしていたところ，学習アルゴリズム中でハッシュリストの読み出しがボトルネックとなっていた．実際に値を取り出すわけではなく，存在だけが確認できればよかったためブルームフィルタの使用を検討した．既存のライブラリはかなり低速だったため，自分で簡易なものを実装した．

追記

Bloom filterはCommon Lispで実装されたものを以前仕事で使ったことあるけど気をつけて型宣言すれば非常に速いっす。Allegro CLではビットベクタのインデックスの範囲チェックを省くのに型宣言での値の範囲指定がクリティカルだったような覚えがhttps://t.co/aP0hgUVK0R
— Shiro Kawai (@anohana) 2018年1月2日