Class: Bloomer::Scalable

Inherits:
Object
  • Object
show all
Includes:
Msgpackable
Defined in:
lib/bloomer.rb,
lib/bloomer/msgpackable.rb

Overview

Automatically expanding bloom filter. See gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf

Constant Summary collapse

S = 
2
R = 
Math.log(2) ** 2

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Msgpackable

included, #to_msgpack

Constructor Details

#initialize(initial_capacity = 256, false_positive_probability = 0.001) ⇒ Scalable

Returns a new instance of Scalable.



66
67
68
69
 
# File 'lib/bloomer.rb', line 66

def initialize(initial_capacity = 256, false_positive_probability = 0.001)
  @false_positive_probability = false_positive_probability
  @bloomers = [Bloomer.new(initial_capacity, false_positive_probability * R)]
end

Class Method Details

.from_msgpack_ext(data) ⇒ Object 



58
59
60
61
62
63
 
# File 'lib/bloomer/msgpackable.rb', line 58

def self.from_msgpack_ext(data)
  false_positive_probability, bloomers = msgpack_factory.load(data)
  ::Bloomer::Scalable.new.tap do |b|
    b.from_msgpack_ext(false_positive_probability, bloomers)
  end
end

Instance Method Details

#add(string) ⇒ Object 



79
80
81
82
83
84
85
86
 
# File 'lib/bloomer.rb', line 79

def add string
  l = @bloomers.last
  r = l.add(string)
  if r && (l.count > l.capacity)
    @bloomers << Bloomer.new(l.capacity * S, @false_positive_probability * (R**@bloomers.size))
  end
  r
end

#capacity ⇒ Object 



71
72
73
 
# File 'lib/bloomer.rb', line 71

def capacity
  @bloomers.last.capacity
end

#count ⇒ Object 



75
76
77
 
# File 'lib/bloomer.rb', line 75

def count
  @bloomers.inject(0) {|i,b|i + b.count}
end

#from_msgpack_ext(false_positive_probability, bloomers) ⇒ Object 



54
55
56
 
# File 'lib/bloomer/msgpackable.rb', line 54

def from_msgpack_ext(false_positive_probability, bloomers)
  @false_positive_probability, @bloomers = false_positive_probability, bloomers
end

#include?(string) ⇒ Boolean

only return false if no bloomers include string.

Returns:

  • (Boolean) 


89
90
91
 
# File 'lib/bloomer.rb', line 89

def include? string
  @bloomers.any? { |ea| ea.include? string }
end

#to_msgpack_ext ⇒ Object 



50
51
52
 
# File 'lib/bloomer/msgpackable.rb', line 50

def to_msgpack_ext
  self.class.msgpack_factory.dump([@false_positive_probability, @bloomers])
end