Фильтр Блума на PHP

Что это?

Википедия гласит:

Это вероятностная структура данных, придуманная Бёртоном Блумом в 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 без счетчика и со счетчиком.