BloomFilter Sınıfı - Nesne Var Diyorsa Yanılma İhtimali (False Positive) Bulunur

Giriş
Bloom Filter bir şeyin olmadığını bilmek için kullanılır. Bu sınıfın en önemli metodu mightContain() Açıklaması şöyle.

For a true Bloom filter, the bits only ever go from 0 to 1, never back - so the result of a mightContain call can only ever go from false to true, never back, because mightContain returns true if a certain subset of all bits are 1, and once they're 1 they'll stay 1.

Eğer nesne yok diyorsa yoktur, var diyorsa yanılma ihtimali (false positive) bulunur.

Bellek Kullanımı
Bu sınıfın tahminen ne kadar bellek kullandığını görmek için şöyle yaparız.

import static java.lang.Math.log;
import static java.lang.Math.pow;

// expected insertions
int n = 100_000_000;

// false positive probability; default: 3% for Guava
double fpp = 0.03;

double bits = n * log(fpp) / -log(pow(2, log(2)));
int bytes = (int) Math.ceil(bits / 8);

// result for the above: 91230511

create metodu
İkinci parametre expected insertions anlamına gelir. Örneğin 1 milyon nesneyi filtreye ekleyeceksek bu değeri 1 milyon vermek gerekir. Açıklaması şöyle.

When we design our Bloom filter, it is important that we provide a reasonably accurate value for the expected number of elements. Otherwise, our filter will return false positives at a much higher rate than desired. 

Örnek- String
Üçüncü parametre false positive probability anlamına gelir. False positive nesne varmış gibi gösterir ancak aslında yoktur. Bu değeri örneğin 0.01 verirsek yüzde 1 ihtimalle false positive alabiliriz. Yüzde 99 ise sonuçtan emin olabiliriz. Açıklaması şöyle.

The only guarantee BloomFilter provides is that the true false positive probability is at most the value you set. In some cases, the nature of the Bloom Filter data structure may have to "round" the actual FPP down.

Örnek- String
Şöyle yaparız.

BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.
  stringFunnel(StandardCharsets.UTF_8), 100_000_000);

Örnek - Integer
Şöyle yaparız.

BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), 500, 0.01);

Örnek - Long
Şöyle yaparız.

BloomFilter<Long> filter = BloomFilter.create(Funnels.longFunnel(), 1_000_000, .001);

mightContain metodu
- true dönerse nesne var veya yoktur diyemeyiz false positive olabilir, yani false positive probability kadar yanılma ihtimalimiz vardır.
- false dönerse nesne yoktur.

put metodu
- true dönerse nesne yoktur ve ilk defa ekleniyordur anlamına gelir.
- false dönerse nesne var veya yok diyemeyiz, false positive olabilir.
Örnek

Şöyle yaparız. Bu örnekte false dönerse nesne var veya yok olabilir.

if (!bloomFilter.put(Long.valueOf(i))) {
  // There is no duplicated elements so put returns false means false-positive
}

Örnek

Şöyle yaparız

BloomFilter<Integer> filter = BloomFilter.create(
            Funnels.integerFunnel(),
            500,
            0.01);
for (int i=0; i<400; i++) {
  filter.put(i);
}

readFrom metodu

Örnek

Şöyle yaparız

BloomFilter<Integer> filter = ...;

ByteArrayOutputStream out = new ByteArrayOutputStream();
filter.writeTo(out);

ByteArrayInputStream in = new ByteArrayInputStream(out.toByteArray());
BloomFilter<Integer> filter1 = BloomFilter.readFrom(in, Funnels.integerFunnel());

writeTo metodu
Örnek

Şöyle yaparız.

BloomFilter<String> bloomFilter = ...;
ByteArrayOutputStream baos = new ByteArrayOutputStream();
bloomFilter.writeTo(baos);
System.out.println(baos.toByteArray().length);