Assorium26 фев 2013 в 06:58

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

3 мин

19K

PHP * Алгоритмы *

+33

Комментарии 23

Igorbek 26 фев 2013 в 08:05

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

Mrrl 26 фев 2013 в 08:47

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

Assorium 26 фев 2013 в 09:26

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

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

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

Mrrl 26 фев 2013 в 09:40

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

Assorium 26 фев 2013 в 09:54

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

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

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

ToSHiC 26 фев 2013 в 09:57

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

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

Assorium 26 фев 2013 в 10:22

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

nikita2206 26 фев 2013 в 08:19

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

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

Assorium 26 фев 2013 в 10:26

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

nikita2206 26 фев 2013 в 10:34

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

Assorium 26 фев 2013 в 14:34

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

fifonik 26 фев 2013 в 08:37

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

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

ToSHiC 26 фев 2013 в 08:39

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

Assorium 26 фев 2013 в 10:24

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

Assorium 26 фев 2013 в 14: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 26 фев 2013 в 14:27

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

Assorium 26 фев 2013 в 14:38

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

Из Википедии

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

ToSHiC 26 фев 2013 в 15:00

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

Assorium 26 фев 2013 в 15:05

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

ToSHiC 26 фев 2013 в 15:33

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

weirdan 26 фев 2013 в 09:59

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

guyfawkes 26 фев 2013 в 18:48

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

Assorium 27 фев 2013 в 05:20

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

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий