html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

Фильтр Блума на 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 без счетчика и со счетчиком.
Читать дальше
Twitter
Одноклассники
Мой Мир

материал с habrahabr.ru

1

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • habrahabr.ru
          • домен habrahabr.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции