Filtry Blooma | DevOops adventures

Dzisiaj będzie trochę bardziej nisko poziomowo (nie mylić z niższym poziomem posta). Postaram się w przystepny sposób przybliżyć wam czym jest Filtr Blooma i jak można go zaimplementować w JavaScripcie.

Filtra teorie

Filtr Blooma to struktura danych pozwalająca w sposób szybki i pamięciowo optymalny odpowiedzieć na pytanie, czy dany element znajduje się w zbiorze. Niestety, ponieważ nie ma nic za darmo, za wydajność musimy zapłacić, a zapłatą będzie błąd w jaki struktura może nas wprowadzić. Nie użyłem probabilistyczna bez powodu: filtr może stwierdzić jedynie, że elementu na pewno nie ma, lub może jest w zbiorze. Założenie to prowadzi do wniosków tzw. false-positive, czyli że dany element nie istnieje w zadanym zbiorze, a jednak otrzymamy informację o jego prawdopodobnym istnieniu.

Budowa i parametry filtra

Filtr można opisać mniej więcej tak:

Filtr Blooma to tablica (wektor) m-bitów, który ma “przewidywać” istnienie n elementów. Elementy te zostały zakodowane k funkcjami haszującymi.

Dobór tych parametrów wpływa na prawdopodobieństwo wystąpienia błędu (które chcemy minimalizować). Wikipedia bardzo ładnie przedstawia to od matematycznej strony. Najważniejsze są dwa wzory:

$k$ $m$

My do teorii aż tak wagi przywiązywać nie będziemy, ale trzeba pamiętać, że przy produkcyjnym użyciu takiej struktury bez wstępnej analizy się nie obejdzie.

Działanie filtra

Całość sprowadza się do testu, czy dany bit (lub k bitów w przypadku k > 1) dla zadanej wartości (np. x) jest zapalonych w tablicy. Jeśli choć jeden nie jest - mamy pewność, że element jest nieobecny.

Haszowanie

Orłem z kryptografii nie jestem, ale wyczytałem, że użyte funkcje haszujące powinny być przede wszystkim niezależne i o jednostajnym rozkładzie prawdopodobieństwa, np. takie jak: murmur lub fnv. Zalecam dalszą lekturę w tym zakresie dla zainteresowanych szczegółami.

Podwójne haszowanie

Jak i jakich funkcji używać do haszowania? Aby zapewnić prawdopodobieństwo błędu na podobnym poziomie, możemy skorzystać z podwójnego haszowania:

$double hash$

Będziemy potrzebować wtedy jedynie dwóch funkcji haszujących h₁ i h₂, i - numer funkcji (nasze k), T (nasze m). (Przepraszam za zamieszanie z parametrami, ale wzory są żywcem z Wikipedii).

Myślę, że powoli możemy przejść do kodu i próby zaimplementowania tego wszystkiego, co wyżej opisałem.

Implementacja

Dla celów edukacyjnych przyjmijmy następujące parametry:

k = 1    Jedna funkcja haszująca fnv-1
m = 16   16-bitowa tablica
n = 2    Dwa elementy

fnv-1

Wybrałem tę, bo jest relatywnie prosta w implementacji:

// Operacje na bitach w JS są 32-bitowe
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators
//
// Stałe dla 32-bitów
// http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param
const FNV_OFFSET = 0x811c9dc5;
const FNV_PRIME = 0x01000193;

function fnv1(string) {
  let bytes = stringToBytes(string);
  let hash = FNV_OFFSET;

  for (let byte of bytes) {
    hash = hash * FNV_PRIME;
    hash = hash ^ byte;
  }

  return Math.abs(hash);
}

stringToBytes

Powyższa funkcja potrzebuje tablicy bajtów z ciągu znaków. JS nie posiada takiej ładnej funkcji jak chociażby C# byte[] bytes = encoding.GetBytes(AnyString), dlatego musimy napisać coś podobnego. Dla ułatwienia przyjmijmy, że ciąg znaków kodowany jest w ASCII (basic English).

function stringToBytes(string) {
  let bytes = [];

  for (let char of string) {
    bytes.push(char.charCodeAt(0));
  }
  
  return bytes;
}

BloomFilter

Jak zauważyliście używam składni ES6, o co by iść z duchem czasu. Filtr będzie przyjmował w konstruktorze liczbę bitów oraz funkcje haszujące, których chcemy użyć.

class BloomFilter {
  constructor (m, k) {
    this.bits = m;
    this.hashFunctions = k;
    this.filter = new Int32Array(m);
  }

  add (value) {
    for (let hash of this.hashFunctions) {
      let hashIndex = hash(value) % this.bits;
      this.filter[hashIndex] = 1;
    }
  }

  check (value) {
    for (let hash of this.hashFunctions) {
      let hashIndex = hash(value) % this.bits;
      if (this.filter[hashIndex] == 0)
        return false;
    }
    return true;
  }
}

Testujemy!

var bloomFilter = new BloomFilter(16, [ fnv1 ]);

bloomFilter.add('testujemy!');
bloomFilter.add('filtr');

bloomFilter.check('testujemy!');
// true
bloomFilter.check('filtr');
// true
bloomFilter.check('nie ma')
// false

Prawdopodobieństwo błędu dla przyjętych parametrów wynosi: bloom p ~= 0.12

ale przy 10-ciu elementach wzrasta do p ~= 0.46, dlatego dobór odpowiednich parametrów jest bardzo ważny.

Produkcyjne użycia

Z Filtrów Blooma korzystają m.in: