Фильтр Блума представляет собой структуру данных, которая может эффективно определить является ли элемент возможным элементом набора или определенно не относится к нему. Эта статья продемонстрирует простую реализацию фильтра Блума в C++.
Интерфейс
Давайте сначала определим интерфейс данного фильтра. Можно выделить три основные функции:
- Конструктор
- Функция, чтобы добавить элемент к фильтру Блума
- Функция для запроса относится ли элемент частью фильтра Блума
Несколько задействованных переменных, включая небольшое количество векторов, также содержат состояние фильтра.
#include <vector>
struct BloomFilter {
BloomFilter(uint64_t size, uint8_t numHashes);
void add(const uint8_t *data, std::size_t len);
bool possiblyContains(const uint8_t *data, std::size_t len) const;
private:
uint64_t m_size;
uint8_t m_numHashes;
std::vector<bool> m_bits;
};
Стоит отметить, что std::vector является намного более эффективной специализацией std::vector, требует только один бит на элемент (в отличие от одного байта в типичных реализациях).
Можно обработать эту структуру по шаблону, как расширение. Вместо жесткого кодирования ключевых типов и хеш-функций, мы можем обработать класс по шаблону с чем-то подобным:
template< class Key, class Hash = std::hash<Key> >
struct BloomFilter {
...
};
Это позволит фильтру Блума быть обобщенным для более сложных типов данных.
Параметры фильтра Блума
Есть два параметра для построения фильтра Блума:
- Размер фильтра в битах
- Число хэш-функций для использования
Мы можем вычислить ложный положительный коэффициент ошибок — n, на основе размера фильтра — m, числа хэш-функций — K и число вложенных элементов -N, с помощью формулы:
Эта формула не очень полезна в таком виде. Но нам нужно знать насколько большой фильтр должен быть и сколько хеш-функций понадобится, чтобы использовать, учитывая предполагаемое количество элементов набора и коэффициент ошибок. Есть два уравнения, которые мы можем использовать для расчета этих параметров:
Реализация
Вы можете задаться вопросом, как же реализовать kk хеш-функции; двойное хеширование может использоваться, чтобы генерировать kk значения хэш-функции, не влияя на вероятность ложно-положительного результата! Такой результат можно получить используя формулу, где i — ординал, м — размер фильтра Блума и x — значение, которое будет хешировано:
Для начала нужно написать конструктор. Он просто записывает параметры масштабирования и битовый массив.
#include "BloomFilter.h"
#include "MurmurHash3.h"
BloomFilter::BloomFilter(uint64_t size, uint8_t numHashes)
: m_size(size),
m_numHashes(numHashes) {
m_bits.resize(size);
}
Далее давайте напишем функцию для вычисления 128 — битного хэша данного элемента. В данной реализации используется MurmurHash3, 128 бит хэш — функция, которая имеет хорошие компромиссы между производительностью, распределение, потоковым поведением и сопротивлением противоречиям. Поскольку эта функция генерирует 128 бит хэш и нам нужно 2х64 битные хэши, мы можем разделить возвращенный хэш пополам, чтобы получить хэшa(x) хэшb(x).
std::array<uint64_t, 2> hash(const uint8_t *data,
std::size_t len) {
std::array<uint64_t, 2> hashValue;
MurmurHash3_x64_128(data, len, 0, hashValue.data());
return hashValue;
}
Теперь, когда у нас есть хэш-значения, нужно написать функцию, чтобы вернуть выходной сигнал n хэш-функции.
inline uint64_t nthHash(uint8_t n,
uint64_t hashA,
uint64_t hashB,
uint64_t filterSize) {
return (hashA + n * hashB) % filterSize;
}
Все, что осталось сделать — это написать функции для набора контрольных битов для заданных элементов.
void BloomFilter::add(const uint8_t *data, std::size_t len) {
auto hashValues = hash(data, len);
for (int n = 0; n < m_numHashes; n++) {
m_bits[nthHash(n, hashValues[0], hashValues[1], m_size)] = true;
}
}
bool BloomFilter::possiblyContains(const uint8_t *data, std::size_t len) const {
auto hashValues = hash(data, len);
for (int n = 0; n < m_numHashes; n++) {
if (!m_bits[nthHash(n, hashValues[0], hashValues[1], m_size)]) {
return false;
}
}
return true;
}
Результаты
С помощью фильтра Блума 4.3MБ и 13 хэш-функции, вставляя элементы 1.8МБ приняли примерно 189 наносекунд для каждого элемента на средней производительности ноутбуке.
Оригинал данного поста Вы можете найти по ссылке.
Автор: ua-hosting.company