Class: Kotoshu::DataStructures::BloomFilter

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

Overview

Bloom filter - probabilistic data structure for fast membership testing.

A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not.

Examples:

Basic usage

filter = BloomFilter.new
filter.add("hello")
filter.include?("hello")  # => true (definitely in set)
filter.include?("world")  # => false (probably not in set)

See Also:

Constant Summary collapse

DEFAULT_FALSE_POSITIVE_RATE =

Default false positive rate (1%)

0.01
DEFAULT_EXPECTED_SIZE =

Default expected number of elements

10_000

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(expected_size: DEFAULT_EXPECTED_SIZE, false_positive_rate: DEFAULT_FALSE_POSITIVE_RATE, case_sensitive: false) ⇒ BloomFilter

Create a new Bloom filter.

Parameters:

  • expected_size (Integer) (defaults to: DEFAULT_EXPECTED_SIZE) —

    Expected number of elements (default: 10_000)

  • false_positive_rate (Float) (defaults to: DEFAULT_FALSE_POSITIVE_RATE) —

    Desired false positive rate (default: 0.01)

  • case_sensitive (Boolean) (defaults to: false) —

    Whether lookups are case-sensitive (default: false)



45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/kotoshu/data_structures/bloom_filter.rb', line 45

def initialize(expected_size: DEFAULT_EXPECTED_SIZE,
               false_positive_rate: DEFAULT_FALSE_POSITIVE_RATE,
               case_sensitive: false)
  @case_sensitive = case_sensitive
  @item_count = 0

  # Calculate optimal size and hash count
  # m = -n * ln(p) / (ln(2)^2)
  # k = (m/n) * ln(2)
  @size = calculate_size(expected_size, false_positive_rate)
  @hash_count = calculate_hash_count(@size, expected_size)

  # Initialize bit array
  @bits = Array.new(@size, false)
end

Instance Attribute Details

#bits ⇒ Array<Boolean> (readonly)

Read-only view of the internal bit array. Exposed so #merge can OR bits across two filters without poking at another instance's ivars.

Returns:

  • (Array<Boolean>) —

    bit array, length == size



38
39
40
 
# File 'lib/kotoshu/data_structures/bloom_filter.rb', line 38

def bits
  @bits
end

#hash_count ⇒ Integer (readonly)

Returns Number of hash functions.

Returns:

  • (Integer) —

    Number of hash functions



29
30
31
 
# File 'lib/kotoshu/data_structures/bloom_filter.rb', line 29

def hash_count
  @hash_count
end

#item_count ⇒ Integer (readonly)

Returns Number of items added.

Returns:

  • (Integer) —

    Number of items added



32
33
34
 
# File 'lib/kotoshu/data_structures/bloom_filter.rb', line 32

def item_count
  @item_count
end

#size ⇒ Integer (readonly)

Returns Size of the bit array.

Returns:

  • (Integer) —

    Size of the bit array



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

def size
  @size
end

Instance Method Details

#add(item) ⇒ self

Add an element to the filter.

Parameters:

  • item (String) —

    The item to add

Returns:

  • (self) —

    Self for chaining



65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/kotoshu/data_structures/bloom_filter.rb', line 65

def add(item)
  normalized_item = normalize_item(item)

  @hash_count.times do |i|
    index = hash_index(normalized_item, i)
    @bits[index] = true
  end

  @item_count += 1
  self
end

#clear ⇒ self

Clear all elements from the filter.

Returns:

  • (self) —

    Self for chaining



116
117
118
119
120
 
# File 'lib/kotoshu/data_structures/bloom_filter.rb', line 116

def clear
  @bits = Array.new(@size, false)
  @item_count = 0
  self
end

#merge(other) ⇒ self

Merge another bloom filter into this one.

Parameters:

  • other (BloomFilter) —

    Another bloom filter with same parameters

Returns:

  • (self) —

    Self for chaining

Raises:

  • (ArgumentError) 


101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/kotoshu/data_structures/bloom_filter.rb', line 101

def merge(other)
  raise ArgumentError, "Cannot merge filters with different sizes" unless other.size == @size
  raise ArgumentError, "Cannot merge filters with different hash counts" unless other.hash_count == @hash_count

  @size.times do |i|
    @bits[i] = @bits[i] || other.bits[i]
  end

  @item_count += other.item_count
  self
end

#stats ⇒ Hash

Get filter statistics.

Returns:

  • (Hash) —

    Statistics including :size, :hash_count, :item_count



125
126
127
128
129
130
131
 
# File 'lib/kotoshu/data_structures/bloom_filter.rb', line 125

def stats
  {
    size: @size,
    hash_count: @hash_count,
    item_count: @item_count
  }
end