Class: BloomFilter::Filter

Inherits:
Object
  • Object
show all
Defined in:
lib/bloom_filter.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(capacity = 100, probability = 0.01) ⇒ Filter

Returns a new instance of Filter.



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
# File 'lib/bloom_filter.rb', line 14

def initialize(capacity = 100, probability = 0.01)
  # amount of inserted elements

  @count = 0

  # params ob filter, are used for comparison with params of other bloom filters

  @capacity = capacity
  @probability = probability

  #number of bits in the array

  @m = (-(capacity * Math.log(probability)) / (Math.log(2) ** 2)).ceil

  @bitset = Bitset.new(@m)

  #number of hash functions that minimizes the probability of false positives

  @k = (Math.log(2) * (@m / capacity)).ceil
end

Instance Attribute Details

#capacity ⇒ Object (readonly)

Returns the value of attribute capacity.



12
13
14
 
# File 'lib/bloom_filter.rb', line 12

def capacity
  @capacity
end

#count ⇒ Object (readonly)

Returns the value of attribute count.



12
13
14
 
# File 'lib/bloom_filter.rb', line 12

def count
  @count
end

#probability ⇒ Object (readonly)

Returns the value of attribute probability.



12
13
14
 
# File 'lib/bloom_filter.rb', line 12

def probability
  @probability
end

Instance Method Details

#add(value) ⇒ Object 



31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/bloom_filter.rb', line 31

def add(value)
  x = get_hash(value)
  was_inserted = true
  @k.times do |i|
    a, b = get_hash_params(i)
    position = get_position(a, b, x)
    was_inserted = false unless self.get_bit(position)
    self.set_bit(position)
  end
  @count += 1 unless was_inserted
  value
end

#bit_size ⇒ Object 



56
57
58
 
# File 'lib/bloom_filter.rb', line 56

def bit_size
  @m
end

#clear_bit(position) ⇒ Object 



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

def clear_bit(position)
  valid_position?(position)
  @bitset[position] = false
end

#contains?(value) ⇒ Boolean Also known as: includes?

Returns:

  • (Boolean) 


44
45
46
47
48
49
50
51
52
53
 
# File 'lib/bloom_filter.rb', line 44

def contains?(value)
  x = get_hash(value)
  result = true
  @k.times do |i|
    a, b = get_hash_params(i)
    result = false unless self.get_bit(get_position(a, b, x))
  end

  result
end

#get_bit(position) ⇒ Object 



60
61
62
63
 
# File 'lib/bloom_filter.rb', line 60

def get_bit(position)
  valid_position?(position)
  @bitset[position]
end

#intersect_with(bloom_filter) ⇒ Object 



83
84
85
86
87
88
89
 
# File 'lib/bloom_filter.rb', line 83

def intersect_with(bloom_filter)
  same_params?(bloom_filter)

  @m.times do |i|
    @bitset[i] = self.get_bit(i) && bloom_filter.get_bit(i)
  end
end

#set_bit(position) ⇒ Object 



65
66
67
68
 
# File 'lib/bloom_filter.rb', line 65

def set_bit(position)
  valid_position?(position)
  @bitset[position] = true
end

#union_with(bloom_filter) ⇒ Object 



75
76
77
78
79
80
81
 
# File 'lib/bloom_filter.rb', line 75

def union_with(bloom_filter)
  same_params?(bloom_filter)

  @m.times do |i|
    @bitset[i] = self.get_bit(i) || bloom_filter.get_bit(i)
  end
end