В повседневной работе существует довольно распространенное требование — определить, входит ли элемент в набор.

Например следующий сценарий:

Учитывая библиотеку черного списка IP-адресов, проверьте, находится ли указанный IP-адрес в черном списке?
При получении электронных писем определить, является ли адрес электронной почты спамом?
В текстовом редакторе проверьте, правильно ли написано английское слово?

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

Фрагмент кода Java используется для имитации хранения и проверки библиотеки черного списка IP-адресов.

public class IPBlackList {

	public static void main(String[] args) {
		Set<String> set = new HashSet<>();
		set.add("192.168.1.1");
		set.add("192.168.1.2");
		set.add("192.168.1.4");
		System.out.println(set.contains("192.168.1.1"));
		System.out.println(set.contains("192.168.1.2"));
		System.out.println(set.contains("192.168.1.3"));
		System.out.println(set.contains("192.168.1.4"));
	}
	
}

Результаты:

true
true
false
true

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

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

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

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

Поколение Bloom Filter (Фильтр Блума) может очень хорошо решить эту проблему. С одной стороны, он может хранить данные с меньшим объемом памяти, а с другой стороны, может достигать очень эффективной производительности запросов.

Фильтр Блума

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

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

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

Фундаментальный

Основной принцип работы фильтра Блума не сложен, он примерно таков:

Во-первых, создайте двоичный вектор со всеми битами, установленными в 0.

Затем выбираются K хеш-функций для хеширования элементов K раз и вычисляется битовый индекс вектора.

добавить элемент

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

проверить элемент

Если вы хотите проверить, существует ли элемент в наборе, используйте тот же метод хеширования, сгенерируйте K нижних индексов и проверьте, равны ли все соответствующие биты вектора 1. Если все 1, элемент, вероятно, будет в наборе; в противном случае (пока 1 или более битов равны 0), элемент определенно не находится в наборе.

Это основная идея фильтра Блума.

простой пример

Предположим, есть фильтр Блума емкостью 15 бит и использующий 2 хеш-функции.

Добавьте строку a, дважды хешируйте ее, чтобы получить индексы 4 и 10, и пометьте биты, соответствующие 4 и 10, от 0 до 1.

Затем добавьте строку b, дважды хешируйте ее, чтобы получить индексы 11 и 11, и пометьте бит, соответствующий 11, от 0 до 1.

Добавьте еще одну строку c, дважды хешируйте ее, чтобы получить индексы 11 и 12, и пометьте биты, соответствующие 11 и 12, от 0 до 1.

Наконец, добавляется строка sam, и индексы 0 и 7 получаются 2-мя хэшами, а биты, соответствующие 0 и 7, размечаются от 0 до 1.

Выше мы добавили 4 строки, каждая из которых хешируется 2 раза, соответствующие 2 бита помечаются как 1 и, наконец, помечаются как 1, всего 6 бит вместо 8 бит.

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

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

Например, при проверке того, существует ли в наборе строка b, два нижних индекса, полученные с помощью хэша, равны 11. Проверка показала, что бит, соответствующий 11, равен 1. Однако это не означает, что b должно быть в множестве. Это связано с тем, что нижний индекс хешированной строки c также содержит 11. Возможно, что строка c есть в наборе, но b не существует, что вызывает неправильное распознавание, также известное как ложное срабатывание.

Снова проверьте строку foo.Нижние индексы, полученные хешем, равны 8 и 13 соответственно, а все соответствующие биты равны 0. Так что строки foo точно нет в наборе.

Математические принципы

Математика фильтра Блума такова:

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

2 способа решить проблему неправильного распознавания

белый список

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

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

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

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

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

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

Вернуться к подтверждению источника

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

Например:

Google Bigtable, Apache HBase, Apache Cassandra и PostgreSQL используют фильтры Блума, чтобы сократить количество операций поиска на диске несуществующих строк или столбцов. Отказ от дорогостоящих операций поиска на диске может значительно повысить производительность операций запросов к базе данных.
Веб-браузер, используемый в Google Chrome для выявления вредоносных URL-адресов с помощью фильтров Блума. Все URL-адреса сначала проверяются на соответствие локальному фильтру Блума, и только если фильтр Блума возвращает положительный результат, выполняется полная проверка выполненного URL-адреса (если этот результат также возвращает положительный результат, пользователь получает предупреждение).
Заблокируйте большое количество запросов к черному списку, отличных от IP, и снова запросите в базе данных черного списка небольшое количество IP-адресов, которые могут быть в черном списке.

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

Отличие этого метода от библиотеки белого списка в том, что нет необходимости строить еще один набор библиотек для обработки, а использовать уже существующие данные и логику.

Например, строки данных запроса Google Bigtable необходимо проверять, но большинство ненужных запросов блокируются с помощью фильтра Блума. И есть ли IP в черном списке, тоже нужно запрашивать.Также необходимо использовать фильтр Блума, чтобы сначала заблокировать большинство IP.

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

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

Ссылаться на

En. Wikipedia.org/wiki/bloom_…

en.wikipedia.org/en-us/bloom-filter

Лили Марлен поклонение.GitHub.IO/bloom filter…

woohoo.geek для гиков is.org/bloom-FI LTE…

«Красота математики»

обо мне

Публичный аккаунт: Binary Road

Руководство:996geek.com

Блог:binarylife.icu