Фильтр Блума: зачем нужен и как работает

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

• Как ищут объект
• Что такое фильтр Блума и как он работает
• Какие у фильтра Блума недостатки и ограничения
• Где применяется фильтр Блума
• Как фильтр Блума реализуется на JavaScript
• Вывод
• Дополнительные материалы

Эта тема не входит в стандартную программу подготовки программистов. Если вы изучите ее и примените на практике, то станете более востребованным специалистом.

Как ищут объект

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

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

Предположим, вы играете с другом в «Города». Вы плохо знаете географию и поэтому не можете утверждать, что Норфолк — это не город.

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

Допустим, поиск города в неотсортированном списке занимает время О(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

Никогда не останавливайтесь: В программировании говорят, что нужно постоянно учиться даже для того, чтобы просто находиться на месте. Развивайтесь с нами — на Хекслете есть сотни курсов по разработке на разных языках и технологиях