Counting Bloom Filterを試す

プログラミング

はじめに

悩み多き年頃なので、進捗ダメです。
KVS見てるときに出てきた、次元圧縮っぽさがあるBloom Filterを試してみる。

Bloom Filterとは

  • 「ある要素が集合に含まれるか否か？」を扱えるデータ構造
  • 要素をそのまま保存せず、ハッシュ値にしたものを配列に保存する
  • アルゴリズム
    • サイズがMの配列A[]を用意し、すべて値を0にしておく
    • 要素の追加
    • 要素の検索
      • 追加時と同様にハッシュ値にし、すべて1になっていれば、要素が含まれると判断する
  • 他の組み合わせでも1となってしまう組み合わせがあるために、「間違って要素がある、と判断してしまう可能性」がある＝偽陽性
  • MやKを調整する事で、記憶容量と偽陽性のトレードオフを実現できる
Counting Filter
  • 基本的にBloom Filterのアルゴリズムでは削除ができない
    • 無理矢理行おうとすると、予期せぬ組み合わせで消してしまって偽陰性も出てしまう
  • Bloom Filterの配列において、0/1のビットではなく、カウンタに拡張したもの
  • 追加ではインクリメント、削除では存在を確認してデクリメント、検索では0でないこと、で実現できる

コード

文字列を要素に、Counting Bloom Filterで要素の追加・検索を試してみる。

#include <iostream>
#include <vector>
#include <cmath>

class CountingBloomFilterForString {
  int M; //配列のサイズ
  int N; //現在登録されている数
  std::vector<int> base; //ハッシュ関数のBASE値
  std::vector<int> bit; //保存用の配列

  //ハッシュ関数
  unsigned long long hash(const std::string& str, int b){
    unsigned long long ret = 0;
    for(size_t i=0; i<str.length(); i++){
      ret = ret * b + (char)(str[i]);
    }
    return ret;
  }

public:
  //M : 配列のサイズ
  //h_base : ハッシュ関数のBASE値
  CountingBloomFilterForString(int M, const std::vector<int>& h_base):
    M(M),bit(M,0),base(h_base),N(0)
  {}

  //配列の状態をダンプ
  void dump_bit(){
    int zero = 0, nonzero = 0;
    for(int i=0; i<bit.size(); i++){
      std::cout << bit[i];

      if(bit[i] > 0) nonzero++;
      else zero++;
    }
    std::cout << std::endl;

    std::cout << "zero:    " << zero << std::endl;
    std::cout << "nonzero: " << nonzero << std::endl;
  }

  //要素を追加
  void insert(const std::string& str){
    for(int k=0; k<base.size(); k++){
      unsigned long long h = hash(str, base[k]);
      bit[ h%M ]++;
    }
    N++;
  }

  //要素を削除
  bool remove(const std::string& str){
    if(!find(str)) return false;
    for(int k=0; k<base.size(); k++){
      unsigned long long h = hash(str, base[k]);
      bit[ h%M ]--;
    }    
    return true;
  }

  //要素を検索
  bool find(const std::string& str){
    for(int k=0; k<base.size(); k++){
      unsigned long long h = hash(str, base[k]);
      if(bit[ h%M ] <= 0) return false;
    }    
    return true;
  }

  //find()が間違って「ある」と判定する確率
  double prob_fp(int n){
    int K = base.size();
    return pow(1.0-exp(-K*(double)n/M), K);
  }
};


//乱数
// 注意: longではなくint(32bit)にすべき
unsigned long xor128(){
  static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
  unsigned long t;
  t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
//適当な文字列を返す
std::string get_random_text(){
  std::string ret = "";
  for(int i=0; i<10; i++){
    ret += 'a' + xor128() % 26;
  }
  return ret;
}


int main(){
  
  int M = 100000; //配列のサイズ
  int N = 10000; //入力文字列の数

  std::vector<int> base; //ハッシュのBASE値
  base.push_back(41);


  CountingBloomFilterForString bf(M, base);

  //ランダムな文字列を生成
  std::vector<std::string> strs;
  for(int i=0; i<(int)(N); i++){
    strs.push_back(get_random_text());
  }

  //生成した文字列を追加
  for(int i=0; i<strs.size(); i++){
    std::cout << strs[i] << std::endl;
    bf.insert(strs[i]);
  }
  
  //追加された状態を表示
  bf.dump_bit();

  //追加した文字列がすべて問題なく入っているか確認
  for(int i=0; i<strs.size(); i++){
    if(bf.find(strs[i]) != true){
      std::cout << "Error" << std::endl;
    }
  }

  //現在のFP率を出力
  std::cout << bf.prob_fp(strs.size()) << std::endl;

  //関係ない文字列を検索してみる
  std::cout << (bf.find("cba123")?"find!":"none") << std::endl;

  return 0;
}

結果

適当な文字列をN個入れたとき、(M,BASE)なBloomFilterの配列(ゼロと非ゼロの個数)、FP率、適当な別の文字列を検索したときの結果、を表示。

  • M=100000, N=10000, BASE=41
...
zero:    90479
nonzero: 9521
0.0951626
none
  • M=100000, N=10000, BASE=41,57
...
zero:    81899
nonzero: 18101
0.0328585
none
  • M=10000, 10000, BASE=41
...
zero:    3657
nonzero: 6343
0.632121
none
  • M=10000, 10000, BASE=41,57
...
zero:    1310
nonzero: 8690
0.747645
none

できてるっぽい。MとKでFP率の変化の仕方が変わる。
ハッシュ関数はどういうのがよいのだろうか。。。

参照