Проверка наличия объекта — одна из ключевых задач в программировании. Она встречается при разработке практически любого программного продукта. Чтобы ускорить поиск объекта, разработчики применяют фильтр Блума. В этой статье мы расскажем, почему появился фильтр Блума и в каких случаях его применяют. Также познакомим с принципами работы с фильтром и научим пользоваться им.
Эта тема не входит в стандартную программу подготовки программистов. Если вы изучите ее и примените на практике, то станете более востребованным специалистом.
Как ищут объект
Чтобы найти объект, применяют разные способы. Можно сделать последовательный перебор или использовать хеш-таблицы. При этом каждый из этих способов применяется в определенных случаях, и у них есть ограничения.
Например, поиск в таблице маршрутизации на роутере должен быть максимально быстрым, притом что скорость процессора и доступная память устройства ограничены.
Предположим, вы играете с другом в «Города». Вы плохо знаете географию и поэтому не можете утверждать, что Норфолк — это не город.
Программист решил бы эту проблему так: разработал программу, загрузил в нее справочник всех городов планеты и выполнил поиск. Но это не понравится сопернику, так как ему придется долго ждать.
Допустим, поиск города в неотсортированном списке занимает время О(N). Всего в мире насчитывается 2 667 417 городов. Предположим, что наш компьютер может выполнять 1 000 операций в секунду. Тогда время на поиск составит 2667,5 секунды — более 44 минут.
Это слишком долго для игры в «Города», поэтому нужно ускорить процесс. Например, купить компьютер помощнее, но тогда придется потратиться. Решить вопрос можно менее затратно — улучшить алгоритм, который сократит время поиска.
Например, можно использовать хеш-таблицы, чья скорость поиска в идеальном случае считается равной О(1). Только она требует больших затрат по памяти и зависит от выбранного разработчиком метода хеширования.
Из-за того, что в программировании не было идеального способа решения такой проблемы, придумали вероятностную структуру данных — фильтр Блума. С его помощью не ищут объект, а проверяют, что его не существует. Еще он решает поставленную задачу за время О(1) и не размещает все объекты в оперативной памяти.
Что такое фильтр Блума и как он работает
Фильтр Блума — это инструмент разработчика, который ускоряет проверку наличия объекта.
Фильтр состоит из двух частей: нескольких хеш-функций, которые преобразуют элементы, добавляемые в фильтр, и массива битов. Результатом вычисления хеш-функций будут позиции в массиве, значения которых будут равны единице.
Проверка вхождения проходит аналогично: к искомому элементу применяются те же хеш-функции. При этом номера полученных адресов сравниваются с соответствующими адресами в массиве битов.
Далее события могут развиваться по двум вариантам:
1) Хотя бы в одном из адресов содержится ноль — объекта нет в исходной последовательности.
2) Во всех адресах содержатся только единицы — искомый объект, возможно, присутствует в исходной последовательности.
Например, так выглядит фильтр последовательности трех элементов — x, y и z:
Фильтр состоит из трех хеш-функций и битового массива длиной 18. Когда элемент добавляется, к нему применяется по три хеш-функции — они возвращаются в результате позиции в массиве.
В местах, где указываются функции, устанавливаем значение элемента массива равным единице. Далее проверяется наличие элемента w.
В нашем примере проверка завершается неудачно, так как хеш-функции вернули позиции массива, в одной из которых содержится ноль.
Вернемся к игре, где один из соперников назвал город Норфолк. Чтобы узнать, есть ли такой город, применим фильтр Блума.
Составим полный список всех городов мира и применим для каждого элемента хеш-функции. У нас получится следующий массив:
Проверим работу программы для нашего списка на Москве:
Во всех адресах содержатся единицы — город Москва, возможно, есть в списке.
Теперь проверим наличие Норфолка в базе:
Одна из ячеек содержит ноль — города Норфолк нет в списке. Чтобы вычислить это, нам понадобились доли секунды, а не 40 минут для перебора каждого элемента списка.
Фильтр Блума ускоряет поиск объекта, что важно для разработки. При этом у него есть побочный эффект — результат бывает неопределенным. Например, когда хеш-функции вернули все позиции массива с единицей. Это означает, что объект, возможно, есть в исходной последовательности. Такой побочный эффект — главный недостаток фильтра Блума.
Какие у фильтра Блума недостатки и ограничения
У фильтра Блума есть важное преимущество: он экономит память и увеличивает скорость проверки информации о наличии конкретного объекта. Но из-за этого проявляется существенный недостаток.
Фильтр работает с косвенными данными, которые вычисляются на основе хеш-функций. Они подвергаются коллизиям — когда при разных входных документах с некоторой частотой выдаются одинаковые ответы.
Из-за этого недостатка у фильтра Блума появляется ограничение — вероятность ошибки. Фильтр отвечает, что объект, возможно, есть, хотя его нет в изначальной последовательности.
Вероятность ошибки можно уменьшить, если подобрать оптимальное количество хеш-функций, которые обрабатывают входную последовательность. Еще вероятность ошибки можно снизить, если увеличить размерность массива битов.
Представим, что мы продолжаем играть в «Города» и решили уменьшить вероятность ложноположительного ответа.
Если мы подберем оптимальное количество хеш-функций, вероятность ошибки составит 0,001 — 0,1%. Это значение нашли через вероятность ложноположительного срабатывания.
Получается, что на каждую тысячу названных игроками городов только один будет определен некорректно — возможно существующий. Это можно признать допустимым для игры.
Фильтр Блума все равно выдаст неопределенный ответ, если уменьшить вероятность ошибки.
Если нам нужен точный ответ, то можно выполнить традиционный поиск в исходной последовательности. Поэтому классические методы выбора оптимального алгоритма поиска все равно применяются.
Фильтр Блума сэкономит время на обращение к диску и уменьшит их частоту. Но это можно применить только в качестве предварительного фильтра запросов к основной последовательности.
В таком виде структура данных используется в поисковых движках типа Google. С ее помощью можно не обращаться к ресурсам, на которых гарантированно отсутствует информация из поискового запроса.
Несмотря на то, что фильтр Блума придумали более 50 лет назад, он до сих пор активно применяется разработчиками. Рассмотрим, где с ним можно столкнуться.
Где применяется фильтр Блума
По сравнению со старыми компьютерами, вычислительная мощность современных устройств выросла. При этом увеличилась и сложность задач. Некоторые из них могут решаться несколько дней из-за больших данных. В итоге запросы долго обрабатываются, памяти не хватает, а оборудование быстро изнашивается.
В этом случае помогает фильтр Блума, который применяется в следующих случаях:
1) Поиск в интернете. Здесь фильтр позволяет поисковой машине не сканировать ресурсы, на которых точно нет информации из поискового запроса. Это экономит время пользователя.
2) Таблицы маршрутизации. Например, черные списки IP-адресов, куда нельзя перенаправлять запросы. Эту информацию нужно получать максимально быстро. Ниже на рисунке пример проверки двух IP-адресов в черном списке:
Адреса 112.64.90.12 точно нет в списке, так как одна из функций вернула позицию с нулевым значением. Для адреса 178.23.12.63 нужно уточнение, так как фильтр отвечает, что адрес, возможно, есть в черном списке. Если бы маршрутизатор проверял каждый из адресов полностью, скорость работы интернета была бы значительно ниже
3) Системы проверки орфографии. В этом случае компьютер может выделить слово, которого нет в словаре. Так не придется нагружать устройство после каждого нажатия клавиши.
4) Криптокошельки. Фильтр Блума используется, чтобы искать транзакции. В результате с некоторой вероятностью можно утверждать, что транзакция в наличии, или ее нет.
5) В биоинформатике. Фильтр используется, чтобы искать фрагменты в последовательностях ДНК. Ниже на рисунке видно, как в фильтр Блума добавили цепочку ДНК ACCTAG и искали фрагмент CGTAT:
Поиск завершается неудачей, так как различается последняя буква в искомой последовательности аминокислот и исходной последовательности ДНК
Список случаев, где применяется фильтр Блума, постоянно пополняется. В сети можно найти публикации об открытии новых мест применения этой структуры данных.
Теперь посмотрим, как фильтр Блума применяется на практике. Поработаем с JavaScript.
Как фильтр Блума реализуется на JavaScript
Работу с фильтром Блума будем рассматривать по шагам.
1) Для начала создадим новый класс, который будет представлять нашу структуру данных. Также создадим к нему конструктор, который в качестве исходных параметров будет принимать размерность массива и количество используемых хеш-функций.
В свойствах конструктора сохраним входные значения и создадим массив, который проинициализируем нулевыми значениями:
/**
* Пример реализации «фильтра Блума»
*/
class BloomFilter{
/**
* @param size Размер битового массива для хранения адресов
* @param funcCount Количество функций для хеширования входной строки
*/
constructor(size, funcCount){
this.size = size;
this.funcCount = funcCount;
this.bitArray = new Array(size);
this.initiateArray();
}
/**
* Создаем битовый массив и предзаполняем его нулями
*/
initiateArray(){
for(let i = 0; i < this.bitArray.length; i++){
this.bitArray[i] = 0;
}
}
2) Далее реализуем операцию, которая добавляет элемент исходной последовательности в фильтр. Для этого захешируем исходный объект N раз с помощью различных хеш-функций и по каждому полученному адресу установим значение бита равным единице.
Чтобы упростить реализацию, мы используем одну хеш-функцию. Она будет незначительно изменять алгоритм хеширования в зависимости от номера функции, с которым ее вызвали.
Так как в JavaScript нет встроенного метода хеширования строки, будем использовать метод String.hashCode().
Этот алгоритм переводит строку в число, которое суммируется из кодов символов в таблице кодировки. Так как фильтру Блума нужно несколько разных хеш-функций, мы модифицируем исходную строку. Для этого добавим в качестве префикса номера используемой хеш-функции:
/**
* Реализация универсальной функции хеширования,
* которая отличается в зависимости от номера вызова
* @param input Входная строка
* @param functionNumber Номер вызова
* @returns Результат хеширования типа Number
*/
hashString(input, functionNumber){
let hash = 0;
let chr;
if (input.length === 0) return hash;
input = functionNumber + input; // Подставляем перед исходным текстом номер вызова
for (let i = 0; i < input.length; i++){
chr = input.charCodeAt(i);
hash = ((hash << 5) - hash) + chr;
hash |= 0;
}
return Math.abs(hash % this.size); // Определяем адрес в битовом массиве
}
/**
* Регистрируем элемент исходной последовательности в фильтре
* @param item Элемент исходной последовательности
*/
addItem(item){
for (let i = 0; i < this.funcCount; i++){
let index = this.hashString(item, i);
this.bitArray[index] = 1;
}
}
3) В конце проверим наличие элемента в последовательности. Для этого прогоним хеш-функции для искомого элемента и проверим по каждому адресу значение бита. Если хоть одно значение равно нулю, то элемента точно нет в последовательности:
/**
* Проверяем наличие искомого элемента в последовательности
* @param item Искомый элемент
* @returns true — «точно отсутствует», false — «отсутствует»
*/
checkItemNotPresented(item){
for (let i = 0; i < this.funcCount; i++){
let index = this.hashString(item, i);
if (this.bitArray[index] === 0) return true;
}
return false;
}
}
Если бы каждое значение равнялось единице, то элемент, возможно, был в последовательности.
Вывод
Вероятностная структура данных фильтр Блума увеличивает скорость проверки информации и показывает, есть ли объект в последовательности.
Этот инструмент важен для разработчиков, так как не разбирается в стандартных программах обучения, но ценится среди специалистов.
Сегодня фильтр используют в поисковых движках, таблицах маршрутизации, системах проверки орфографии и крипто-кошельках. Уже сейчас этот список может быть шире, так как разработчики постоянно ищут новые способы, чтобы применить инструмент.
Если хотите рассмотреть полную версию программной реализации, можете найти ее в Github. Так вы научитесь пользоваться фильтром Блума в полной мере и станете более востребованным специалистом.
Дополнительные материалы
- Пример реализации, разобранный в статье
- Основная статья с изложением идей Бертона Блума
- Детали определения вероятности ложноположительного срабатывания
- Имплементация алгоритма хеширования строк для JS
Никогда не останавливайтесь: В программировании говорят, что нужно постоянно учиться даже для того, чтобы просто находиться на месте. Развивайтесь с нами — на Хекслете есть сотни курсов по разработке на разных языках и технологиях
