Loading...
Searching...
No Matches
bloom_filter.hpp
Go to the documentation of this file.
// SPDX-FileCopyrightText: 2006-2025 Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2025 Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: BSD-3-Clause
#pragma once
#include <seqan3/contrib/sdsl-lite.hpp>
#include <seqan3/core/concept/cereal.hpp>
//Todo: When removing search/dream_index/interleaved_bloom_filter.hpp, the contents of the following header can be
// moved into this file
#include <seqan3/utility/bloom_filter/bloom_filter_strong_types.hpp>
namespace seqan3
{
template <data_layout data_layout_mode_ = data_layout::uncompressed>
class bloom_filter
{
private:
template <data_layout data_layout_mode>
friend class bloom_filter;
using data_type = std::conditional_t<data_layout_mode_ == data_layout::uncompressed,
seqan3::contrib::sdsl::bit_vector,
seqan3::contrib::sdsl::sd_vector<>>;
size_t size_in_bits{};
size_t hash_shift{};
size_t hash_funs{};
data_type data{};
static constexpr std::array<size_t, 5> hash_seeds{13'572'355'802'537'770'549ULL, // 2**64 / (e/2)
13'043'817'825'332'782'213ULL, // 2**64 / sqrt(2)
10'650'232'656'628'343'401ULL, // 2**64 / sqrt(3)
16'499'269'484'942'379'435ULL, // 2**64 / (sqrt(5)/2)
4'893'150'838'803'335'377ULL}; // 2**64 / (3*pi/5)
inline constexpr size_t hash_and_fit(size_t h, size_t const seed) const
{
h *= seed;
h ^= h >> hash_shift; // XOR and shift higher bits into lower bits
h *= 11'400'714'819'323'198'485ULL; // = 2^64 / golden_ration, to expand h to 64 bit range
// Use fastrange (integer modulo without division) if possible.
#ifdef __SIZEOF_INT128__
h = static_cast<uint64_t>((static_cast<__uint128_t>(h) * static_cast<__uint128_t>(size_in_bits)) >> 64);
#else
h %= size_in_bits;
#endif
return h;
}
public:
static constexpr data_layout data_layout_mode = data_layout_mode_;
bloom_filter() = default;
bloom_filter(bloom_filter const &) = default;
bloom_filter & operator=(bloom_filter const &) = default;
bloom_filter(bloom_filter &&) = default;
bloom_filter & operator=(bloom_filter &&) = default;
~bloom_filter() = default;
bloom_filter(seqan3::bin_size size, seqan3::hash_function_count funs = seqan3::hash_function_count{2u})
requires (data_layout_mode == data_layout::uncompressed)
{
size_in_bits = size.get();
hash_funs = funs.get();
if (hash_funs == 0 || hash_funs > 5)
throw std::logic_error{"The number of hash functions must be > 0 and <= 5."};
if (size_in_bits == 0)
throw std::logic_error{"The size of a bloom filter must be > 0."};
hash_shift = std::countl_zero(size_in_bits);
data = seqan3::contrib::sdsl::bit_vector(size_in_bits);
}
bloom_filter(bloom_filter<data_layout::uncompressed> const & bf)
requires (data_layout_mode == data_layout::compressed)
{
std::tie(size_in_bits, hash_shift, hash_funs) = std::tie(bf.size_in_bits, bf.hash_shift, bf.hash_funs);
data = seqan3::contrib::sdsl::sd_vector<>{bf.data};
}
void emplace(size_t const value) noexcept
requires (data_layout_mode == data_layout::uncompressed)
{
for (size_t i = 0; i < hash_funs; ++i)
{
size_t idx = hash_and_fit(value, hash_seeds[i]);
assert(idx < data.size());
data[idx] = 1;
};
}
void reset() noexcept
requires (data_layout_mode == data_layout::uncompressed)
{
seqan3::contrib::sdsl::util::_set_zero_bits(data);
}
bool contains(size_t const value) const noexcept
{
for (size_t i = 0; i < hash_funs; i++)
{
size_t idx = hash_and_fit(value, hash_seeds[i]);
assert(idx < data.size());
if (data[idx] == 0)
return false;
}
return true;
}
template <std::ranges::range value_range_t>
size_t count(value_range_t && values) const noexcept
{
static_assert(std::ranges::input_range<value_range_t>, "The values must model input_range.");
static_assert(std::unsigned_integral<std::ranges::range_value_t<value_range_t>>,
"An individual value must be an unsigned integral.");
size_t result = 0;
for (auto && value : values)
result += contains(value);
return result;
}
size_t hash_function_count() const noexcept
{
return hash_funs;
}
size_t bit_size() const noexcept
{
return size_in_bits;
}
friend bool operator==(bloom_filter const & lhs, bloom_filter const & rhs) noexcept
{
return std::tie(lhs.size_in_bits, lhs.hash_shift, lhs.hash_funs, lhs.data)
== std::tie(rhs.size_in_bits, rhs.hash_shift, rhs.hash_funs, rhs.data);
}
friend bool operator!=(bloom_filter const & lhs, bloom_filter const & rhs) noexcept
{
return !(lhs == rhs);
}
constexpr data_type & raw_data() noexcept
{
return data;
}
constexpr data_type const & raw_data() const noexcept
{
return data;
}
template <cereal_archive archive_t>
void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
{
archive(size_in_bits);
archive(hash_shift);
archive(hash_funs);
archive(data);
}
};
} // namespace seqan3
std::array
bloom_filter_strong_types.hpp
Provides strong types for the (Interleaved) Bloom Filter.
cereal.hpp
Adaptions of concepts from the Cereal library.
seqan3::bloom_filter::operator!=
friend bool operator!=(bloom_filter const &lhs, bloom_filter const &rhs) noexcept
Test for inequality.
Definition bloom_filter.hpp:339
seqan3::bloom_filter::raw_data
constexpr data_type & raw_data() noexcept
Provides direct, unsafe access to the underlying data structure.
Definition bloom_filter.hpp:355
seqan3::bloom_filter::bloom_filter
bloom_filter(bloom_filter &&)=default
Defaulted.
seqan3::bloom_filter::data_layout_mode
static constexpr data_layout data_layout_mode
Indicates whether the Bloom Filter is compressed.
Definition bloom_filter.hpp:136
seqan3::bloom_filter::raw_data
constexpr data_type const & raw_data() const noexcept
Provides direct, unsafe access to the underlying data structure.
Definition bloom_filter.hpp:361
seqan3::bloom_filter::operator=
bloom_filter & operator=(bloom_filter const &)=default
Defaulted.
seqan3::bloom_filter::contains
bool contains(size_t const value) const noexcept
Check whether a value is present in the Bloom Filter.
Definition bloom_filter.hpp:253
seqan3::bloom_filter::bloom_filter
bloom_filter(bloom_filter< data_layout::uncompressed > const &bf)
Construct a compressed Bloom Filter.
Definition bloom_filter.hpp:186
seqan3::bloom_filter::operator==
friend bool operator==(bloom_filter const &lhs, bloom_filter const &rhs) noexcept
Test for equality.
Definition bloom_filter.hpp:328
seqan3::bloom_filter::reset
void reset() noexcept
Remove all values from the Bloom Filter by setting all bits to 0.
Definition bloom_filter.hpp:232
seqan3::bloom_filter::bloom_filter
bloom_filter(bloom_filter const &)=default
Defaulted.
seqan3::bloom_filter::hash_function_count
size_t hash_function_count() const noexcept
Returns the number of hash functions used in the Bloom Filter.
Definition bloom_filter.hpp:306
seqan3::bloom_filter::count
size_t count(value_range_t &&values) const noexcept
Counts the occurrences for all values in a range.
Definition bloom_filter.hpp:285
seqan3::bloom_filter::bloom_filter
bloom_filter()=default
Defaulted.
seqan3::bloom_filter::bit_size
size_t bit_size() const noexcept
Returns the size of the underlying bitvector.
Definition bloom_filter.hpp:314
seqan3::bloom_filter::operator=
bloom_filter & operator=(bloom_filter &&)=default
Defaulted.
seqan3::bloom_filter::emplace
void emplace(size_t const value) noexcept
Inserts a value into the Bloom Filter.
Definition bloom_filter.hpp:209
seqan3::bloom_filter::~bloom_filter
~bloom_filter()=default
Defaulted.
seqan3::bloom_filter::bloom_filter
bloom_filter(seqan3::bin_size size, seqan3::hash_function_count funs=seqan3::hash_function_count{2u})
Construct an uncompressed Bloom Filter.
Definition bloom_filter.hpp:160
std::conditional_t
seqan3::data_layout
data_layout
Determines if the Interleaved Bloom Filter is compressed.
Definition bloom_filter_strong_types.hpp:23
seqan3::uncompressed
@ uncompressed
The Interleaved Bloom Filter is uncompressed.
Definition bloom_filter_strong_types.hpp:24
seqan3::compressed
@ compressed
The Interleaved Bloom Filter is compressed.
Definition bloom_filter_strong_types.hpp:25
std::logic_error
seqan3
The main SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
seqan3::bin_size
A strong type that represents the number of bits for each bin in the seqan3::interleaved_bloom_filter...
Definition bloom_filter_strong_types.hpp:38
seqan3::hash_function_count
A strong type that represents the number of hash functions for the seqan3::interleaved_bloom_filter.
Definition bloom_filter_strong_types.hpp:45
seqan3::seed
strong_type for seed.
Definition minimiser_hash.hpp:22
std::tie
T tie(T... args)
Hide me