Bloom Filterの動作確認スクリプトをRubyで書いてみました

bf.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-

SIZE = 1987
def hashes(s)
  xs = [0, 0, 0]
  s.each_char do |c|
    o = c.ord
    xs[0] = xs[0] * 137 + o
    xs[1] = xs[1] * 69 + o
    xs[2] = xs[2] * 545 + o
  end
  xs.map{ |x| x % SIZE }
end

class BloomFilter
  def initialize
    @bitarray = Array.new(SIZE, 0)
  end

  def add(s)
    hashes(s).each { |x| @bitarray[x] = 1 }
  end

  def query(s)
    hashes(s).all? { |x| @bitarray[x] == 1}
  end
end

実行結果

$ irb -I. -rbf --noecho 
ruby-1.9.2-p180 :001 > bf = BloomFilter.new
ruby-1.9.2-p180 :002 > bf.add("hoge")
ruby-1.9.2-p180 :003 > p bf.query("hoge")
true
ruby-1.9.2-p180 :004 > p bf.query("hoga")
false
ruby-1.9.2-p180 :005 > bf.add("foo")
ruby-1.9.2-p180 :006 > bf.add("bar")
ruby-1.9.2-p180 :007 > bf.add("baz")
ruby-1.9.2-p180 :008 > p bf.query("hoga")
false
ruby-1.9.2-p180 :009 > p bf.query("foo")
true

参考

Bloom filterのシンプルな実装 - 西尾泰和のはてなダイアリー

• http://d.hatena.ne.jp/nishiohirokazu/20080213/1202912207

[を] Bloom Filter の動作確認スクリプトを Perl で書いてみました

• http://chalow.net/2011-04-28-3.html