Bloom Filters — Введение и реализация Python

31.12.2019GBlog, Python, Технический Scripter

Предположим, вы создаете учетную запись в Geekbook, хотите ввести классное имя пользователя, вы ввели его и получили сообщение «Имя пользователя уже занято». Вы добавили свою дату рождения вместе с именем пользователя, но все равно не повезло. Теперь вы также добавили номер своего университетского списка и получили «Имя пользователя уже занято». Это действительно расстраивает, не так ли?
Но вы когда-нибудь задумывались, как быстро Geekbook проверяет доступность имени пользователя, выполняя поиск по миллионам зарегистрированных пользователей. Есть много способов сделать эту работу —

Линейный поиск : плохая идея!
Бинарный поиск : сохраняйте все имена пользователей в алфавитном порядке и сравнивайте введенное имя пользователя со средним в списке. Если оно совпадает, то используется имя пользователя, в противном случае выясняется, будет ли введенное имя пользователя идти до или после среднего и, если оно будет после, пренебречь всеми именами пользователей до середины (включительно). Теперь ищите после среднего и повторяйте этот процесс, пока не получите совпадение или конец поиска без совпадения. Этот метод лучше и перспективнее, но все же требует нескольких шагов.
Но должно быть что-то лучше!

Bloom Filter — это структура данных, которая может выполнять эту работу.

Для понимания фильтров Блума, вы должны знать, что такое хэширование . Хеш-функция принимает входные данные и выводит уникальный идентификатор фиксированной длины, который используется для идентификации входных данных.

Что такое Bloom Filter?

Фильтр Блума — это компактная вероятностная структура данных, которая используется для проверки того, является ли элемент членом набора. Например, проверка доступности имени пользователя задается проблемой членства, где набор представляет собой список всех зарегистрированных имен пользователей. Цена, которую мы платим за эффективность, заключается в том, что она носит вероятностный характер, что означает, что могут быть некоторые ложноположительные результаты. Ложное положительное значение может означать , что данное имя пользователя уже занято, но на самом деле это не так.

Интересные свойства Bloom Filters

В отличие от стандартной хеш-таблицы, фильтр Блума фиксированного размера может представлять набор с произвольно большим количеством элементов.
Добавление элемента никогда не завершится неудачей. Однако частота ложных срабатываний постоянно увеличивается по мере добавления элементов, пока все биты в фильтре не будут установлены в 1, после чего все запросы дают положительный результат.
Фильтры Блума никогда не генерируют ложно-отрицательный результат, т. Е. Сообщают вам, что имя пользователя не существует, когда оно действительно существует.
Удаление элементов из фильтра невозможно, потому что, если мы удаляем один элемент путем очистки битов по индексам, сгенерированным k хэш-функциями, это может привести к удалению нескольких других элементов. Пример — если мы удалим «geeks» (в приведенном ниже примере), очистив биты в 1, 4 и 7, мы можем в конечном итоге удалить также «nerd», поскольку бит с индексом 4 становится равным 0, а фильтр Bloom утверждает, что «nerd» не является настоящее время.

Работа фильтра Блума

Пустой фильтр Блума — это битовый массив из m битов, все установлены в ноль, например:

Нам нужно k количество хеш-функций для вычисления хешей для данного входа. Когда мы хотим добавить элемент в фильтр, устанавливаются биты при k индексах h1 (x), h2 (x),… hk (x), где индексы рассчитываются с использованием хеш-функций.
Пример. Предположим, что мы хотим ввести «гиков» в фильтр, мы используем 3 хеш-функции и битовый массив длиной 10, изначально все они установлены в 0. Сначала мы вычислим хэши следующим образом:

h1(“geeks”) % 10 = 1
h2(“geeks”) % 10 = 4
h3(“geeks”) % 10 = 7

Примечание: эти результаты являются случайными только для объяснения.
Теперь мы установим биты на индексы 1, 4 и 7 на 1

Мы снова хотим ввести «ботаник», так же мы будем вычислять хэши

h1(“nerd”) % 10 = 3
h2(“nerd”) % 10 = 5
h3(“nerd”) % 10 = 4

Установите биты в индексах 3, 5 и 4 в 1

Теперь, если мы хотим проверить, есть ли «гики» в фильтре или нет. Мы сделаем тот же процесс, но на этот раз в обратном порядке. Мы вычисляем соответствующие хэши, используя h1, h2 и h3, и проверяем, установлены ли все эти индексы в 1 в битовом массиве. Если все биты установлены, то мы можем сказать, что «гики», вероятно, присутствуют . Если какой-либо из битов этих индексов равен 0, то «гиков» определенно нет .

Ложный позитив в фильтрах Блума

Вопрос в том, почему мы сказали «вероятно, присутствует» , почему эта неопределенность. Давайте разберемся с этим на примере. Предположим, мы хотим проверить, присутствует «кошка» или нет. Мы будем вычислять хэши, используя h1, h2 и h3

h1(“cat”) % 10 = 1
h2(“cat”) % 10 = 3
h3(“cat”) % 10 = 7

Если мы проверим битовый массив, биты этих индексов будут установлены в 1, но мы знаем, что «cat» никогда не добавлялся в фильтр. Бит по индексам 1 и 7 был установлен, когда мы добавили «гиков», а бит 3 был установлен, мы добавили «ботаник».

Таким образом, поскольку биты в вычисленных индексах уже установлены каким-либо другим элементом, фильтр Блума ошибочно утверждает, что присутствует «кот» и генерирует ложноположительный результат. В зависимости от приложения, это может быть огромным недостатком или относительно хорошо.

Мы можем контролировать вероятность получения ложного срабатывания, контролируя размер фильтра Блума. Больше места означает меньше ложных срабатываний. Если мы хотим уменьшить вероятность ложноположительного результата, мы должны использовать большее количество хеш-функций и больший массив битов. Это добавило бы задержку в дополнение к пункту и проверке членства.

Вероятность ложной положительности: Пусть m будет размером битового массива, k будет числом хеш-функций и n будет числом ожидаемых элементов, которые будут вставлены в фильтр, тогда вероятность ложноположительного значения p можно рассчитать как:

Размер битового массива: если ожидаемое количество элементов n известно и желаемая вероятность ложного положительного результата равна p, то размер битового массива m можно рассчитать как:

Оптимальное количество хеш-функций: количество хеш-функций k должно быть положительным целым числом. Если m — это размер битового массива, а n — количество элементов, которые нужно вставить, то k можно рассчитать как:

Космическая эффективность

Если мы хотим , чтобы хранить большой список элементов в наборе для целей членства набора, мы можем хранить его в HashMap , пытается или простой массив или связанный список . Все эти методы требуют хранения самого элемента, что не очень эффективно для памяти. Например, если мы хотим сохранить «гиков» в hashmap, мы должны сохранить фактическую строку «гиков» в виде пары «ключ-значение» {some_key: «geeks»}.
Фильтры Блума не хранят элемент данных вообще. Как мы уже видели, они используют битовый массив, который допускает коллизию хешей. Без столкновения хэшей это не было бы компактно.

Выбор хеш-функции

Хеш-функция, используемая в фильтрах Блума, должна быть независимой и равномерно распределенной. Они должны быть максимально быстрыми. Быстрые простые некриптографические хеши, которые достаточно независимы, включают ропот , ряд хэш-функций FNV и хеш-функции Дженкинса .
Генерация хэша является основной операцией в фильтрах Блума. Криптографические хеш-функции обеспечивают стабильность и гарантию, но дороги в расчете. С увеличением числа хеш-функций k фильтр Блума становится медленным. Несмотря на то, что некриптографические хеш-функции не гарантируют, а обеспечивают значительное улучшение производительности.

Базовая реализация класса Bloom Filter в Python3. Сохранить как bloomfilter.py

# Python 3 программа для сборки Bloom Filter
# Сначала установите mmh3 и сторонний модуль bitarray
# pip install mmh3
# pip install bitarray

import math

import mmh3

from bitarray import bitarray

class BloomFilter(object):

«»»

Класс для фильтра Блума, использующий хэш-функцию murmur3

«»»

def __init__(self, items_count,fp_prob):

«»»

items_count: int

Количество элементов, которые предполагается сохранить в фильтре Блума

fp_prob: float

Ложная положительная вероятность в десятичном виде

«»»

# Ложная вероятность в десятичном виде

self.fp_prob = fp_prob

# Размер битового массива для использования

self.size = self.get_size(items_count,fp_prob)

# количество хеш-функций для использования

self.hash_count = self.get_hash_count(self.size,items_count)

# Битовый массив заданного размера

self.bit_array = bitarray(self.size)

# инициализировать все биты как 0

self.bit_array.setall(0)

def add(self, item):

«»»

Добавить элемент в фильтр

«»»

digests = []

for i in range(self.hash_count):

# создать дайджест для данного элемента.

# Я работаю в качестве семени для функции mmh3.hash ()

# С другим семенем, созданный дайджест отличается

digest = mmh3.hash(item,i) % self.size

digests.append(digest)

# установить бит True в bit_array

self.bit_array[digest] = True

def check(self, item):

«»»

Проверить наличие элемента в фильтре

«»»

for i in range(self.hash_count):

digest = mmh3.hash(item,i) % self.size

if self.bit_array[digest] == False:

# если бит имеет значение False, его нет

# в фильтре

# иначе есть вероятность что оно существует

return False

return True

@classmethod

def get_size(self,n,p):

«»»

Вернуть размер битового массива (м) для использования с помощью

следующая формула

m = - (n * lg (p)) / (lg (2) ^ 2)

n: int

количество элементов, которые предполагается сохранить в фильтре

р: плавать

Ложная положительная вероятность в десятичном виде

«»»

m = -(n * math.log(p))/(math.log(2)**2)

return int(m)

@classmethod

def get_hash_count(self, m, n):

«»»

Вернуть хеш-функцию (k) для использования, используя

следующая формула

k = (м / н) * LG (2)

m: int

размер битового массива

n: int

количество элементов, которые предполагается сохранить в фильтре

«»»

k = (m/n) * math.log(2)

return int(k)

Давайте проверим фильтр Блума. Сохраните этот файл как bloom_test.py

from bloomfilter import BloomFilter

from random import shuffle

n = 20 # нет элементов для добавления

p = 0.05 # ложная вероятность

bloomf = BloomFilter(n,p)

print("Size of bit array:{}".format(bloomf.size))

print("False positive Probability:{}".format(bloomf.fp_prob))

print("Number of hash functions:{}".format(bloomf.hash_count))

# слов, которые будут добавлены

word_present = ['abound','abounds','abundance','abundant','accessable',

'bloom','blossom','bolster','bonny','bonus','bonuses',

'coherent','cohesive','colorful','comely','comfort',

'gems','generosity','generous','generously','genial']

# слово не добавлено

word_absent = ['bluff','cheater','hate','war','humanity',

'racism','hurt','nuke','gloomy','facebook',

'geeksforgeeks','twitter']

for item in word_present:

bloomf.add(item)

shuffle(word_present)
shuffle(word_absent)

test_words = word_present[:10] + word_absent

shuffle(test_words)

for word in test_words:

if bloomf.check(word):

if word in word_absent:

print("'{}' is a false positive!".format(word))

else:

print("'{}' is probably present!".format(word))

else:

print("'{}' is definitely not present!".format(word))

Выход

Size of bit array:124
False positive Probability:0.05
Number of hash functions:4
'war' is definitely not present!
'gloomy' is definitely not present!
'humanity' is definitely not present!
'abundant' is probably present!
'bloom' is probably present!
'coherent' is probably present!
'cohesive' is probably present!
'bluff' is definitely not present!
'bolster' is probably present!
'hate' is definitely not present!
'racism' is definitely not present!
'bonus' is probably present!
'abounds' is probably present!
'genial' is probably present!
'geeksforgeeks' is definitely not present!
'nuke' is definitely not present!
'hurt' is definitely not present!
'twitter' is a false positive!
'cheater' is definitely not present!
'generosity' is probably present!
'facebook' is definitely not present!
'abundance' is probably present!

Применение фильтров Блума

Средний использует фильтры Блума для рекомендации пользователям постов путем фильтрации постов, которые просматривал пользователь.
Quora внедрила общий фильтр Блума в бэкэнд-канал, чтобы отфильтровать истории, которые люди видели раньше.
В веб-браузере Google Chrome использовался фильтр Блума для выявления вредоносных URL-адресов.
Google BigTable, Apache HBase и Apache Cassandra, а также Postgresql используют фильтры Блума, чтобы уменьшить количество обращений к диску для несуществующих строк или столбцов.

Ссылки

Эта статья предоставлена Атулом Кумаром . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Bloom Filters — Введение и реализация Python

0.00 (0%) 0 votes