Skip to content

Instantly share code, notes, and snippets.

@frm
Last active Sep 13, 2016
Embed
What would you like to do?
A Look Into Bloom Filters with Ruby
require "fnv"
require "bitarray"
module BloomFilter
class V1
def initialize(opts = {})
opts = {size: 1024}.merge(opts)
@bits = BitArray.new opts[:size]
@fnv = FNV.new
@size = opts[:size]
end
def add(str)
@bits[i(str)] = 1
end
def test(str)
@bits[i(str)] == 1
end
alias_method :insert, :add
alias_method :include?, :test
private
def i(str)
@fnv.fnv1a_32(str) % @size
end
end
end
require "murmurhash3"
require "bitarray"
require "securerandom"
module BloomFilter
class V2
def initialize(opts = {})
opts = {size: 1024, hashes: 3}.merge(opts)
@bits = BitArray.new opts[:size]
@seeds = seed(opts[:hashes])
@size = opts[:size]
end
def add(str)
set i(str)
end
def test(str)
get i(str)
end
alias_method :insert, :add
alias_method :include?, :test
private
def seed(iterations)
s = []
iterations.times { s << SecureRandom.hex(3).to_i(16) }
s
end
def hash(str, seed)
MurmurHash3::V32.str_hash(str, seed)
end
def i(str)
@seeds.map { |seed| hash(str, seed) % @size }
end
def get(indexes)
indexes.all? { |i| @bits[i] == 1 }
end
def set(indexes)
indexes.each { |i| @bits[i] = 1 }
end
end
end
module DumbFilter
class Array
def initialize
@data = []
end
def test(str)
@data.include? str
end
def add(str)
@data << str
end
end
class Hash
def initialize
@data = {}
end
def test(str)
@data[str]
end
def add(str)
@data[str] = true
end
alias_method :insert, :add
alias_method :include?, :test
end
end
source "https://rubygems.org"
gem 'bitarray'
gem 'fnv'
gem 'murmurhash3'
gem 'bloomfilter-rb'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment