Блум фильтр дизайн - PullRequest
Новая
       49

Блум фильтр дизайн

1 голос
/ 08 января 2012

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

Кроме того, у меня есть следующие вопросы:
1) Известно, что фильтр Блума имеет ложные срабатывания.Можно ли уменьшить их, используя два фильтра, один для использованных элементов и один для неиспользуемых элементов (при условии, что набор конечен и известен априори), и сравнить два?
2) существуют ли другие подобные алгоритмыв литературе по КС?

Ответы [ 4 ]

1 голос
/ 08 января 2012

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

Что касается ресурсов, то в ссылках на документына 8 марта с мой учебный план будет полезен.

0 голосов
/ 06 ноября 2017

Очень легко реализовать фильтр Блума с использованием функций Java 8.Вам просто нужно long[] для хранения битов и несколько хеш-функций, которые вы можете представить с помощью ToIntFunction<T>.Я кратко написал о , делающем это с нуля .

Осторожнее всего выбрать правильный бит из массива. 

public class BloomFilter<T> {

     private final long[] array;
     private final int size;
     private final List<ToIntFunction<T>> hashFunctions;

     public BloomFilter(long[] array, int logicalSize, List<ToIntFunction<T>> hashFunctions) {
         this.array = array;
         this.size = logicalSize;
         this.hashFunctions = hashFunctions;
     }

     public void add(T value) {
         for (ToIntFunction<T> function : hashFunctions) {
              int hash = mapHash(function.applyAsInt(value));
              array[hash >>> 6] |= 1L << hash;
         }
     }

     public boolean mightContain(T value) {
         for (ToIntFunction<T> function : hashFunctions) {
              int hash = mapHash(function.applyAsInt(value));
              if ((array[hash >>> 6] & (1L << hash)) == 0) {
                   return false;
              }
         }
         return true;
    }

    private int mapHash(int hash) {
         return hash & (size - 1);
    }


    public static <T> Builder<T> builder() {
         return new Builder<>();
    }

    public static class Builder<T> {
         private int size;
         private List<ToIntFunction<T>> hashFunctions;

         public Builder<T> withSize(int size) {
             this.size = size;
             return this;
         }

         public Builder<T> withHashFunctions(List<ToIntFunction<T>> hashFunctions) {
              this.hashFunctions = hashFunctions;
              return this;
          }

         public BloomFilter<T> build() {
              return new BloomFilter<>(new long[size >>> 6], size, hashFunctions);
         }
     }  
}
0 голосов
/ 06 июня 2014

Я думаю, что мы должны посмотреть на применение Bloom Filters, и секрет в названии, это Фильтр, а не структура данных.Он в основном используется для сохранения ресурсов путем проверки, не являются ли элементы частью набора.Если вы хотите свести к минимуму ложные срабатывания до 0, вам нужно будет вставить все элементы, которые не входят в набор, поскольку для хорошо спроектированного фильтра Блума нет ложных негативов, за исключением того, что фильтр Блума будет гигантским и непрактичным,с таким же успехом можно просто хранить элементы в пропущенном списке :) Я написал простое руководство по Bloom Filters, если кому-то интересно.

http://techeffigy.wordpress.com/2014/06/05/bloom-filter-tutorial/

0 голосов
/ 18 декабря 2013

Java-реализацию фильтра Блума можно найти в здесь . Если вы не можете просмотреть его, я вставлю код в следующем (с комментариями на китайском языке). 

import java.util.BitSet;

publicclass BloomFilter 
{
    /* BitSet初始分配2^24个bit */ 
    privatestaticfinalint DEFAULT_SIZE =1<<25; 
    /* 不同哈希函数的种子，一般应取质数 */
    privatestaticfinalint[] seeds =newint[] { 5, 7, 11, 13, 31, 37, 61 };
    private BitSet bits =new BitSet(DEFAULT_SIZE);
    /* 哈希函数对象 */ 
    private SimpleHash[] func =new SimpleHash[seeds.length];

    public BloomFilter() 
    {
        for (int i =0; i < seeds.length; i++)
        {
            func[i] =new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    // 将字符串标记到bits中
    publicvoid add(String value) 
    {
        for (SimpleHash f : func) 
        {
            bits.set(f.hash(value), true);
        }
    }

    //判断字符串是否已经被bits标记
    publicboolean contains(String value) 
    {
        if (value ==null) 
        {
            returnfalse;
        }
        boolean ret =true;
        for (SimpleHash f : func) 
        {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /* 哈希函数类 */
    publicstaticclass SimpleHash 
    {
        privateint cap;
        privateint seed;

        public SimpleHash(int cap, int seed) 
        {
            this.cap = cap;
            this.seed = seed;
        }

        //hash函数，采用简单的加权和hash
        publicint hash(String value) 
        {
            int result =0;
            int len = value.length();
            for (int i =0; i < len; i++) 
            {
                result = seed * result + value.charAt(i);
            }
            return (cap -1) & result;
        }
    }
}

С точки зрения проектирования фильтра Блума, число хеш-функций, необходимых для фильтра Блума, можно определить, как в здесь , также ссылаясь на статью Википедии о фильтрах Блума , затем вы найдете сечение Вероятность ложных срабатываний . В этом разделе объясняется, как количество хеш-функций влияет на вероятности ложных срабатываний, и дается формула для определения k из требуемой ожидаемой вероятности. ложных срабатываний.

Цитата из статьи в Википедии:

Очевидно, вероятность ложного положительные значения уменьшается как м (число битов в массиве) увеличивается, и увеличивается как n (количество вставленных элементы) увеличивается. Для данного м и n, значение k (количество хэшей функции), который минимизирует вероятность

formula

...