Реализация фильтра Блума

Question

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

Answer 1

Вы можете понять, как это экономит место, используя этот пример: допустим, я работаю на 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-адрес вряд ли является вредоносным, небольшой фильтр Bloom в браузере обнаруживает это и, следовательно, экономит время, избегая обращений к удаленному серверу.Только в некоторых случаях, если фильтр Bloom сообщает нам, что URL МОЖЕТ быть вредоносным, только в тех случаях мы делаем вызов на сервер.Это «МОЖЕТ» правильно на 99%.

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

Answer 2

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

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

код: пакет 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

Фильтр Блума не является "структурой".Это действительно больше похоже на алгоритм.Реализация не очень длинная.

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

«Автономные Java-реализации хеширования и Bloom Filters» (вы можете обратиться в Google за этим, если следующая ссылка больше не работает):

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

Answer 4

Вы можете использовать фильтр Блума на основе 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

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