Я создал фильтр Блума, используя 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 точек данных.