Фильтры Блума: частота ошибок выше, чем ожидалось

Я создал фильтр Блума, используя murmur3, blake2b и оптимизацию Кирша-Митценмахера, как описано во втором ответе на этот вопрос: Какие хеш-функции использовать в фильтре Блума

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

Вот код, который я использовал для создания фильтров Блума:

public class BloomFilter {
private BitSet filter;
private int size;
private int hfNum;
private int prime;
private double fp = 232000; //One false positive every fp items

public BloomFilter(int count) {
    size = (int)Math.ceil(Math.ceil(((double)-count) * Math.log(1/fp))/(Math.pow(Math.log(2),2)));
    hfNum = (int)Math.ceil(((this.size / count) * Math.log(2)));
    //size = (int)Math.ceil((hfNum * count) / Math.log(2.0));
    filter = new BitSet(size);

    System.out.println("Initialized filter with " + size + " positions and " + hfNum + " hash functions.");
}

public BloomFilter extraSecure(int count) {
    return new BloomFilter(count, true);
}

private BloomFilter(int count, boolean x) {
    size = (int)Math.ceil((((double)-count) * Math.log(1/fp))/(Math.pow(Math.log(2),2)));
    hfNum = (int)Math.ceil(((this.size / count) * Math.log(2)));
    prime = findPrime();
    size = prime * hfNum;
    filter = new BitSet(prime * hfNum);

    System.out.println("Initialized filter with " + size + " positions and " + hfNum + " hash functions.");
}

public void add(String in) {
    filter.set(getMurmur(in), true);
    filter.set(getBlake(in), true);

    if(this.hfNum > 2) {
        for(int i = 3; i <= (hfNum); i++) {
            filter.set(getHash(in, i));
        }
    }
}

public boolean check(String in) {
    if(!filter.get(getMurmur(in)) || !filter.get(getBlake(in))) {
        return false;
    }

    for(int i = 3; i <= hfNum; i++) {
        if(!filter.get(getHash(in, i))) {
            return false;
        }
    }

    return true;
}

private int getMurmur(String in) {
    int temp = murmur(in) % (size);

    if(temp < 0) {
        temp = temp * -1;
    }

    return temp;
}

private int getBlake(String in) {
    int temp = new BigInteger(blake256(in), 16).intValue() % (size);

    if(temp < 0) {
        temp = temp * -1;
    }

    return temp;
}

private int getHash(String in, int i) {
    int temp = ((getMurmur(in)) + (i * getBlake(in))) % size;
    return temp;
}

private int findPrime() {
    int temp;

    int test = size;
    while((test * hfNum) > size ) {
        temp = test - 1;
        while(!isPrime(temp)) {
            temp--;
        }
        test = temp;
    }

    if((test * hfNum) < this.size) {
        test++;
        while(!isPrime(test)) {
            test++;
        }
    }

    return test;
}

private static boolean isPrime(int num) {
    if (num < 2) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;
    for (int i = 3; i * i <= num; i += 2)
        if (num % i == 0) return false;
    return true;
}

@Override
public String toString() {
    final StringBuilder buffer = new StringBuilder(size);
    IntStream.range(0, size).mapToObj(i -> filter.get(i) ? '1' : '0').forEach(buffer::append);
    return buffer.toString();
}

}

Вот код, который я использую для проверки:

public static void main(String[] args) throws Exception {
    int z = 0;
    int times = 10;
    while(z < times) {
        z++;
        System.out.print("\r");
        System.out.print(z);


        BloomFilter test = new BloomFilter(4000);

        SecureRandom random = SecureRandom.getInstance("SHA1PRNG");
        for(int i = 0; i < 4000; i++) {
            test.add(blake256(Integer.toString(random.nextInt())));
        }

        int temp = 0;
        int count = 1;
        while(!test.check(blake512(Integer.toString(temp)))) {
            temp = random.nextInt();
            count++;
        }

        if(z == (times)) {
            Files.write(Paths.get("counts.txt"), (Integer.toString(count)).getBytes(), StandardOpenOption.APPEND);
        }else {
            Files.write(Paths.get("counts.txt"), (Integer.toString(count) + ",").getBytes(), StandardOpenOption.APPEND);
        }

        if(z == 1) {
            Files.write(Paths.get("counts.txt"), (Integer.toString(count) + ",").getBytes());
        }

    }
}

Я ожидаю получить значение, относительно близкое к переменной fp в классе фильтра Блума, но вместо этого часто получаю половину этого значения. Кто-нибудь знает, что я делаю неправильно, или это нормально?

РЕДАКТИРОВАТЬ: Чтобы показать, что я имею в виду под высокой частотой ошибок, когда я запускаю код на фильтре, инициализированном счетчиком 4000 и fp 232000, это был вывод с точки зрения того, сколько чисел должен был пройти фильтр, прежде чем он обнаружил ложное срабатывание. :

158852,354114,48563,76875,156033,82506,61294,2529,82008,32624

Это было сгенерировано с использованием метода extraSecure() для инициализации и повторено 10 раз, чтобы сгенерировать эти 10 чисел; всем, кроме одного, потребовалось менее 232000 сгенерированных значений, чтобы найти ложное срабатывание. Среднее значение из 10 составляет около 105 540, и это обычное дело, независимо от того, сколько раз я повторяю этот тест.

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


person Lev Knoblock    schedule 18.03.2018    source источник


Ответы (2)


Боюсь не знаю где баг, но можно многое упростить. На самом деле вам не нужен простой размер, вам не нужны SecureRandom, BigInteger и модуль. Все, что вам нужно, это хороший 64-битный хэш (если возможно, заполненный, например бормотание):

long bits = (long) (entryCount * bitsPerKey);
int arraySize = (int) ((bits + 63) / 64);
long[] data = new long[arraySize];
int k = getBestK(bitsPerKey);

void add(long key) {
    long hash = hash64(key, seed);
    int a = (int) (hash >>> 32);
    int b = (int) hash;
    for (int i = 0; i < k; i++) {
        data[reduce(a, arraySize)] |= 1L << index;
        a += b;
    }
}

boolean mayContain(long key) {
    long hash = hash64(key, seed);
    int a = (int) (hash >>> 32);
    int b = (int) hash;
    for (int i = 0; i < k; i++) {
        if ((data[reduce(a, arraySize)] & 1L << a) == 0) {
            return false;
        }
        a += b;
    }
    return true;
}

static int reduce(int hash, int n) {
    // http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
    return (int) (((hash & 0xffffffffL) * n) >>> 32);
}

static int getBestK(double bitsPerKey) {
    return Math.max(1, (int) Math.round(bitsPerKey * Math.log(2)));
}
person Thomas Mueller    schedule 12.11.2018

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

В комментарии говорилось:

в статье hash_i = hash1 + i x hash2 % p, где p — простое число, hash1 и hash2 находятся в диапазоне [0, p-1], а набор битов состоит из k * p битов.

Однако просмотр статьи показывает, что, хотя все хэши имеют модификацию p, каждой хеш-функции назначается подмножество общего набора битов, что, как я понял, означает, что хэш1 по модулю p будет определять значение для индексов от 0 до p, хеш2 по модулю p будет определить значение для индексов от p до 2*p и т. д. и т. д., пока не будет достигнуто значение k, выбранное для набора битов.

Я не уверен на 100%, что добавление этого исправит мой код, но попробовать стоит. Я обновлю это, если это сработает.

ОБНОВЛЕНИЕ: не помогло. Я смотрю, что еще может быть причиной этой проблемы.

person Lev Knoblock    schedule 19.03.2018