В чем преимущество использования фильтров Блума?
Я читаю о фильтрах Блума, и они просто кажутся глупыми. Все, что вы можете сделать с помощью фильтра Блума, вы можете сделать в меньшем пространстве, более эффективно, используя одну хэш-функцию, а не несколько, или это то, что вам кажется. Зачем вам использовать фильтр Блума и чем он полезен?
8 ответов
Из Википедии:
Фильтры Блума обладают значительным пространственным преимуществом перед другими структурами данных для представления наборов, таких как самобалансирующиеся двоичные деревья поиска, попытки, хэш-таблицы или простые массивы или связанные списки записей. Большинство из них требуют хранения как минимум самих элементов данных, что может потребовать от небольшого числа битов для небольших целых чисел до произвольного числа битов, например для строк (попытки являются исключением, поскольку они могут совместно использовать память между элементы с одинаковыми префиксами). Связанные структуры влекут за собой дополнительное линейное пространство для указателей. С другой стороны, для фильтра Блума с ошибкой 1% и оптимальным значением k требуется всего около 9,6 битов на элемент - независимо от размера элементов. Это преимущество частично связано с его компактностью, унаследованной от массивов, и частично с его вероятностным характером. Если 1% ложных срабатываний кажется слишком высоким, каждый раз, когда мы добавляем около 4,8 бит на элемент, мы уменьшаем его в десять раз.
Довольно ясно для меня.
Фильтр Блума не хранит сами элементы, это решающий момент. Вы не используете фильтр Блума, чтобы проверить, присутствует ли элемент, вы используете его, чтобы проверить, действительно ли он присутствует, так как он не гарантирует ложных негативов. Это позволяет вам не выполнять дополнительную работу для элементов, которые не существуют в наборе (например, дисковый ввод-вывод для их поиска).
И все в значительно меньшем пространстве, чем что-то вроде хеш-таблицы (которая, вероятно, будет частично на диске для больших наборов данных). Хотя вы можете использовать фильтр Блума в сочетании со структурой, такой как хеш-таблица, но как только вы убедитесь, что элемент может присутствовать.
Таким образом, пример использования шаблона может быть:
У вас есть много данных на диске - вы решаете, какую погрешность вы хотите (например, 1%), которая предписывает значение m. Затем определяется оптимальное k (по формуле, приведенной в статье). Вы заполняете свой фильтр из этих привязанных к диску данных один раз.
Теперь у вас есть фильтр в оперативной памяти. Когда вам нужно обработать какой-либо элемент, вы запрашиваете фильтр, чтобы определить, существует ли вероятность его существования в вашем наборе данных. Если этого не произойдет, дополнительная работа не выполняется. Нет чтения с диска и т. Д. (Что бы вы сделали, если бы это был хеш или дерево и т. Д.).
В противном случае, если фильтр говорит "Да, он там", есть вероятность 1%, что это неправильно, поэтому вы проделаете необходимую работу, чтобы выяснить это. 99% времени оно действительно будет там, поэтому работа была не напрасной.
Алекс объяснил это довольно хорошо. Для тех, кто еще не совсем понял, надеюсь, этот пример поможет вам понять:
Допустим, я работаю в Google, в команде Chrome, и хочу добавить в браузер функцию, которая уведомляет пользователя, если введенный им URL является вредоносным URL. Итак, у меня есть набор данных из примерно 1 миллиона вредоносных URL-адресов, размер этого файла составляет около 25 МБ. Поскольку размер довольно большой (большой по сравнению с размером самого браузера), я храню эти данные на удаленном сервере.
Случай 1: я использую хеш-функцию с хеш-таблицей. Я выбираю эффективную функцию хеширования и запускаю все 1 миллион URL-адресов через функцию хеширования, чтобы получить хеш-ключи. Затем я создаю хеш-таблицу (массив), где ключ хеша даст мне индекс для размещения этого URL. Итак, теперь, когда я хэшировал и заполнял хеш-таблицу, я проверял ее размер. Я сохранил все 1 миллион URL-адресов в хэш-таблице вместе с их ключами. Таким образом, размер не менее 25 МБ. Эта хеш-таблица, благодаря своему размеру, будет храниться на удаленном сервере. Когда пользователь приходит и вводит URL в адресную строку, мне нужно проверить, не является ли он вредоносным. Таким образом, я запускаю URL через хеш-функцию (сам браузер может сделать это), и я получаю хеш-ключ для этого URL. Теперь мне нужно сделать запрос к моему удаленному серверу с этим хэш-ключом, чтобы проверить, совпадает ли конкретный URL-адрес в моей хеш-таблице с этим конкретным ключом с тем, что ввел пользователь. Если да, то это вредоносно, а если нет, то не является вредоносным. Таким образом, каждый раз, когда пользователь вводит URL-адрес, необходимо сделать запрос на удаленный сервер, чтобы проверить, является ли он вредоносным URL-адресом. Это займет много времени и, следовательно, замедлит работу моего браузера.
Случай 2: я использую фильтр Блума. Весь список из 1 миллиона URL-адресов проходит через фильтр Блума с использованием нескольких хэш-функций, и соответствующие позиции помечаются как 1 в огромном массиве 0. Допустим, мы хотим, чтобы процент ложных срабатываний составлял 1%. Используя калькулятор фильтра Блума ( http://hur.st/bloomfilter?n=1000000&p=0.01), мы получаем требуемый размер фильтра Блума всего лишь 1,13 МБ. Этот небольшой размер ожидается, поскольку, хотя размер массива огромен, мы храним только 1 или 0, а не URL-адреса, как в случае хеш-таблицы. Этот массив можно рассматривать как битовый массив. То есть, поскольку у нас есть только два значения 1 и 0, мы можем установить отдельные биты вместо байтов. Это уменьшит занимаемое пространство в 8 раз. Этот блум-фильтр размером 1,13 МБ, благодаря небольшому размеру, может храниться в самом веб-браузере! Таким образом, когда пользователь приходит и вводит URL, мы просто применяем необходимые хеш-функции (в самом браузере) и проверяем все позиции в фильтре Блума (который хранится в браузере). Значение 0 в любой из позиций говорит нам о том, что этот URL определенно НЕ находится в списке вредоносных URL-адресов, и пользователь может свободно перемещаться. Таким образом, мы не сделали звонок на сервер и, следовательно, сэкономили время. Значение 1 означает, что URL МОЖЕТ быть в списке вредоносных URL. В этих случаях мы делаем вызов на удаленный сервер, и там мы можем использовать некоторую другую хеш-функцию с некоторой хеш-таблицей, как в первом случае, чтобы получить и проверить, присутствует ли URL-адрес. Поскольку в большинстве случаев URL-адрес вряд ли является вредоносным, небольшой фильтр 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 используют фильтры Bloom для предотвращения сохранения "однократных чудес" в своих дисковых кешах. Чудеса одного удара - это веб-объекты, запрошенные пользователями только один раз, что, по мнению Акамаи, применимо почти к трем четвертям их инфраструктуры кэширования. Использование фильтра Блума для обнаружения второго запроса на веб-объект и кэширование этого объекта только по его второму запросу предотвращает попадание чудес в один удар в кэш диска, значительно сокращая нагрузку на диск и увеличивая частоту обращений к кэшу диска (взято из примеров в фильтре Блума статья в вики)
Фильтры Блума весьма полезны в биоинформатике. Они могут быть более компактными по сравнению с использованием обычного хэша, особенно когда размер строк, с которыми вы работаете, может составлять сотни миллионов букв с очень маленьким алфавитом, то есть {A,G,T,C} . Они обычно используются для оценки наличия или отсутствия определенного геномера в геноме. Вот пример того, что используется для чего-то уместного здесь.
РЕДАКТИРОВАТЬ:
Несколько хеш-функций используются для минимизации ложных срабатываний. Есть надежда, что между всеми k-хэш-функциями каждое значение будет иметь уникальную сигнатуру в битовом массиве по сравнению с любым другим возможным значением. Тем не менее, ложные срабатывания существуют, но их можно минимизировать до приемлемого уровня. Используя эту технику, вы хэшируете элементы независимо от их размера. Когда вы ищете их, вы используете каждую хеш-функцию и проверяете, чтобы все их битовые значения были равны 1.
Сравните это с геномом человека, где увеличение размера элемента значительно увеличивает размер хеш-таблицы (размер таблицы 4 * 4k). Это предполагает, что вы кодируете элементы, используя 2 бита / букву.
Если фильтр Блума возвращает, что элемент является членом набора, существует определенная вероятность ложного срабатывания. Если бы для обозначения принадлежности к набору использовалась только одна хеш-функция, вероятность ложного срабатывания была бы выше, чем при использовании нескольких хеш-функций.
Фильтры Блума используются для кеширования, но не везде. Если вы знаете некоторые применения фильтров Блума, вы увидите, насколько они полезны:
Маршрутизаторы
Современные маршрутизаторы имеют ограниченное пространство и, учитывая объем пакетов, которые они обрабатывают в секунду, им требуются чрезвычайно быстрые алгоритмы. Таким образом, они являются идеальным получателем для фильтров Блума для всех тех операций, которые могут справиться с небольшим количеством ошибок. Помимо кеширования, маршрутизаторы часто используют фильтры Блума для отслеживания запрещенных IP-адресов и ведения статистики, которая будет использоваться для выявления DoS-атак.
Краулеры
Сканеры - это автоматизированные программные агенты, сканирующие сеть и ищущие контент, анализируя и индексируя все, что они находят. Когда сканер находит ссылки на странице или в документе, он обычно запрограммирован, чтобы следовать по ним и рекурсивно сканировать место назначения ссылки.
Есть некоторые исключения: например, большинство типов файлов будут игнорироваться сканерами, как и ссылки, созданные с помощью тегов с атрибутом.
rel="nofollow".
На самом деле рекомендуется отмечать таким образом любую привязку ссылкой на действие, имеющее побочные эффекты. В противном случае сканеры поисковых систем, даже если они соблюдают эту политику, будут вести себя непредсказуемо.
Что может случиться, так это то, что если вы напишете свой собственный сканер и не будете осторожны, он может оказаться в бесконечном цикле между двумя или более страницами с взаимными ссылками (или цепочкой ссылок) друг на друга. Чтобы избежать таких циклов, сканеры должны отслеживать страницы, которые они уже посетили.
Фильтры Блума - лучший способ сделать это, потому что они могут хранить URL-адреса в компактном виде и выполнять проверку и сохранение URL-адресов в постоянное время.
Сборщик IO
Кэширование на основе фильтра Блума помогает сократить ненужную выборку / хранение дорогостоящих ресурсов ввода-вывода. Механизм такой же, как и при сканировании: операция выполняется только тогда, когда у нас есть «промах», в то время как «попадания» обычно запускают более глубокое сравнение (например, при попадании, получение с диска только первых нескольких строк или первый блок документа и сравнивая их).
Программа проверки орфографии
Более простые версии программ проверки правописания, которые использовали фильтры Блума в качестве словарей. Для каждого проверенного слова текста поиск по фильтру Блума подтвердит правильность слова или пометит его как орфографическую ошибку. Конечно, ложные срабатывания могут привести к тому, что некоторые орфографические ошибки останутся незамеченными, но вероятность этого можно контролировать заранее. Однако сегодня средства проверки правописания в основном используют попытки: эти структуры данных обеспечивают хорошую производительность при текстовом поиске без ложных срабатываний.
Распределенные базы данных и файловые системы
Cassandra использует фильтры Блума для сканирования индекса, чтобы определить, есть ли в SSTable данные для определенной строки. Аналогичным образом, Apache HBase использует фильтры Блума в качестве эффективного механизма для проверки того, содержит ли StoreFile определенную строку или ячейку с строкой-столбцом. Это, в свою очередь, увеличивает общую скорость чтения за счет фильтрации ненужных операций чтения с диска блоков HFile, которые не содержат определенной строки или столбца-строки.
Все, что вы можете сделать с помощью фильтра Блума, вы можете сделать с меньшим объемом памяти и более эффективно, используя одну хеш-функцию, а не несколько.
Не правда. Использование нескольких хэш-функций может снизить уровень ложных срабатываний. В частности, учитывая фиксированное пространство в памяти, которое мы хотим использовать для нашего фильтра Блума в битах ( m бит ), и фиксированное количество элементов, которые он будет содержать ( n ), оптимальное количество хэш-функций k равно k = ( m / н ) пер 2 .
Почему не оптимально использовать одну хэш-функцию, как вы предлагаете? Самый простой способ увидеть это — рассмотреть фильтр Блума, содержащий один элемент. Если вы используете только одну хеш-функцию, у вас есть шанс 1/ m , что любой отдельный элемент, который вы ищете, даст ложное срабатывание (из-за хэширования до того же значения, что и элемент, действительно содержащийся в фильтре). Но если вместо этого у вас есть k > 1 хеш-функций, вероятность ложного срабатывания намного ниже (примерно 1/mᵏ , если m >> k), потому что все k хеш-значений должны столкнуться. В более общем случае, пока n мало, m велико и k мало, увеличивается kуменьшит количество ложных срабатываний.
Почему оптимальное число не может быть огромным? Потому что, если у вас слишком много хеш-функций, вы установите все (или почти все) биты в вашем фильтре Блума в 1, что приведет к 100% (или близкому к 100%) проценту ложных срабатываний.
Таким образом, решение для минимизации ложных срабатываний состоит в использовании нескольких хеш-функций (но не слишком много).
Использование хеш-таблицы для 1 млн элементов означает обнаружение коллизий после каждой 1 тыс. вставок из-за парадокса дня рождения . Фильтр Блума помогает значительно уменьшить количество коллизий, но также может давать ложноположительные результаты.