BloomFilter

common lisp algorithm

オンラインで読める『Real World Haskell』という本の目次を眺めていたら、BloomFilterという言葉を発見。
どうやらデータ構造の一種らしいが、聞いたことがなかったので調べてみた(Wikipediaで)。


結果、セット(集合)を表すためのデータ構造だということが分かった。
偽陽性*1はあるが、メモリ使用量が凄く少なくて済むのが特徴で、例えば-目安として、だが- 要素数が100万のセットなら1MB程度のメモリで表現できるようだ。ちなみに、集合中の要素の列挙や削除といった操作は出来ない
実装としては、衝突を考慮しない and 要素を格納しないハッシュ、といった感じ。


BloomFilterの初期化、要素追加、帰属判定を行うcommon lispのプログラムを書いてみたので、下に載せる。

;; 構造体: ビット配列と要素の追加・判定に用いるハッシュ関数のリストを持つ
(defstruct bloom-filter
  (array #*0 :type simple-bit-vector)
  (hash-function-list '() :type list))

;; n個の異なるハッシュ関数のリストを生成する
;; ※ ハッシュ関数の作成方法はテキトウ
(defun gen-n-hash-functions (n)
  (cons #'sxhash
        (loop for i from 1 below n 
              collect (lambda (s) (sxhash (format nil "~A~A" s n))))))

;; [初期化]
;; ビット配列のサイズと、使用するハッシュ関数リストを引数として、bloom-filter構造体を初期化する
;; sizeには、集合の(最終的な)要素数*10、以上の数を指定するのが望ましい
(defun init-bloom-filter (size &optional (hash-function-list (gen-n-hash-functions 4)))
  (make-bloom-filter
   :array (make-array size :element-type 'bit :initial-element 0)
   :hash-function-list hash-function-list))

;; bloom-filterアクセス用の補助関数群
(defun blm-array (blm-filter)     (bloom-filter-array blm-filter))
(defun blm-size (blm-filter)      (length (bloom-filter-array blm-filter)))
(defun blm-hash-funs (blm-filter) (bloom-filter-hash-function-list blm-filter))

;; [要素追加]
;; 集合に要素を追加する
;;  以下の操作をハッシュ関数の数だけ繰り返す
;;   elementのハッシュ値を計算する
;;   上の値をビット配列のインデックスとし、該当個所のビットを1に設定する
(defun blm-insert (element blm &aux (bits (blm-array blm)))
  (dolist (fn (blm-hash-funs blm) 'done)
    (let ((index (mod (funcall fn element) (blm-size blm))))
      (setf (sbit bits index) 1))))

;; [帰属判定]
;; 引数の要素が、集合に含まれるかどうかを判定する
;;  全ての、ビット配列[ハッシュ関数(element)]が1に設定されているなら、この要素は集合内に含まれると判定する
;;  ※ 実際に、その要素を追加していないくても、偶然全てのハッシュ値が一致してしまう可能性があるので、BloomFilterは疑陽性を有する
(defun blm-member (element blm)
  (every (lambda (fn)
           (let ((index (mod (funcall fn element) (blm-size blm))))
             ;; ビットは1か?
             (= 1 (sbit (blm-array blm) index))))
         (blm-hash-funs blm)))

結構単純。
(上でも少し触れたが)普通のハッシュと似ていると思うが、要素を保持しないことと、(ハッシュ値の)衝突を考慮しないことと、複数のハッシュ関数を使用すること、が異なるかな。
要素を保持しないことで使用メモリを(一つのハッシュ関数につき約1bitに)抑えられるが、そのために衝突の判定ができなくなり、その衝突率(疑陽性率?)を下げるために（一つではなく)複数のハッシュ関数を使用するようにしている、といった感じだろうか。
いずれにせよ、メモリ使用量が極めて少ないのは良い。

ハッシュ関数の数

複数のハッシュ関数を使えば、要素の(ハッシュ値の)衝突率を下げられると書いたが、ハッシュ関数を増やすほど一つの要素が使用するbit数も多くなるので、あまり増やし過ぎると(ビット配列の大半が1で埋まってしまい)逆に疑陽性率が上がってしまうような気もする。
あと実際上の問題として、ハッシュ関数が増えるほど、要素の追加・判定に要する時間が長くなる。


Wikipediaの『ブルームフィルタ』の項目には、ビット配列のサイズと集合の要素数、ハッシュ関数の数から、疑陽性率を求める計算式が載っていた。
lispで書くと次のようになる。

(defun false-positive-rate(bits-size elem-num hash-num)
  (float (expt (- 1 (exp (- (/ (* hash-num elem-num) bits-size)))) hash-num)))

この関数を使って以下の二つのグラフを作成した。


グラフ1(全体図)
Y軸: 疑陽性率(%)、 X軸: 集合の要素数/ビット配列のサイズ*100(%)、 線: ハッシュ関数の数


グラフ2(疑陽性率が低い箇所の拡大図)
Y軸: 疑陽性率(%)、 X軸: 集合の要素数/ビット配列のサイズ*100(%)、 線: ハッシュ関数の数


このグラフを見ると、ハッシュ関数を複数使うことの効果は、一目瞭然だ。
ハッシュ関数が一つの場合は、集合の要素数が少ない場合でも、疑陽性率を抑えるためには、巨大なビット配列を用意しなければならない。

また、ハッシュ関数の数が増えた場合の(疑陽性率の上昇勾配が急になるという)デメリットもグラフからは見て取れる。
実用の場面では、疑陽性率は最大でも1%程度に抑える必要があると思う。
その際に、例えばハッシュ関数を20個使った場合は、(x軸が6%を過ぎた辺りからの)疑陽性率の上昇率が高すぎて、ハッシュ関数を3個しか使わなかった場合よりも、悪い結果となっている。※もちろん、ビット配列を十分余裕がある場合は、ハッシュ関数の数が多ければ多いほど(?)、疑陽性率も低く抑えることができる。
処理速度も考慮すると、ビット配列のサイズを(集合に追加する予定の)要素数の10倍以上にして、使用するハッシュ関数は4〜8個くらいにするのが、バランスが良いかもしれない。

*1:集合に含まれていない要素を、誤って含まれていると判定してしまう可能性があるということ