Если вы хотите определить, находится ли элемент в наборе, общая идея состоит в том, чтобы сохранить все элементы в наборе, а затем определить их путем сравнения. Связанные списки, деревья, хеш-таблицы (также известные как хеш-таблицы, Hash-таблицы) и другие структуры данных — все это таким образом.Вообще говоря, коллекции в компьютерах хранятся в хеш-таблицах.
Но по мере увеличения элементов в коллекции нам нужно все больше и больше места для хранения. В то же время скорость поиска становится все медленнее и медленнее.Сложность времени поиска трех вышеуказанных структур составляет O (n), O (logn) и O (1). Среди них пространственная сложность хеш-таблицы с наименьшей временной сложностью составляет O (N).При сотнях миллионов записей стоимость хранения этого метода реализации будет относительно большой.
Например, общедоступный провайдер электронной почты, такой как Yahoo, Hotmail и Gmail, всегда должен фильтровать спам от спамеров. Один из способов — отслеживать адреса электронной почты, с которых рассылается спам. Поскольку эти отправители постоянно регистрируют новые адреса, по всему миру существуют миллиарды спам-адресов, если не сказать больше, и для их хранения потребуются огромные веб-серверы. Если используется хеш-таблица, требуется 1,6 ГБ памяти для каждых 100 миллионов сохраненных адресов электронной почты (конкретный способ использования хеш-таблицы заключается в отображении каждого адреса электронной почты в восьмибайтный информационный отпечаток (см.:Китай.Google blog.com/2006/08/No…), а затем сохранить эти отпечатки информации в хэш-таблице. Поскольку эффективность хранения хэш-таблицы обычно составляет всего 50%, адрес электронной почты должен занимать 16 байт. 100 миллионов адресов составляют около 1,6 ГБ или 1,6 миллиарда байт памяти). Таким образом, для хранения миллиардов адресов электронной почты могут потребоваться сотни гигабайт памяти. Если это не суперкомпьютер, общий сервер не может его хранить - отчет Google BlackboardКитай.Google blog.com/2007/07/No…
Так есть ли другой способ добиться того же? Эта статья знакомит с фильтром Блума, его принципом и применением.
Если интервьюер спросит вас, веб-сайт имеет 10 миллиардов URL-адресов в черном списке, и каждый URL-адрес в среднем составляет 64 байта. Как сохранить этот черный список? Если вы введете URL-адрес в это время, как определить, находится ли URL-адрес в этом черном списке?
текст
Фильтр Блума(фильтр Блума) можно использовать для определения того, находится ли элемент в коллекции. Его преимуществоКак эффективность использования пространства, так и время запроса намного превышают общий алгоритм., слабостьСуществует определенная скорость неправильного распознавания и сложность удаления элементов..
Общий фильтр Блума предоставляет два метода:TestиAdd
TestИспользуется для подтверждения наличия элемента в коллекции. если он возвращает:
false, то этот элементне должно быть тамвнутри коллекции.
правда, то этот элемент простовозможныйВ наборе некоторые элементы, которых нет в наборе, будут неправильно оценены в наборе.Для описания этой вероятности используется частота ложных срабатываний фильтра Блума.растет по мере роста данных, Между тем такжесвязанные с используемой хэш-функцией.
Частота ложных срабатываний — это вероятность того, что фактические данные ложны, а предсказанные данные (оценка фильтра Блума) верны.
AddИспользуется для добавления элементов в коллекцию.
Здесь нет удаления, и когда мы будем говорить о принципиальной части, мы ясно объясним, почему фильтру Блума сложно удалять элементы.
Принцип фильтра Блума
Принцип фильтра Блума заключается в том, что когда элемент добавляется в набор, элемент сопоставляется с K точками в битовом массиве через K хэш-функций, и им присваивается значение 1. При извлечении нам нужно только увидеть, все ли эти точки равны 1, чтобы (приблизительно) узнать, есть ли он в наборе: если какая-либо из этих точек имеет 0, проверяемый элемент должен отсутствовать; если все они равны 1, тогда отмеченный элемент, скорее всего, будет там. Это основная идея фильтра Блума.
структура данных
Фильтр Блума — это битовый вектор, который выглядит так:
При добавлении элемента в фильтр Блума мы передаем это значение в k хэш-функций, а затем устанавливаем бит позиции результата в 1. В примере на рисунке длина вектора или массива равна 50, используя 3 хеш-функции.
Когда мы хотим определить, находится ли элемент в фильтре Блума, мы передаем это значение в k хеш-функций, чтобы получить k точек карты. На этот раз мы подтверждаем, что все точки установлены в 1, если есть бит, который не установлен в 1, то этот элементточно нет в комплекте. Если оба находятся в этом элементе, тоВозможно в наборе.
Прочитав принцип, мы поймем, почемуВозможные ложные срабатывания фильтров Блумаа такжеЧем больше элементов, тем выше процент ложных срабатываний (вероятность неправильной оценки), потому что по мере того, как добавляется все больше и больше значений, все больше и больше бит устанавливаются в 1, так что даже если определенное значение не было сохранено, возможно, что все k бит, возвращаемые хеш-функцией элемента, Если он установлен в 1 другими значениями, программа все равно будет считать, что это значение существует.
The false positive probability p as a function of number of elements n in the filter and the filter size m.
В то же время количество хеш-функций также необходимо взвешивать: чем больше число, тем быстрее бит фильтра Блума устанавливается в 1 и тем ниже эффективность фильтра Блума, но если оно слишком мало, тогда наш уровень ложных срабатываний станет выше.
Что касается того, как выбрать подходящее количество хеш-функций k и длину фильтра Блума m, кто-то вывел следующую формулу
Поняв принцип работы фильтра Блума, мы знаем, что удалить элементы в фильтре Блума практически невозможно, но на самом деле существует метод, который называетсяcounting bloom filtersструктура данных
сцены, которые будут использоваться
Используйте фильтры Блума, чтобы уменьшить дисковый ввод-вывод или сетевые запросы.
Типичным примером является использование фильтра Блума для уменьшения количества дисковых операций ввода-вывода или сетевых запросов (обе дорогостоящие операции) для поиска несуществующего ключа.
Фильтр Блума возвращает false, тогда этого значения точно нет
Поскольку значение не должно существовать, мы можем избежать последующих дорогостоящих запросов. Если он есть, то мы его поищем.Поскольку процент ложных срабатываний не слишком высок, эта стоимость в целом доступна.
Знаменитая распределенная база данных Google Bigtable использует фильтры Блума для поиска несуществующих строк или столбцов, чтобы уменьшить количество операций ввода-вывода для поиска на диске.
Фильтры Блума также используются во многих системах Key-Value для ускорения процесса запроса, таких как Hbase, Accumulo, Leveldb.Вообще говоря, значение хранится на диске, и доступ к диску занимает много времени.Однако, с помощью фильтра Блума можно быстро определить, существует ли значение, соответствующее ключу, что позволяет избежать многих ненужных операций ввода-вывода с диском.
Например, в системе шипов с высокой степенью параллелизма система захвата красных конвертов определяет, получил ли пользователь сегодня красный конверт.
В системе сканера нам нужно удалить дубликаты URL-адреса, а просканированные веб-страницы могут быть опущены. Но URL-адресов слишком много, десятки миллионов или миллиарды. Было бы пустой тратой места хранить эти URL-адреса в одном наборе. В настоящее время вы можете рассмотреть возможность использования фильтра Блума. Это может значительно сократить потребление хранилища дедупликацией, но также приведет к тому, что система сканирования пропустит небольшое количество страниц.
Функция фильтрации спама системы почтовых ящиков также обычно использует фильтр Блума.Из-за этого фильтра некоторые обычные электронные письма обычно помещаются в каталог спама.Это вызвано ошибочным суждением.Вероятность мала.