Class: Bloomer

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

Overview

Patch Bloomer and Scalable to make them msgpackable

Defined Under Namespace

Classes: Scalable

Constant Summary collapse

VERSION = 
"1.0.0"

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Msgpackable

included, #to_msgpack

Constructor Details

#initialize(capacity, false_positive_probability = 0.001) ⇒ Bloomer

Returns a new instance of Bloomer.



5
6
7
8
9
10
11
12
13
14
 
# File 'lib/bloomer.rb', line 5

def initialize(capacity, false_positive_probability = 0.001)
  @capacity = capacity.round
  # m is the required number of bits in the array
  m = -(capacity * Math.log(false_positive_probability)) / (Math.log(2) ** 2)
  @ba = BitArray.new(m.round)
  # count is the number of unique additions to this filter.
  @count = 0
  # k is the number of hash functions that minimizes the probability of false positives
  @k = (Math.log(2) * (@ba.size / capacity)).round
end

Class Method Details

.from_msgpack_ext(data) ⇒ Object 



40
41
42
43
44
45
 
# File 'lib/bloomer/msgpackable.rb', line 40

def self.from_msgpack_ext(data)
  values = msgpack_factory.load(data)
  ::Bloomer.new(values[1]).tap do |b|
    b.from_msgpack_ext(*values)
  end
end

Instance Method Details

#add(string) ⇒ Object

returns true if item did had not already been added



17
18
19
20
21
22
23
 
# File 'lib/bloomer.rb', line 17

def add string
  count = 0
  hashes(string).each { |ea| count += @ba[ea]; @ba[ea] = 1 }
  previously_included = (count == @k)
  @count += 1 unless previously_included
  !previously_included
end

#capacity ⇒ Object

If count exceeds capacity, the provided #false_positive_probability will probably be exceeded.



38
39
40
 
# File 'lib/bloomer.rb', line 38

def capacity
  @capacity
end

#count ⇒ Object

The number of unique strings given to #add (including false positives, which can mean this number under-counts)



33
34
35
 
# File 'lib/bloomer.rb', line 33

def count
  @count
end

#from_msgpack_ext(capacity, count, k, ba_size, ba_field) ⇒ Object 



35
36
37
38
 
# File 'lib/bloomer/msgpackable.rb', line 35

def from_msgpack_ext(capacity, count, k, ba_size, ba_field)
  @capacity, @count, @k = capacity, count, k
  @ba = BitArray.new(ba_size, ba_field)
end

#include?(string) ⇒ Boolean

returns false if the item hadn’t already been added returns true if it is likely that string had been added. See #false_positive_probability

Returns:

  • (Boolean) 


27
28
29
 
# File 'lib/bloomer.rb', line 27

def include? string
  !hashes(string).any? { |ea| @ba[ea] == 0 }
end

#to_msgpack_ext ⇒ Object 



31
32
33
 
# File 'lib/bloomer/msgpackable.rb', line 31

def to_msgpack_ext
  self.class.msgpack_factory.dump([@capacity, @count, @k, @ba.size, @ba.field])
end