Что это?
Это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложно-положительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложно-отрицательное.
А попроще
Это способ проверки существования элемента в огромной выборке.
Как это работает?
Довольно просто. Мы имеем битовый объект определенной длинны. Также определяем несколько уникальных хеш-функций. Каждое значение выборки проходит через каждую хеш-функцию, которая возвращает позицию в битовой строке и устанавливает в нее 1.
Позже, когда нам необходимо узнать, есть ли элемент в выборке, мы просто пропускаем его через все хеш-функции. Если на всех позициях битовой строки была 1, то объект «возможно присутствует», если хотя бы в одном месте был 0, то объекта нет.
На википедии приведена матмодель определения длинны битовой строки и количества хеш-функций для определенного размера выборки и процента ложно-положительного срабатывания.
Где это можно применить?
Я применяю фильтр, чтобы проверить существования слова или фразу в словаре >10000000 слов. Гугл применяет его в своем поисковом движке.
Вообще положительный момент фильтра Блума в скорости его работы, когда соотношение операций Вставка/Проверка более 0.001 и проверок более 10000. Но это только если сравнивать со стандартным in_array в PHP.
Плюсы очевидны: скорость, меньшая нагрузка на диск, меньшее потребление памяти.
Минусы: долгая загрузка значений, нет возможности удаления (есть решение)
Зачем еще один велосипед? Я уверен, уже делали фильтр Блума на php.
Да, делали. Я провел бенчмарки и моя реализация опередила по скорости и расходу памяти все, которые я смог завести. Об уникальности хеш-алгоритмов я вообще промолчу.
В чем соль?
На самом деле проблемы две.
1. Как хранить битовую строку
2. Нужен уникальный хеш.
1. Тут проблема скорее в том, как хранить битовую строку для варианта с удалением. В том случае используется счетчик и выставляется не 1, а инкремент при добавлении объекта. Я решил использовать алфавит. Но удаление штука не самая хорошая, удаляются элементы, на которые фильтр отвечает «возможно присутствует» и если это было ложно-положительное срабатывание, мы удалим несуществующий объект.
2. Я не специалист по хешам и подбирал функцию хеширования по 2м показателям.
Скорость работы, наверное самый важный показатель. Уникальность, при создании 1000 уникальных хешей, на одну и туже строку они должны выдать 1000 различных значений. Я, к сожалению, добился только 64% уникальности. У конкурентов выше 40% показатель не поднимался.
И это всего лишь:
abs( crc32( md5($this->seed[0] . $string) ) ) % $size;
Уникальность создается при помощи рандомной строки $this->seed[0].
Где попробовать?
Милости прошу на Github.
И пробуем:
include 'bloom.class.php';
$parameters = array(
'entries_max' => 2 //создаем Объект для выборки из 2х элементов, с дефолтной вероятностью ошибки 0.1%
);
$bloom = new Bloom($parameters);
//добавляем элемент, можно добавить массив элементов
$bloom->set('Some string');
//проверяем наличие элемента
echo $bloom->has('Some string'); //true
//удаление объекта, только если Bloom был инициирован с параметром counter
$bloom->delete('Some string');
Доступные параметры:
/*
//основные
entries_max (int) Размер выборки. По умолчанию: 100.
error_chance (float) (0;1) Шанс ошибки. По умолчанию: 0.001.
counter (boolean) Используется для включения режима счетчика, чтобы можно было удалять объекты. По умолчанию: false.
//на свой страх и риск
set_size (int) Размер битовой строки. По умолчанию: вычисляется.
hash_count (int) Количество уникальных хешей. По умолчанию: вычисляется.
//параметры для Хешей, вложенным массивом
['hash']
strtolower (boolean) Конвертировать строки в нижний регистр или нет. По умолчанию: true;
*/
Прилагаются примеры, юнит-тесты, и бенчмарки (сравнение с in_array двумя способами и с тремя другими библиотеками). Многие из Вас и сами способны это написать, но возможно кому-то не захочется велосипедить.
Бонус: бенчмарк на 50 000 выборку с 25000 проверок против in_array без счетчика и со счетчиком.
Автор: Assorium
