Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

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のシンプルな実装 - 西尾泰和のはてなダイアリー

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

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