Як написати фільтр Блума в C ++

Фільтр Блума представляє собою структуру даних, яка може ефективно визначити чи є елемент можливим елементом набору або визначено не відноситься до нього. Ця стаття продемонструє просту реалізацію фільтра Блума в 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.3 МБ і 13 хеш-функції, вставляючи елементи 1.8 МБ взяли приблизно 189 наносекунд для кожного елемента середньої продуктивності ноутбуці.

Оригінал даного посту Ви можете знайти на посилання.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.