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

Ответ 1

От Wikipedia:

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

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

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

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

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

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

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

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

Ответ 2

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

Предположим, что я работаю в 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-адрес вряд ли будет вредоносным, фильтр маленького цветения в браузере отображает это и, следовательно, экономит время, избегая вызовов на удаленный сервер. Только в некоторых случаях, если фильтр цветения сообщает нам, что URL МОЖЕТ быть вредоносным, только в тех случаях мы делаем звонок на сервер. Это "MIGHT" имеет право 99%.

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

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

изменить

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

Ответ 3

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

Таким образом, стандартный фильтр цветения является вероятностной структурой данных, которая может ^*

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

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

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

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

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

Но подождите минуту: мы уже знаем структуру данных, которая может ответить на все это без смутного "возможного", а также без всех ограничений (не может удалить, не может показать все). И он называется 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, чтобы предотвратить сохранение "one-hit-wonders" в своих кеш-дисках. Однократные чудеса - это веб-объекты, запрошенные пользователями только один раз, то, что Акамаи нашел применимым к почти трем четвертям своей инфраструктуры кэширования. Использование фильтра Bloom для обнаружения второго запроса для веб-объекта и кэширования этого объекта только по его второму запросу предотвращает попадание одного попадания чужих в кеш диска, что значительно снижает нагрузку на диск и увеличивает частоту попадания в кеш диска (взяты из примеров в цветном фильтре статья в wiki)

Ответ 4

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

EDIT:

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

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

Ответ 5

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