Фильтр Блума
Фильтр Bloom - это структура данных, позволяющая компьютерам видеть, происходит ли данный элемент в наборе. Для этого фильтры Bloom используют хэш-функции. Для каждого добавляемого элемента вычисляется значение хэша. При добавлении нового элемента его значение хэша сравнивается со значением других элементов множества. Фильтр Блума представляет собой вероятностную структуру данных. Можно получить ложное срабатывание, но нельзя получить ложное срабатывание. Другими словами, запрос возвращает либо "возможно в множестве", либо "определенно не в множестве". Элементы могут быть добавлены в множество, но не удалены. Для каждого добавляемого элемента возрастает вероятность получения ложного срабатывания.
Эдвард Блум предложил фильтр Блума в 1970 году. В статье Блум предполагает наличие алгоритма дефисования слов в конце строки. Согласно примеру, большинство слов имеют простые шаблоны дешифровки. Но около 10% слов требуют трудоемкого поиска, чтобы получить правильное правило. В его случае дефисом было около 500 000 слов. Он видел, что при использовании "обычных" безошибочных техник хеширования, при хранении шаблонов дефисов, потребуется много памяти. Он обнаружил, что используя свою технику, он может исключить большинство поисков. Например, область хэша всего в 15% от размера, необходимого для идеального безошибочного хэша, по-прежнему исключает 85% доступа к диску.
В более общем случае для 1 % ложноположительной вероятности, независимо от размера или количества элементов в наборе, требуется менее 10 бит на элемент.
Вопросы и ответы
В: Что такое фильтр Блума?
О: Фильтр Блума - это структура данных, которая позволяет компьютеру определить, встречается ли данный элемент в наборе. Для этого он использует хэш-функции, вычисляя хэш-значение каждого добавленного элемента и сравнивая его с другими элементами в наборе.
В: Каким типом структуры данных является фильтр Блума?
О: Фильтр Блума - это вероятностная структура данных, то есть существует вероятность получения ложноположительных результатов, но не ложноотрицательных.
В: Кто предложил фильтр Блума?
О: Эдвард Блум предложил фильтр Блума в 1970 году.
В: Какой пример Эдвард привел для использования своей техники?
О: В качестве примера Эдвард привел дефисный поиск около 500 000 слов; он обнаружил, что, используя свою методику, он может исключить большинство поисков и сократить обращения к диску на 15%.
В: Сколько бит на элемент требуется для 1% вероятности ложного срабатывания?
О: Для 1% вероятности ложного срабатывания требуется менее 10 бит на элемент, независимо от размера или количества элементов в наборе.
В: Можно ли удалить элементы из фильтра цветности после того, как они были добавлены?
О: Нет, элементы можно только добавлять в набор, но не удалять.
В: Добавление большего количества элементов увеличивает или уменьшает вероятность получения ложноположительного результата?
О: Добавление большего количества элементов увеличивает вероятность получения ложноположительного результата.
