Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment