Bloom Filter: Пробний Фільтр для Перевірки Належності до Множини

Масив бітів як заміна множині

Бертон Хауард Блум описав цю структуру в 1970 році як спосіб перевірки наявності елемента в множині без збереження самої множини. Фільтр Блума – це масив з m бітів, усі початково встановлені у 0, плюс k незалежних хеш-функцій. Для вставки елемента хешуйте його k разів і встановлюйте біти, на які вказують ці хеші. Щоб перевірити, чи може бути елемент у множині, хешуйте його так само k разів і перевірте, чи всі k біти встановлені – якщо хоча б один дорівнює 0, то елемент точно ніколи не вставлявся; якщо всі k дорівнюють 1, то ймовірно, елемент є у множині.

Жодного хибного негативу, регульований хибний позитив

Це вся цінність у одній реченні: фільтр Блума ніколи не повідомляє про відсутність вставленого елемента, але з певною ймовірністю може повідомити, що елемент присутній, навіть якщо його ніколи не було вставлено. Хибний позитив виникає, коли несхожі вставки випадково встановлюють усі k біт-позиції нового запиту, лише через хеш-конфлікт. Немає механізму для хибного негативу, оскільки вставка завжди лише встановлює біти і ніколи їх не стирає.

function add(item) {
  for (let i = 0; i < k; i++) bits[hash(item, i) % m] = 1;
}
function mightContain(item) {
  for (let i = 0; i < k; i++)
    if (bits[hash(item, i) % m] === 0) return false;   // definitely not in the set
  return true;                                          // probably in the set
}

Формула хибнопозитивного результату

Після вставки n елементів у масив з m бітами за допомогою k хеш-функцій, ймовірність того, що один із бітів все ще дорівнює 0, становить приблизно e^(-kn/m). Отже, ймовірність того, що запит для елемента, який ніколи не вводився, випадково встановить всі k своїх бітів, становить приблизно (1 - e^(-kn/m))^k. Це вираження мінімізується для заданих m та n, коли k дорівнює (m/n) * натуральному логарифму 2 – приблизно 0,693 хеш-функції на біт бюджету на елемент. Підставляючи цю оптимальну величину назад, отримуємо добре відоме правило, згідно з яким близько 10 бітів на елемент та 7 хеш-функцій дають приблизно 1% хибнопозитивного результату.

Чому варті хибні спрацьовування

Множина хешування, яка зберігає самі елементи, потребуватиме пам’яті пропорційної до кількості та розміру цих елементів. Фільтр Блума ж використовує лише фіксований по розміру бітовий масив, незалежно від того, наскільки великими або складними є елементи, ціною випадкового хибного «можливо». Ця компромісна схема є ідеальною як попередній фільтр перед чимось дорогим: перевірка бази даних, чи може існувати ключ, перш ніж здійснити дорогий зчитування з диска; пропуск веб-краулером URL-адрес, які він, ймовірно, вже відвідував; рішення CDN або маршрутизатора, чи містить кеш, ймовірно, елемент, перш ніж здійснювати мережевий запит; або перевірка правопису, яка перевіряє, чи є слово, ймовірно, дійсним, перед повною перевіркою словника.

Варіанти, які варто знати

Підрахунковий фільтр Блума замінює кожен біт на невеликий лічильник, який збільшується при вставці та зменшується при видаленні, що відновлює підтримку видалення за рахунок декількох разів більшої пам’яті. Фільтр Куку – зберігає короткі відбитки в хеш-таблиці Куку замість окремих бітів, підтримує видалення безпосередньо та при низькому рівні хибнопозитивних результатів використовує менше пам'яті, ніж фільтр Блума для забезпечення однакового гарантованого рівня точності – сучасний стандарт, коли важливе видалення.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Bloom Filter і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.