@spec bits_info(t()) :: bits_info()

Returns a map representing the bit state of the atomics_ref.

Use this for debugging purposes.

Examples

iex> b = Talan.BloomFilter.new(1000)
iex> b |> Talan.BloomFilter.bits_info()
%{total_bits: 9600, set_bits_count: 0, set_ratio: 0.0}

@spec cardinality(t()) :: non_neg_integer()

Returns a non-negative integer representing the estimated number of unique elements in the filter.

A saturated filter has no unset bits, so its cardinality cannot be estimated reliably; in that case this function returns a finite fallback value.

Examples

iex> b = Talan.BloomFilter.new(1000)
iex> b |> Talan.BloomFilter.cardinality()
0
iex> b |> Talan.BloomFilter.put("Barna")
iex> b |> Talan.BloomFilter.cardinality()
1
iex> b |> Talan.BloomFilter.put("Barna")
iex> b |> Talan.BloomFilter.cardinality()
1
iex> b |> Talan.BloomFilter.put("Kovacs")
iex> b |> Talan.BloomFilter.cardinality()
2

@spec clear(t()) :: t()

Clears every bit in bloom_filter and returns the same filter.

The filter is reset in place without reallocating its atomics reference. Clearing individual atomic words is safe during concurrent access, but the filter is not cleared as one atomic operation. Concurrent reads may observe a partially cleared filter, and concurrent writes may be cleared or remain set depending on their timing.

Examples

iex> b = Talan.BloomFilter.new(1000)
iex> Talan.BloomFilter.put(b, "Barna")
iex> Talan.BloomFilter.clear(b) == b
true
iex> Talan.BloomFilter.member?(b, "Barna")
false

@spec deserialize(binary()) :: t()

Deserializes a binary into a Bloom filter.

This function takes a binary that was previously created by serialize/1 and reconstructs the Bloom filter structure.

The modules and code versions defining the serialized hash functions must be available and compatible.

Examples

iex> bloom_filter = Talan.BloomFilter.new(1000)
iex> serialized = Talan.BloomFilter.serialize(bloom_filter)
iex> deserialized = Talan.BloomFilter.deserialize(serialized)
iex> is_struct(deserialized, Talan.BloomFilter)
true

@spec false_positive_probability(t()) :: float()

Returns a float representing the current estimated false-positive probability.

Examples

iex> b = Talan.BloomFilter.new(1000)
iex> b |> Talan.BloomFilter.false_positive_probability()
0.0 # fpp zero when bloom filter is empty
iex> b |> Talan.BloomFilter.put("Barna") # fpp increases
iex> b |> Talan.BloomFilter.put("Kovacs")
iex> fpp = b |> Talan.BloomFilter.false_positive_probability()
iex> fpp > 0 && fpp < 1
true

@spec hash_term(t(), term()) :: [non_neg_integer(), ...]

Hashes term with all hash_functions of %Talan.BloomFilter{}. Custom hash functions must return non-negative integers.

Returns a list of hashed values.

Examples

iex> b = Talan.BloomFilter.new(1000, hash_functions: [fn _term -> 42 end])
iex> Talan.BloomFilter.hash_term(b, :any_term_can_be_hashed)
[42]

@spec intersection([t(), ...]) :: t()

Intersects the atomics of multiple %Talan.BloomFilter{} structs into one new struct.

All filters must have the same size and use the same hash functions.

Returns a new %BloomFilter{} struct whose set bits are the intersection of the Bloom filters in the list.

Examples

iex> hash_functions = [fn term -> :erlang.phash2(term) end]
iex> b1 = Talan.BloomFilter.new(1000, hash_functions: hash_functions)
iex> b1 |> Talan.BloomFilter.put("GitHub")
iex> b2 = Talan.BloomFilter.new(1000, hash_functions: hash_functions)
iex> b2 |> Talan.BloomFilter.put("GitHub")
iex> b2 |> Talan.BloomFilter.put("Octocat")
:ok
iex> b3 = Talan.BloomFilter.intersection([b1, b2])
iex> b3 |> Talan.BloomFilter.member?("GitHub")
true
iex> b3 |> Talan.BloomFilter.member?("Octocat")
false

@spec member?(t(), any()) :: boolean()

Checks for membership of term in bloom_filter.

Returns false if the term is definitely absent. Returns true if the term may be present.

Examples

iex> b = Talan.BloomFilter.new(1000)
iex> b |> Talan.BloomFilter.member?("Barna Kovacs")
false
iex> b |> Talan.BloomFilter.put("Barna Kovacs")
iex> b |> Talan.BloomFilter.member?("Barna Kovacs")
true

@spec merge([t(), ...]) :: t()

Merges the atomics of multiple %Talan.BloomFilter{} structs into one new struct.

All filters must have the same size and use the same hash functions.

Returns a new %Talan.BloomFilter{} struct whose set bits are the merged set bits of the bloom filters in the list.

Examples

iex> hash_functions = [fn term -> :erlang.phash2(term) end]
iex> b1 = Talan.BloomFilter.new(1000, hash_functions: hash_functions)
iex> b1 |> Talan.BloomFilter.put("GitHub")
iex> b2 = Talan.BloomFilter.new(1000, hash_functions: hash_functions)
iex> b2 |> Talan.BloomFilter.put("Octocat")
:ok
iex> b3 = Talan.BloomFilter.merge([b1, b2])
iex> b3 |> Talan.BloomFilter.member?("GitHub")
true
iex> b3 |> Talan.BloomFilter.member?("Octocat")
true

@spec new(pos_integer(), options()) :: t()

Returns a new %Talan.BloomFilter{} for the desired cardinality.

cardinality is the expected number of unique items. Duplicate items do not count toward the expected cardinality.

Raises ArgumentError if cardinality or any option is invalid.

Options

• :false_positive_probability - a float, defaults to 0.01
• :hash_functions - a list of functions that each accept a term and return a non-negative integer, defaults to randomly seeded Murmur

Examples

iex> bloom_filter = Talan.BloomFilter.new(1_000_000)
iex> bloom_filter |> Talan.BloomFilter.put("Barna Kovacs")
:ok

@spec put(t(), any()) :: :ok

Puts term into bloom_filter, a %Talan.BloomFilter{} struct.

After insertion, member?/2 will always return true for this term.

Returns :ok.

Examples

iex> b = Talan.BloomFilter.new(1000)
iex> b |> Talan.BloomFilter.put("Chris McCord")
:ok
iex> b |> Talan.BloomFilter.put("Jose Valim")
:ok

@spec required_filter_length(pos_integer(), float()) :: pos_integer()

Returns the required bit count given

• cardinality - Number of unique elements that will be inserted
• false_positive_probability - Desired false positive probability of membership

Wikipedia - Bloom filter - Optimal number of hash functions

Examples

iex> Talan.BloomFilter.required_filter_length(10_000, 0.01)
95851

@spec required_hash_function_count(float()) :: pos_integer()

Returns the required number of hash functions for the given false_positive_probability.

Wikipedia - Bloom filter - Optimal number of hash functions

Examples

iex> Talan.BloomFilter.required_hash_function_count(0.01)
7
iex> Talan.BloomFilter.required_hash_function_count(0.001)
10
iex> Talan.BloomFilter.required_hash_function_count(0.0001)
14

@spec serialize(t()) :: binary()

Serializes the Bloom filter into a binary.

This function converts the Bloom filter structure into a binary format, which can be used for storage or transmission.

The binary embeds the filter's hash functions and is only portable to environments running compatible code. It is not a stable interchange format across code upgrades.

Examples

iex> bloom_filter = Talan.BloomFilter.new(1000)
iex> serialized = Talan.BloomFilter.serialize(bloom_filter)
iex> is_binary(serialized)
true