В чем преимущество использования фильтров цветения?

Из Википедии:

Фильтры Блума имеют сильное преимущество в пространстве перед другими структурами данных для представления наборов, таких как самобалансирующиеся деревья двоичного поиска, попытки, хэш-таблицы или простые массивы или связанные списки записей. Большинство из них требует хранения как минимум самих элементов данных, что может потребовать от небольшого количества бит для небольших целых чисел до произвольного количества бит, например для строк (попытки являются исключением, поскольку они могут совместно использовать хранилище между элементы с одинаковыми префиксами). Связанные структуры несут дополнительные линейные накладные расходы на пространство для указателей. С другой стороны, фильтр Блума с ошибкой 1% и оптимальным значением k требует всего около 9,6 бит на элемент - независимо от размера элементов. Это преимущество частично объясняется его компактностью, унаследованной от массивов, а частично - его вероятностной природой. Если 1% ложных срабатываний кажется слишком высоким, каждый раз, когда мы добавляем около 4,8 бита на элемент, мы уменьшаем его в десять раз.

Для меня это довольно ясно.

Фильтр Блума не хранит сами элементы, это ключевой момент. Вы не используете фильтр цветения для проверки наличия элемента, вы используете его, чтобы проверить, действительно ли он отсутствует, поскольку он гарантирует отсутствие ложноотрицательных результатов. Это позволяет вам не выполнять дополнительную работу для элементов, которых нет в наборе (например, ввода-вывода диска для их поиска).

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

Итак, пример использования может быть таким:

У вас много данных на диске - вы решаете, какую границу ошибки вы хотите (например, 1%), которая предписывает значение m. Затем определяется оптимальный k (по формуле, приведенной в статье). Вы заполняете свой фильтр из этих привязанных к диску данных один раз.

Теперь у вас есть фильтр в ОЗУ. Когда вам нужно обработать какой-либо элемент, вы запрашиваете свой фильтр, чтобы узнать, есть ли у него шансы на существование в вашем наборе данных. Если этого не произойдет, никаких дополнительных действий не будет. Нет чтения с диска и т. Д. (Что вам пришлось бы сделать, если бы это был хэш, дерево и т. Д.).

В противном случае, если фильтр говорит: «Да, это там», вероятность того, что это неверно, составляет 1%, поэтому вы проделаете необходимую работу, чтобы выяснить это. В 99% случаев он действительно будет там, поэтому работа не была напрасной.

Алекс объяснил это довольно хорошо. Для тех, кто еще не совсем понял это, надеюсь, этот пример поможет вам понять:

Допустим, я работаю в Google в команде Chrome и хочу добавить в браузер функцию, которая уведомляет пользователя, если введенный им URL-адрес является вредоносным. Итак, у меня есть набор данных из примерно 1 миллиона вредоносных URL-адресов, размер этого файла составляет около 25 МБ. Поскольку размер довольно большой (большой по сравнению с размером самого браузера), я храню эти данные на удаленном сервере.

Случай 1: я использую хеш-функцию с хеш-таблицей. Я выбираю эффективную функцию хеширования и пропускаю все 1 миллион URL-адресов через функцию хеширования, чтобы получить хеш-ключи. Затем я создаю хеш-таблицу (массив), где хеш-ключ дает мне индекс для размещения этого URL-адреса. Итак, теперь, когда я хэшировал и заполнил хеш-таблицу, я проверяю ее размер. Я сохранил все 1 миллион URL-адресов в хеш-таблице вместе с их ключами. Так что размер не менее 25 МБ. Эта хеш-таблица из-за своего размера будет храниться на удаленном сервере. Когда пользователь приходит и вводит URL-адрес в адресную строку, мне нужно проверить, не является ли он вредоносным. Таким образом, я пропускаю URL-адрес через хеш-функцию (это может делать сам браузер) и получаю хеш-ключ для этого URL-адреса. Теперь мне нужно сделать запрос на мой удаленный сервер с этим хеш-ключом, чтобы проверить, совпадает ли конкретный URL-адрес в моей хэш-таблице с этим конкретным ключом с тем, что ввел пользователь. Если да, то это злонамеренно, если нет, то не злонамеренно. Таким образом, каждый раз, когда пользователь вводит URL-адрес, должен выполняться запрос к удаленному серверу, чтобы проверить, является ли это вредоносным URL-адресом. Это займет много времени и, следовательно, замедлит работу моего браузера.

Случай 2: я использую фильтр цветения. Весь список из 1 миллиона URL-адресов пропускается через фильтр Блума с использованием нескольких хэш-функций, и соответствующие позиции помечаются как 1 в огромном массиве нулей. Допустим, мы хотим получить 1% ложных срабатываний, используя калькулятор фильтра Блума (http://hur.st/bloomfilter?n=1000000&p=0.01), мы получаем размер требуемого фильтра Блума всего 1,13 МБ. Этот небольшой размер ожидается, поскольку, хотя размер массива огромен, мы храним только единицы или нули, а не URL-адреса, как в случае с хеш-таблицей. Этот массив можно рассматривать как битовый массив. То есть, поскольку у нас есть только два значения 1 и 0, мы можем установить отдельные биты вместо байтов. Это уменьшит занимаемое пространство в 8 раз. Этот фильтр цветения 1,13 МБ, из-за своего небольшого размера, может быть сохранен в самом веб-браузере !! Таким образом, когда пользователь приходит и вводит URL-адрес, мы просто применяем необходимые хэш-функции (в самом браузере) и проверяем все позиции в фильтре цветения (который хранится в браузере). Значение 0 в любой из позиций говорит нам, что этот URL-адрес ОПРЕДЕЛЕННО НЕ входит в список вредоносных URL-адресов, и пользователь может свободно действовать. Таким образом, мы не обращались к серверу и, следовательно, экономили время. Значение 1 говорит нам, что URL МОЖЕТ быть в списке вредоносных URL. В этих случаях мы вызываем удаленный сервер, и там мы можем использовать другую хеш-функцию с некоторой хеш-таблицей, как в первом случае, чтобы получить и проверить, действительно ли присутствует URL-адрес. Поскольку в большинстве случаев URL-адрес не может быть вредоносным, фильтр small bloom в браузере определяет это и, следовательно, экономит время, избегая вызовов удаленного сервера. Только в некоторых случаях, если фильтр bloom сообщает нам, что URL-адрес МОЖЕТ быть вредоносным, только в этих случаях мы обращаемся к серверу. Это «МОЖЕТ» верно на 99%.

Таким образом, используя небольшой фильтр цветения в браузере, мы сэкономили много времени, поскольку нам не нужно выполнять запросы к серверу для каждого введенного URL.

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

изменить:

Я реализовал фильтр цветения для задачи тестирования вредоносных URL-адресов в Python. Код можно найти здесь - https://github.com/tarunsharma1/Bloom-Filter код очень прост для понимания, а подробное описание содержится в файле readme.

Я начну с объяснения того, что такое фильтр цветения, что он может и не может делать, зачем он нам нужен, покажу интуитивно понятное описание того, как он работает, а затем приведу несколько примеров, когда они могут быть полезны.

Итак, стандартный фильтр цветения - это вероятностная структура данных, которая может ^*:

• добавить элемент в набор
• проверьте, входит ли элемент в набор, сообщив definitely not in the set или possibly in the set

Это possibly in the set именно поэтому оно называется вероятностным. Используя умные слова, это означает, что возможны ложные срабатывания (могут быть случаи, когда он ошибочно полагает, что элемент положительный), но ложноотрицательные невозможны.

Но это не может ^*:

• удалить предмет из набора
• дать вам список всех элементов, которые в настоящее время находятся в вашем наборе

^* _{Этот набор банок / нельзя для базового фильтра цветения. Поскольку это полезная структура данных, созданная давным-давно, люди нашли способ дополнить его другими полезные функции.}

Но подождите минутку: мы уже знаем структуру данных, которая может ответить на все это без расплывчатого «возможного», а также без всех ограничений (не может удалить, не может показать все). И это называется набором. И вот главное преимущество фильтра Блума: он эффективен по пространству и постоянен.

Это означает, что неважно, сколько элементов мы там храним, пространство будет одинаковым. Да, фильтр цветения с 10^6 элементами (бесполезный фильтр цветения) займет столько же места, что и фильтр цветения с 10^20 элементами, и то же пространство, что и фильтр цветения с 0 элементами. Так сколько места это займет? Вам решать (но есть обмен: чем больше у вас элементов, тем более неопределенным вы будете отвечать possible in the set.

Еще одна крутая вещь - это пространственная постоянная. Когда вы сохраняете данные в набор, вы должны фактически сохранить эти данные. Так что, если вы храните this long string in the set, вам нужно использовать как минимум 27 байт пространства. Но для ошибки 1% и оптимального значения k ^** вам понадобится ~ 9,6 бит (‹2 байта) на любой элемент (будь то короткий int или огромная стена текста) .

Другое свойство состоит в том, что все операции выполняются за постоянное время, что абсолютно не то же самое, что амортизированное постоянное время в случае наборов (помните, что если набор имеет коллизии, он может ухудшиться за O(n) раз).

^** _{k - значение хэш-функций, используемых в фильтре Блума}

Я не буду описывать, как работают фильтры цветения (статья в Википедии очень хорошо объясняет все). Здесь я лишь вкратце расскажу об основах.

• вы инициируете пустой битовый массив длиной m
• вы выбираете k разные хэш-функции (чем независимее, тем лучше)
• если вы хотите добавить элемент, вы вычисляете все k хеши этого значения и устанавливаете соответствующие биты в 1
• если вы хотите проверить, существует ли элемент, вы также вычисляете все k хэшей, и если хотя бы один из них не установлен, его наверняка нет в наборе. В противном случае это может быть в комплекте.

Даже этого описания достаточно, чтобы понять, почему мы не можем быть уверены (вы можете получить все биты из различных других значений). Вот очень хорошая визуализация того, как это работает.

Итак, когда могут быть полезны фильтры цветения? Короткий ответ: везде, где допустимы ложные срабатывания и где вы хотели бы проверить, есть ли что-то в наборе, но даже если это не так, это может быть первой линией защиты, позволяющей исключить дорогостоящие звонки проверяющим.

Вот список более конкретных описаний:

• стандартный пример вредоносных веб-сайтов и браузера описывается практически в любом месте, где люди говорят о фильтрах цветения.
• является слабым паролем: вместо того, чтобы иметь огромный набор всех возможных слабых паролей, вы можете просто проверить, действительно ли пароль не слабый, с гораздо меньшим фильтром Блума
• если у вас есть список статей и список пользователей, вы можете использовать фильтр Блума, чтобы показать статьи пользователей, которые они не читали. Интересно то, что у вас может быть только один фильтр (вы проверяете, есть ли там комбинация user_id + article_id)
• биткойн использует фильтр Блума для синхронизации кошелька
• Веб-серверы Akamai используют фильтры Блума, чтобы не допустить сохранения в его дисковых кэшах «чудеса одного удара». Одноразовые чудеса - это веб-объекты, запрошенные пользователями только один раз, что, как обнаружил Akamai, применимо почти к трем четвертям их инфраструктуры кэширования. Использование фильтра Блума для обнаружения второго запроса веб-объекта и кэширование этого объекта только по его второму запросу предотвращает попадание чудес с одним попаданием в дисковый кеш, значительно снижая нагрузку на диск и увеличивая частоту попаданий в дисковый кеш (взято из примеров в фильтре Блума. статья в вики)

Фильтры Блума весьма полезны в биоинформатике. Они могут занимать больше места по сравнению с использованием обычного хеша, особенно когда размер строк, с которыми вы работаете, может составлять сотни миллионов букв с очень маленьким алфавитом, например {A, G, T, C}. Обычно они используются для оценки наличия или отсутствия определенного k-мер в геноме. Пример того, что используется для чего-то релевантного, здесь.

РЕДАКТИРОВАТЬ:

Множественные хеш-функции используются для минимизации ложных срабатываний. Есть надежда, что между всеми k-хэш-функциями каждое значение будет иметь уникальную подпись в битовом массиве по сравнению с любым другим возможным значением. Однако ложные срабатывания действительно существуют, но их можно свести к минимуму до приемлемого уровня. Используя этот метод, вы хэшируете элементы независимо от их размера. При их поиске вы используете каждую хеш-функцию и проверяете, все ли их битовые значения равны 1.

Сравните это с геномом человека, где увеличение размера элемента значительно увеличивает размер хеш-таблицы (размер таблицы составляет 4 * 4 ^k). Предполагается, что вы кодируете элементы, используя 2 бита на букву.

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