bloom_filter_test.rb

require 'digest'

# ビット配列を簡単に扱う為のクラス
class BitArray
  def initialize m
    @size = (m - 1) / 32 + 1
    @array = [0] * @size
  end

  # 指定されたビット目を立てる
  def set_bit i
    @array[i / 32] |= bitmask i
  end

  # 指定されたビット目が立っているか判定する
  def set? i
    (@array[i / 32] & bitmask(i)) > 0
  end

  private
  # 指定されたビット目のビットマスクを作成
  def bitmask i
    1 << (i % 32)
  end
end

# ブルームフィルタ
class BloomFilter
  def initialize m
    @m = m
    @array = BitArray.new m
  end

  # 要素の追加
  def add s
    hashes(s).each {|n| @array.set_bit n}
  end

  # 要素が含まれているか判定
  def contains s
    !hashes(s).find {|n| !@array.set? n}
  end

  # ファイルの内容を読み込み、ブルームフィルタに登録する
  def load name
    File.open name do |f|
      f.each_line do |line|
        add line.chomp
      end
    end
  end

  private
  # ハッシュ関数で値を計算（今回は3つ）
  def hashes s
    [
      Digest::MD5.hexdigest(s).hex    % @m,
      Digest::SHA1.hexdigest(s).hex   % @m,
      Digest::SHA256.hexdigest(s).hex % @m,
    ]
  end
end

b = BloomFilter.new 8192
# ファイルの内容を読み込み
b.load 'name.txt'

# 入力を受け付けて要素が含まれているかの判定を行う
loop do
  n = gets.chomp
  break if n == 'q'
  if b.contains n
    puts 'exists!'
  else
    puts 'does not exist'
  end
end