Реализация цветного фильтра

Question

Используя фильтр Bloom, мы будем получать оптимизацию пространства. Рамка cassandra также имеет реализацию Bloom Filter. Но подробно, как достигается эта оптимизация пространства?

Answer 1

Цветочный фильтр не является «каркасом». Это больше похоже на алгоритм. Реализация не очень длинная.

Вот один в Java я попытался (.jar, исходный код и JavaDoc быть все доступны):

«Автономные реализации Java кукушки HASHING и Блум Фильтры» (вы можете Google для этого в случае следующая ссылка не работает больше):

http://lmonson.com/blog/?page_id=99

Answer 2

Так что я видел этот вопрос раньше, и я использовал совет выше, и оказалось, что способ замедлить для меня. Поэтому я написал свой собственный. Это не в полной мере целом, но я уверен, что если кто-то отчаянным для исполнения, как и я, они сделают его более общим сами по себе :)

Я использовал реализации хэш ропот, который вы можете скачать здесь: http://d3s.mff.cuni.cz/~holub/sw/javamurmurhash/

код: package uk.ac.cam.cl.ss958.SpringBoardSimulation;

import ie.ucd.murmur.MurmurHash; 

    import java.util.BitSet; 
    import java.util.Random; 

    public class FastBloomFilter { 

     private final BitSet bs; 

     final int [] hashSeeds; 

     final int capacity; 

     public FastBloomFilter(int slots, int hashFunctions) { 
      bs = new BitSet(slots); 
      Random r = new Random(System.currentTimeMillis()); 
      hashSeeds = new int[hashFunctions]; 
      for (int i=0; i<hashFunctions; ++i) { 
       hashSeeds[i] = r.nextInt(); 
      } 
      capacity = slots; 
     } 

     public void add(int value) { 
      byte [] b = new byte[] { 
        (byte)(value >>> 24), 
        (byte)(value >>> 16), 
        (byte)(value >>> 8), 
        (byte)value}; 
      for (int i=0; i<hashSeeds.length; ++i) { 
       int h = MurmurHash.hash32(b, 4, hashSeeds[i]); 
       bs.set(Math.abs(h)%capacity, true); 
      } 
     } 

     public void clear() { 
      bs.clear(); 
     } 

     public boolean mightContain(int value) { 
      byte [] b = new byte[] { 
        (byte)(value >>> 24), 
        (byte)(value >>> 16), 
        (byte)(value >>> 8), 
        (byte)value}; 
      for (int i=0; i<hashSeeds.length; ++i) { 
       int h = MurmurHash.hash32(b, 4, hashSeeds[i]); 

       if(!bs.get(Math.abs(h)%capacity)) { 
        return false; 


      } 

      return true; 
     } 


     public static void main(String [] args) { 
      FastBloomFilter bf = new FastBloomFilter(1000, 10); 
      System.out.println("Query for 2000: " + bf.mightContain(2000)); 
      System.out.println("Adding 2000"); 
      bf.add(2000); 
      System.out.println("Query for 2000: " + bf.mightContain(2000)); 


     } 
    } 

Answer 3

Вы можете понять, как это экономит пространство, используя этот пример: Допустим, я работаю в Google, в команде Chrome, и я хочу, чтобы добавить элемент в браузере, который уведомляет пользователя, если URL он имеет введенный вредоносный URL. Поэтому у меня есть набор данных, насчитывающий около 1 миллиона злонамеренных URL-адресов, размер которого составляет около 25 МБ. Поскольку размер довольно большой (большой по сравнению с размером самого браузера), я храню эти данные на удаленном сервере.

Случай 1: Я использую хеш-функцию с хеш-таблицей. Я решаю эффективную функцию хеширования и запускаю все 1 миллион URL-адресов через хеширующую функцию для получения хэш-ключей. Затем я создаю хэш-таблицу (массив), где хэш-ключ даст мне индекс для размещения этого URL-адреса. Итак, теперь, когда я хэшировал и заполнял таблицу хеширования, я проверяю его размер. Я сохранил все 1 миллион URL-адресов в хэш-таблице вместе с ключами. Таким образом, размер составляет не менее 25 МБ. Эта хеш-таблица из-за ее размера будет храниться на удаленном сервере. Когда пользователь приходит и вводит URL-адрес в адресной строке, мне нужно проверить, злонамерен ли он. Таким образом, я запускаю URL через хэш-функцию (сам браузер может это сделать), и я получаю хэш-ключ для этого URL-адреса. Теперь я должен сделать запрос на мой удаленный сервер с помощью этого хеш-ключа, чтобы проверить, является ли конкретный URL-адрес в моей хэш-таблице с этим конкретным ключом, таким же, как и введенный пользователем. Если да, то это злонамеренно, и если нет, то это не злонамеренно. Таким образом, каждый раз, когда пользователь вводит URL-адрес, запрос на удаленный сервер должен быть проверен, является ли он злонамеренным URL-адресом. Это займет много времени и, таким образом, сделает мой браузер медленным.

Случай 2: Я использую фильтр цветения. Весь список из 1 миллиона URL-адресов запускается через фильтр цветения с использованием нескольких хеш-функций, а соответствующие позиции помечены как 1, в огромном массиве из 0. Допустим, мы хотим, чтобы ложная положительная ставка составляла 1%, используя калькулятор фильтра цветения (http://hur.st/bloomfilter?n=1000000&p=0.01), мы получаем размер фильтра цветения, который требуется всего лишь 1,13 МБ. Ожидается такой небольшой размер, хотя размер массива огромен, мы сохраняем только 1 или 0, а не URL-адреса, как в случае хэш-таблицы. Этот массив можно рассматривать как бит-массив. То есть, поскольку у нас есть только два значения 1 и 0, мы можем установить отдельные биты вместо байтов. Это сократило бы пространство, затраченное 8 раз. Этот цветной фильтр размером 1,13 МБ, благодаря его небольшому размеру, может храниться в самом веб-браузере!Таким образом, когда пользователь приходит и вводит URL-адрес, мы просто применяем требуемые хэш-функции (в самом браузере) и проверяем все позиции в цветном фильтре (который хранится в браузере). Значение 0 в любой из позиций говорит нам, что этот URL-адрес НЕ ОПРЕДЕЛЕН в списке злонамеренных URL-адресов, и пользователь может действовать свободно. Таким образом, мы не звонили на сервер и, следовательно, экономили время. Значение 1 сообщает нам, что URL-адрес МОЖЕТ быть включен в список злонамеренных URL-адресов. В этих случаях мы делаем звонок на удаленный сервер, и там мы можем использовать некоторую другую хеш-функцию с некоторой хеш-таблицей, как в первом случае, чтобы получить и проверить, действительно ли URL-адрес. Поскольку в большинстве случаев URL-адрес вряд ли будет вредоносным, фильтр маленького цветения в браузере отображает это и, следовательно, экономит время, избегая вызовов на удаленный сервер. Только в некоторых случаях, если фильтр цветка сообщает нам, что URL-адрес может быть вредоносным, только в тех случаях мы делаем звонок на сервер. Это «MIGHT» имеет право 99%.

Таким образом, используя небольшой фильтр цветения в браузере, мы сохранили много времени, так как нам не нужно делать серверные вызовы для каждого введенного URL.

Answer 4

Вы можете использовать фильтр Bloom на основе сервера Redis с Redisson lib. На основе 128 бит HighwayHash. Вот пример:

RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample"); 

// initialize bloom filter once with 
// expectedInsertions = 55000000 
// falseProbability = 0.03 
bloomFilter.tryInit(55000000L, 0.03); 

bloomFilter.add(new SomeObject(someStateHere1)); 
bloomFilter.add(new SomeObject(someStateHere2)); 
// does it contain object? 
bloomFilter.contains(new SomeObject(someStateHere3)); 

Answer 5

Я написал short post о реализации цветения фильтра с использованием Java 8 функций, которые я надеюсь, что имеет отношение к вопросу экономии пространства. Я пошел bit further, чтобы обсудить, как бить срез коллекции фильтров цветения, когда некоторые информационно-поисковые системы сделают это, что имеет отношение к эффективности, когда у вас много фильтров цветения.