Class: BloomFilter

Inherits:
Object
  • Object
show all
Defined in:
lib/bloom_filter.rb,
lib/bloom_filter/client.rb,
lib/bloom_filter/server.rb,
lib/bloom_filter/protocol.rb,
lib/bloom_filter/bit_vector.rb

Defined Under Namespace

Modules: Protocol Classes: BitVector, Client, Server, Timeout

Constant Summary collapse

BITS_PER_FIXNUM =

this can really be more on 64-bit systems

31
DUMP_SEPARATOR = 
"\n"

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(m, k, bits = nil) ⇒ BloomFilter

Returns a new instance of BloomFilter.



30
31
32
33
34
 
# File 'lib/bloom_filter.rb', line 30

def initialize(m, k, bits = nil)
  @k = k
  @m = m
  @bits = bits || Array.new((m.to_f / BITS_PER_FIXNUM).ceil, 0)
end

Class Method Details

.load(dumped) ⇒ Object 



25
26
27
28
 
# File 'lib/bloom_filter.rb', line 25

def self.load(dumped)
  m, k, *bits = dumped.split(DUMP_SEPARATOR).collect { |v| v.to_i }
  new(m, k, bits)
end

.new_server(n, p) ⇒ Object 



8
9
10
11
12
 
# File 'lib/bloom_filter/server.rb', line 8

def self.new_server(n, p)
  klass = Class.new(Server)
  klass.filter = BloomFilter.new(*BloomFilter.optimal_values(n, p))
  klass
end

.optimal_values(estimated_elements, probability) ⇒ Object 



7
8
9
10
11
 
# File 'lib/bloom_filter.rb', line 7

def self.optimal_values(estimated_elements, probability)
  m = -(estimated_elements * Math.log(probability)) / (Math.log(2) ** 2)
  k = 0.7 * (m / estimated_elements)
  [m.round, k.round]
end

.read(file) ⇒ Object 



13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/bloom_filter.rb', line 13

def self.read(file)
  m = file.gets(DUMP_SEPARATOR).to_i
  k = file.gets(DUMP_SEPARATOR).to_i
  bits = Array.new((m.to_f / BITS_PER_FIXNUM).ceil, 0)
  index = 0
  while line = file.gets(DUMP_SEPARATOR)
    bits[index] = line.to_i
    index += 1
  end
  [m, k, bits]
end

Instance Method Details

#&(els) ⇒ Object 



52
53
54
 
# File 'lib/bloom_filter.rb', line 52

def &(els)
  els.select { |el| self.include?(el) }
end

#add(el) ⇒ Object Also known as: << 



36
37
38
39
40
41
 
# File 'lib/bloom_filter.rb', line 36

def add(el)
  @k.times do |i|
    self.set_bit(Zlib.crc32("#{i}#{el}") % @m)
  end
  self
end

#dump ⇒ Object 



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

def dump
  [@m, @k, *@bits].join(DUMP_SEPARATOR)
end

#include?(el) ⇒ Boolean

Returns:

  • (Boolean) 


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

def include?(el)
  @k.times do |i|
    return false if !bit_set?(Zlib.crc32("#{i}#{el}") % @m)
  end
  true
end

#replace(file) ⇒ Object 



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

def replace(file)
  m, k, bits = self.class.read(file)
  @m, @k = m, k
  @bits.replace(bits)
end