Понимание одной из самых популярных вероятностных структур данных

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

Точно так же, если вы упорядочите свои книги в лексикографическом порядке, вы можете легко найти книгу, если знаете ее название. Но если на вашей книжной полке есть ящики разных размеров, вам придется организовать свои книги по их размеру. Выглядит красиво, но можете ли вы быстрее найти книгу? Я так не думаю.

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

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

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

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

Цветочный фильтр

Вы знаете, как работают хеш-таблицы?

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

Теперь в хэш-таблицах вы определяете ключ или индекс путем хеширования значения. Затем вы помещаете это значение в этот индекс в списке. Это означает, что ключ определяется из значения, и каждый раз, когда вам нужно проверить, существует ли значение в списке, вы просто хешируете значение и выполняете поиск по этому ключу. Это довольно быстро и потребует времени поиска O (1) в нотации Big-O.

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

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

Что ж, в этом нам может помочь фильтр Блума. Как? Я отвечу на этот вопрос сразу после того, как объясню, как работает фильтр Блума. OK?

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

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

Не будь нетерпеливым. Вскоре я объясню, что это на самом деле означает.

Фильтр Блума по существу состоит из битового вектора или битового списка ( список, содержащий только 0 или 1-битное значение ) длины m . Первоначально все значения установлены на ноль, как показано ниже.

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

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

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

Мы уже заполнили наш битовый вектор двумя входами. Теперь мы можем проверить наличие значения. Как мы можем сделать это?

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

Итак, при поиске по запросу cat наши хеш-функции на этот раз дают нам один, три и семь. И мы видим, что все индексы уже помечены как один. Это означает, что мы можем сказать: «Возможно, кот уже внесен в наш список».

Но это не так. Итак, что пошло не так?

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

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

Итак, в двух словах:

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

Это начинает иметь смысл? Может, немного?

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

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

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

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

Также учтите, что если ваши фильтры bloom фильтруют ложные срабатывания 1% (мы поговорим о частоте ошибок более подробно позже), это означает, что среди дорогостоящих циклических обращений к серверу или диску будет возвращен только 1% запроса. с ложными результатами. Остальные 99% не пропадут даром.
Неплохо, а?

Операции с фильтром Блума

Базовый фильтр цветения поддерживает две операции: test и add.

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

Добавить просто добавляет элемент в набор.

А теперь небольшая викторина для вас.

Исходя из того, что мы обсуждали до сих пор, можно ли удалить элемент из фильтра цветения? Если да, то как?

Сделайте двухминутный перерыв и подумайте над решением.

Есть что-нибудь? Ничего такого? Позвольте мне немного помочь вам. Давайте вернем бит-вектор после вставки в него компьютерных фанатов и ботаников.

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

Итак, какое решение?

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

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

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

Размер фильтра Блума и количество хэш-функций

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

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

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

Из приведенного выше графика видно, что увеличение количества хэш-функций k резко снижает частоту ошибок p.

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

Не волнуйтесь, нам в основном нужно решить, какими будут наши m и k. Итак, если мы сами установим значение допуска ошибки p и количество элементов n, мы сможем использовать следующие формулы для вычисления этих параметров:

Еще один важный момент, о котором я также должен упомянуть. Поскольку единственная цель использования фильтра Блума - ускорить поиск, мы не можем использовать медленные хэш-функции, верно? Криптографические хеш-функции, такие как Sha-1 и MD5, не подходят для фильтров Блума, поскольку они немного медленные. Таким образом, лучшим выбором из более быстрых реализаций хеш-функций будет murmur, серия хешей fnv, хеши Jenkins и HashMix.

Приложения

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

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

Еще несколько конкретных примеров:

  • В данном примере вы видели, что мы могли использовать его для предупреждения пользователя о слабых паролях.
  • Вы можете использовать фильтр цветения, чтобы предотвратить доступ ваших пользователей к вредоносным сайтам.
  • Вместо того, чтобы делать запрос к базе данных SQL, чтобы проверить, существует ли пользователь с определенным адресом электронной почты, вы можете сначала использовать фильтр Блума для недорогой проверки поиска. Если электронной почты не существует - отлично! Если он существует, возможно, вам придется сделать дополнительный запрос к базе данных. То же самое можно сделать и с поиском, если имя пользователя уже занято.
  • Вы можете сохранить фильтр цветения, основанный на IP-адресах посетителей вашего веб-сайта, чтобы проверять, является ли пользователь вашего веб-сайта вернувшимся пользователем или новым пользователем. Некоторые ложноположительные значения для вернувшегося пользователя не повредят вам, верно?
  • Вы также можете сделать проверку орфографии с помощью фильтра Блума для отслеживания слов из словаря.
  • Хотите знать, как Medium использовал фильтры цветения, чтобы определить, читал ли пользователь уже статью? Прочтите об этом умопомрачительно, чертовски круто.

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