Фільтр Блума
Фільтр Блума - це просторово-ефективна ймовірна структура даних, створена для перевірки наявності елемента у множині. Він спроектований неймовірно швидким за мінімального використання пам'яті ціною потенційних помилкових спрацьовувань. Існує можливість отримати хибнопозитивне спрацьовування (елемента в безлічі немає, але структура даних повідомляє, що він є), але не хибнонегативне. Іншими словами, черга повертає або "можливо в наборі", або "певно не у наборі". Фільтр Блума може використовувати будь-який обсяг пам'яті, проте чим він більший, тим менша вірогідність помилкового спрацьовування.
Блум запропонував цю техніку для застосування в областях, де кількість вихідних даних потребувала б непрактично багато пам'яті, у разі застосування умовно безпомилкових технік хешування.
Опис алгоритму
Порожній фільтр Блума представлений бітовим масивом з m бітів, всі біти якого обнулені. Має бути визначено k
незалежних хеш-функцій, що відображають кожен елемент множини в одну з m позицій у масиві, генеруючи однакове
випадковий розподіл. Зазвичай k задана константою, яка набагато менше m і пропорційна
кількості елементів, що додаються; точний вибір k та постійної пропорційності m визначаються рівнем хибних
спрацьовувань фільтра.
Ось приклад Блум фільтра, що представляє набір {x, y, z}. Кольорові стрілки показують позиції в бітовому масиві,
яким прив'язаний кожен елемент набору. Елемент w не в наборі {x, y, z}, тому що він прив'язаний до позиції в бітовому
масиві, що дорівнює 0. Для цієї форми, m = 18, а k = 3.
Фільтр Блума є бітовий масив з m біт. Спочатку, коли структура даних зберігає порожню множину, всі
m біт обнулені. Користувач повинен визначити k незалежних хеш-функцій h1, …, hk,
що відображають кожен елемент в одну з m позицій бітового масиву досить рівномірним чином.
Для додавання елемента e необхідно записати одиниці на кожну з позицій h1(e), …, hk(e)
бітового масиву.
Для перевірки приналежності елемента e до безлічі елементів, що зберігаються, необхідно перевірити стан бітів
h1(e), …, hk(e). Якщо хоча б один з них дорівнює нулю, елемент не може належати множині
(інакше при його додаванні всі ці біти були встановлені). Якщо вони рівні одиниці, то структура даних повідомляє,
що е належить безлічі. При цьому може виникнути дві ситуації: або елемент дійсно належить множині,
або всі ці біти виявилися встановлені випадково при додаванні інших елементів, що і є джерелом помилкових
спрацьовувань у цій структурі даних.
Застосування
Фільтр Блума може бути використаний для блогів. Якщо мета полягає в тому, щоб показати читачам лише ті статті, які вони ще не бачили, фільтр блуму ідеальний. Він може містити значення, що хешуються, відповідні статті. Після того, як користувач прочитав кілька статей, вони можуть бути поміщені у фільтр. Наступного разу, коли користувач відвідає сайт, ці статті можуть бути вилучені з результатів за допомогою фільтра.
Деякі статті неминуче будуть відфільтровані помилково, але ціна прийнятна. Те, що користувач не побачить дещо статей цілком прийнятно, беручи до уваги той факт, що йому завжди показуються інші нові статті при кожному новому відвідуванні.