Фільтр Блума

Фільтр Блума (англ. Bloom filter) — заощадлива до пам'яті ймовірнісна структура даних, призначена для перевірки приналежності елементів до множини. Запропонована Бартоном Говардом Блумом (англ. Burton Howard Bloom) в 1970 році.

Допускає помилкові спрацювання, але пропуск події неможливий, тому фільтр Блума має 100 % потужність. Алгоритм дозволяє перевірити або «ймовірну приналежність до множини», або «точну не приналежність». Можна додавати нові елементи до множини, але не можна їх видаляти (хоча цю проблему можна вирішити «рахуючим» фільтром). Чим більше елементів у множині, тим вища ймовірність помилкового спрацювання.

Блум запропонував цей алгоритм для випадків, коли необхідно обробляти таку кількість даних, що звичайні алгоритми хешування потребуватимуть понад міру пам'яті. Як приклад, він навів алгоритм автоматичного перенесення слів зі словником 500 тисяч слів, 90 % яких підпадають під прості правила розбиття, а решта 10 % потребує повільного доступу до жорсткого диску для пошуку конкретних шаблонів розбиття. За умови достатнього обсягу оперативної пам'яті, звичайне хешування позбавило би потреби в зайвих зверненнях до жорсткого диску. Проте, якщо обсяг оперативної пам'яті обмежений, то фільтр Блума дозволяє позбутись більшості зайвих звернень і, при цьому, використовує менше пам'яті. Наприклад, при використанні лише 15 % пам'яті звичайного хеш-алгоритму, фільтр Блума позбувається 85 % запитів до жорсткого диску, що є варіантом 85-15 правила Парето^[1].

Зазвичай, незалежно від кількості елементів в множині, достатньо не більше 10 біт на елемент для досягнення частки помилкового спрацювання в 1 %^[2].

Опис алгоритму

Приклад фільтру Блума для множини {

x

,

y

,

z

}. Кольорові стрілки вказують на місця в масиві біт, на які відображається кожен елемент. Елемент

w

не належить множині{

x

,

y

,

z

}, оскільки його хеш відображається на позицію з 0. В цій ілюстрації

m

= 18 та

k

= 3.

Порожній фільтр Блума — це масив $m$ біт, що мають значення 0. Також мають бути визначені $k$ хеш-функцій, кожна з яких відображає або хешує елемент множини на одну з $m$ позицій в масиві з рівномірним розподілом ймовірностей.

Аби додати елемент, слід обробити його $k$ хеш-функціями і обчислити $k$ позицій в масиві. Встановити значення біт в цих позиціях рівними 1.

Для перевірки присутності елемента в множині, його слід обробити кожною з $k$ хеш-функцій та отримати $k$ позицій в масиві. Якщо будь-який з біт на цих позиціях дорівнює 0, то елемент гарантовано не перебуває в множині. Якби елемент належав множині, то всі біти отримали б значення 1 при додаванні елемента до множини. Якщо всі біти мають значення 1, тоді або елемент належить множині, або ж біти отримали значення 1 при додаванні інших елементів, що призведе до помилкового спрацювання. Простий фільтр Блума не дозволяє уникнути помилкових спрацювань.

Задача створення $k$ незалежних хеш-функцій може бути заскладною для великих $k$ . Якщо хеш-функція обчислює якісні ключі з широким діапазоном значень, то можливо «розрізати» масив біт на $k$ фрагментів. Як варіант, якщо хеш-функція використовує початкові значення, можна використати $k$ різних початкових значень, або додати ці значення до ключа.

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

Вилучення елементів з фільтра Блума можливо реалізувати з додатковим фільтром, в якому зберігатимуться вилучені елементи. Однак, помилкові спрацювання в додатковому фільтрі стануть пропусками подій в об'єднаному фільтрі, що може бути небажаним. При цьому, повернути раніше видалений елемент неможливо, оскільки цей елемент доведеться видаляти з додаткового фільтру.

Див. також

Примітки

↑ Bloom, Burton H. (1970), Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM, 13 (7): 422—426, doi:10.1145/362686.362692
↑ Bonomi, Flavio; Mitzenmacher, Michael; Panigrahy, Rina; Singh, Sushil; Varghese, George (2006), An Improved Construction for Counting Bloom Filters, Algorithms – ESA 2006, 14th Annual European Symposium (PDF), Lecture Notes in Computer Science, т. 4168, с. 684—695, doi:10.1007/11841036_61, ISBN 978-3-540-38875-3

Література

Jure Leskovec, Anand Rajaraman, Jeffrey D. Ullman (2014). 4.3.2 The Bloom Filter. Mining of Massive Datasets (PDF).

Посилання

Онлайн-калькулятор параметрів фільтра Блума.

Це незавершена стаття про структури даних.
Ви можете допомогти проєкту, виправивши або дописавши її.

[bloom.1970-1] Bloom, Burton H. (1970), Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM, 13 (7): 422—426, doi:10.1145/362686.362692

[bonomi.2006-2] Bonomi, Flavio; Mitzenmacher, Michael; Panigrahy, Rina; Singh, Sushil; Varghese, George (2006), An Improved Construction for Counting Bloom Filters, Algorithms – ESA 2006, 14th Annual European Symposium (PDF), Lecture Notes in Computer Science, т. 4168, с. 684—695, doi:10.1007/11841036_61, ISBN 978-3-540-38875-3

[1]

[2]