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

4/29で作成したものは，Arrayオブジェクトを用いていましたが，空間効率が悪いので，ビットアレイを用いたものに変更しました。自分で，BitArrayクラスを作成しようと思ったのですが，githubにありましたので，それを使っています。

bitarrayのインストール

rvmを使っているので，sudoは不要。

$ gem install ingramj-bitarray -s http://gems.github.com

bf_with_bitarray.rb

変更点は2ヶ所です。

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
require 'bitarray'              # (変更1)

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 = BitArray.new(SIZE) #  (変更2)
  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_with_bitarray --noecho 
(以下省略)

参考

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

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

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

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

2011-04-29 [Ruby]Bloom Filterの動作確認スクリプトをRubyで書いてみました

• http://d.hatena.ne.jp/rahaema/20110429#p1