Filtros de Bloom em R

Por Daniel 18/09/2017

Filtro de Bloom é um algoritmo muito interessante para testar se um elemento pertence a um conjunto. Ele é considerado uma estrutura de dados probabilística, ou seja, o resultado pode não estar correto com alguma probabilidade. Especificamente para o filtro de bloom, existe a possibilidade de falsos positivos mas não de falsos negativos: o algoritmo pode dizer que o elemento pertence ao conjunto, mas na verdade não pertencer, mas nunca dirá que ele não pertence sendo que ele pertence.

Bloom Filters são úteis em diversas situações, geralmente relacionadas ao ganho de velocidade e de espaço que o seu uso pode trazer. Muitos sistemas de bancos de dados usam bloom filters para reduzir o número de buscas no disco (ex. Cassandra). O Medium usa para evitar recomendar uma paǵina que você já leu. Recentemente, encontraram até aplicações para bloom filters em machine learning.

Nesse post vamos implementar uma versão simplificada, nada otimizada dos filtros de Bloom em R. Mas antes disso, vale a pena ler o verbete da Wikipedia sobre o assunto.

Essencialmente, um filtro de bloom é um vetor de TRUEs e FALSES de tamanho \(m\). Inicializamos esse vetor com FALSES. Em seguida para cada elemento do conjunto que você deseja representar pelo filtro, repetimos o seguinte processo: Hasheamos o elemento usando \(k\) funções de hash diferentes. Cada uma dessas funções indicará um elemento do vetor que deve ser marcado como TRUE. Armazenamos então esse vetor de bits. São os valores de \(m\) e de \(k\) que controlam a probabilidade de falsos positivos.

Veja como podemos criar uma função em R para fazer essas operações. Essa função inicializa o vetor de bits de tamanho \(m\) com FALSES e em seguida, para cada uma das \(k\) funções de hash (no caso apenas variamos a semente do hash MurMur32) e para cada elemento de x calculamos o elemento do vetor vec que deve se tornar TRUE. No final, ela retorna o vetor vec, onde armazenamos como atributos os parâmetros usados na sua construção.

library(digest)
library(magrittr)

criar_vetor_de_bits <- function(x, m = 1000, k = 7){
  
  vec <- rep(FALSE, m)
  
  for (i in 1:k) {
    for (j in 1:length(x)) {
      
      hash <- digest(x[j], algo = "murmur32", serialize = FALSE, seed = i) %>%
        Rmpfr::mpfr(base = 16) %% 
        m %>% 
        as.integer()
      
      vec[hash + 1] <- TRUE
      
    }
  }
  
  # armazenamos os parâmetros usados na construção
  attributes(vec) <- list(m = m, k= k)
  
  return(vec)
}

Dado um conjunto de strings, podemos criar o vetor de bits que o representa.

vect <- criar_vetor_de_bits(c("eu", "pertenco", "ao", "conjunto", "de",
                              "strings"), m = 1000, k = 7)

Agora vamos definir uma função que verifica se uma string pertence ao conjunto, dada apenas a representação dos bits desse conjunto. Hasheamos o elemento que desejamos verificar a presença no conjunto com a primeira função de hash. Se ela indicar um elemento do vetor que já está marcado com TRUE então continuamos, se não, retorna FALSE indicando que o elemento não pertence ao conjunto. Continuamos até acabarem as funções de hash ou até 1 FALSE ter sido retornado.

verificar_presenca <- function(x, vetor_de_bits){
  
  k <- attr(vetor_de_bits, "k")
  m <- attr(vetor_de_bits, "m")
  
  for(i in 1:k){
    hash <- digest(x, algo = "murmur32", serialize = FALSE, seed = i) %>%
        Rmpfr::mpfr(base = 16) %% 
        m %>% 
        as.integer()
    
    if(!vetor_de_bits[hash + 1]) {
      return(FALSE)
    }
  }
  return(TRUE)
}

verificar_presenca("nao", vect)
verificar_presenca("eu", vect)
verificar_presenca("abc", vect)

Com m = 1000 e k = 7 não consegui encontrar nenhum falso positivo, mas basta diminuir o tamanho de m e de k que encontraremos. No verbete da Wikipedia a conta está bonitinha mas de fato a probabilidade de falsos positivos pode ser estimada em função dos parâmetros \(k\) e \(m\) e \(n\) (tamanho do conjunto representado) é dada por

\[(1 - e^{-kn/m})^k\]

No caso apresentado, a probabilidade de colisão é de 1.991256e-10.

comments powered by Disqus