Assorium Feb 26 2013 at 10:58

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

3 min

18K

PHP*Algorithms*

+33

Comments 23

Igorbek Feb 26 2013 at 12:05

Если хэш 32-х битный, то нужно 0.5 Гб памяти? И это без счётчика. Вы хэши какой длины использовали?

Mrrl Feb 26 2013 at 12:47

Для 10^7 элементов и вероятности ложного срабатывания 1% оптимально иметь 7 хэшей при массиве в 95 Mbit. Займёт такой массив 12 МБ (без счетчиков) и заполнен он будет примерно на 50%. Если брать 27-битные хэши (массив в 16MiB), то их оптимально взять 9 штук и вероятность ложного срабатывания будет около 0.16%.

Assorium Feb 26 2013 at 13:26

Поправьте, если я чего-то не понял.
Количество хеш-функций определяется из 2-х условий: количества объектов в выборке и вероятности «ложноположительного» срабатывания. Mrrl прав. Число хеш-функций крайне мало по сравнению с количеством объектов. И основную память занимает как раз битовая строка.

Хеш функция приведена в тексте:

 abs( crc32( md5($this->seed[0] . $string) ) ) % $size;

Mrrl Feb 26 2013 at 13:40

На самом деле, даже количество объектов ни при чём. Важно лишь отношение длины битовой строки к этому количеству. Лучше всего это отношение брать около 1.5*h, где h — число хеш-функций, а последнее определять, исходя из желаемой вероятности ошибки (она будет около 0.5^h).

Assorium Feb 26 2013 at 13:54

Ну это логично.

$\textstyle k = \frac{m}{n}\ln 2 \approx 0.6931 \frac{m}{n},$
$2^{-k} \approx {0.6185}^{m/n}.$

Тем более примеры потребления памяти в тексте приведены. Я просто не совсем понял, что конкретно имел в виду Igorbek

ToSHiC Feb 26 2013 at 13:57

Думаю, для тех, кто не очень в теме про блум-фильтры, или хочет почитать про выбор параметров, будет полезно почитать википедию вот в этом разделе: en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives

Кажется, ваши формулы оттуда :)

Assorium Feb 26 2013 at 14:22

Они с русской страницы этой же статьи :)

nikita2206 Feb 26 2013 at 12:19

Не знаю, знали ли вы об этом или нет, но в пхп для сетов лучше использовать ключи массивов. В принципе хеш-таблиц для этого достаточно обычно. Попробуйте сравнить свой фильтр и isset($array[«value»])

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

Assorium Feb 26 2013 at 14:26

Я думал об этом. Как минимум памяти это съест гораздо больше. А вот о возможности задавать в виде ключа строку различных кодировок я не уверен. Разве что и там хеширование использовать.
В общем, я проверю.

nikita2206 Feb 26 2013 at 14:34

Насчет кодировок там все в порядке будет, пхп будет работать с массивами каров, его не волнует что за кодировка там. А с памятью да.

Assorium Feb 26 2013 at 18:34

Кстати, рост памяти во время проверки только из-за наполнения массива ошибок. Его размер равен половине размера выборки. Без него Bloom потребляет почти ничего.

fifonik Feb 26 2013 at 12:37

> Гугл применяет его в своем поисковом движке.

А! Так ведь это он не рекламу мне показывает, это просто ложно-положительные срабатывания! :)

ToSHiC Feb 26 2013 at 12:39

А можете провести ваш тест уникальности для MurMurHash2?

Assorium Feb 26 2013 at 14:24

Да, можно. Под рукой был только Windows, поэтому было невозможно его проверить. Скоро выложу информацию.

Assorium Feb 26 2013 at 18:19

Скорость не проверял, хотя уверен, что работает гораздо быстрее. Уникальность на уровне 62-64%. Есть подозрение, что это из-за использования crc32 в качестве преобразования строка -> число.
Вот код теста.

<?
$num = 2000;
$string = "some long string to test murmur unique";

$ar = array();
for($i=0; $i<$num; $i++) {
  $ar[ abs( crc32( murmurhash3($string, rand(0, $num*60))  ) ) % $num ] = 1;
}

echo array_sum($ar)/$num, PHP_EOL;
?>

Вообще не вижу смысла использовать, даже если работает быстрее, т.к. тогда уже лучше использовать расширение фильтра Блума написанное на C. Но как дополнительный вариант можно добавить.

ToSHiC Feb 26 2013 at 18:27

Попробуйте убрать abs( crc32 ()) — murmurhash3 и так int должен возвращать. murmurhash3 должен быть сильно быстрее md5.

Assorium Feb 26 2013 at 18:38

Вы что, я бы не стал оставлять, если бы он возвращал число. Для меня была целая проблема найти хоть что-то хеширующее и возвращающее число.

Из Википедии

The current version is MurmurHash3 which yields a 32-bit or 128-bit hash value.

ToSHiC Feb 26 2013 at 19:00

Ну вот 32 бита — это как раз uint32_t. Я hashmurmur2 в плюсовом коде использую, и интерпретирую ответ именно как чиселку, сразу делю ей на количество хэш-бакетов. Не знаю, как именно сделано в php, поэтому не могу посоветовать, как с результатом работать.

Assorium Feb 26 2013 at 19:05

Ну тут разницы нет. Конвертирование никто не отменял. Другое дело, что с большими числами напрямую не поработать, поэтому crc32 мне здорово помог. Я пробовал различные манипуляции с разными хешами и лучшей уникальности/производительности добиться не смог.

ToSHiC Feb 26 2013 at 19:33

А у вас он возвращает hex в виде строки? Если модуль для php из исходников ставили — то просто пропатчте его, чтобы uint возвращал, и будет вам счастье в виде хорошей хэш-функции, возвращающей чиселку.

weirdan Feb 26 2013 at 13:59

Удивлен, не увидев в сравнении bloomy

guyfawkes Feb 26 2013 at 22:48

А не могли бы вы пояснить, как работает этот «счетчик» с использованием алфавита?

Assorium Feb 27 2013 at 09:20

Есть алфавит, к примеру '01234567890abcdef'
И вместо 1 производится инкремент по алфавиту. Т.е. если стоял символ 'b' после инкремента будет символ 'c', декремент (во время удаления) все делает наоборот.

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

Show the best of all time