Filtro Bloom
Um filtro Bloom é uma estrutura de dados que permite aos computadores ver se um determinado elemento ocorre em um conjunto. Os filtros Bloom usam funções hash para fazer isso. Para cada elemento que é adicionado, um valor de hash é calculado. Quando um novo elemento é adicionado, seu valor de hash é comparado com o dos outros elementos do conjunto. Um filtro Bloom é uma estrutura de dados probabilística. É possível obter um falso positivo, mas não um falso negativo. Em outras palavras, uma consulta retorna ou "possivelmente no conjunto" ou "definitivamente não no conjunto". Elementos podem ser adicionados ao conjunto, mas não removidos. Para cada elemento adicionado, a probabilidade de obter um falso positivo aumenta.
Edward Bloom propôs o filtro Bloom em 1970. No artigo, Bloom supõe que haja um algoritmo para hifenizar as palavras no final de uma linha. De acordo com o exemplo, a maioria das palavras tem padrões simples de hifenização. Mas cerca de 10% das palavras requerem pesquisas demoradas para que se obtenha a regra correta. Seu caso foi o de hifenizar cerca de 500.000 palavras. Ele viu que a utilização das técnicas de hifenização "normais" sem erros, armazenando os padrões de hifenização, exigiria muita memória. Ele descobriu que, usando sua técnica, ele poderia eliminar a maioria das buscas. Por exemplo, uma área de hash com apenas 15% do tamanho necessário para um hash ideal livre de erros ainda elimina 85% dos acessos ao disco.
Mais geralmente, são necessários menos de 10 bits por elemento para uma probabilidade falsa positiva de 1%, independente do tamanho ou do número de elementos do conjunto.
Perguntas e Respostas
P: O que é um filtro Bloom?
R: Um filtro Bloom é uma estrutura de dados que permite aos computadores ver se um determinado elemento ocorre em um conjunto. Ele usa funções hash para fazer isso, calculando o valor hash de cada elemento adicionado e comparando-o com os outros elementos do conjunto.
P: Que tipo de estrutura de dados é um filtro Bloom?
R: Um filtro Bloom é uma estrutura de dados probabilística, o que significa que há uma possibilidade de obter falsos positivos, mas não falsos negativos.
P: Quem propôs o filtro Bloom?
R: Edward Bloom propôs o filtro Bloom em 1970.
P: Qual foi o exemplo do Edward para usar sua técnica?
R: O exemplo de Edward foi hifenizar cerca de 500.000 palavras; ele descobriu que usando sua técnica, ele poderia eliminar a maioria das consultas e reduzir em 15% os acessos ao disco.
P: Quantos bits por elemento são necessários para 1% de falsa probabilidade positiva?
R: Menos de 10 bits por elemento são necessários para 1% de probabilidade de falso positivo, independente do tamanho ou do número de elementos do conjunto.
P: É possível remover elementos de um filtro de florescimento uma vez que eles tenham sido adicionados?
R: Não, os elementos só podem ser acrescentados ao conjunto, mas não removidos.
P: A adição de mais elementos aumenta ou diminui a probabilidade de se obter um resultado falso positivo?
R: A adição de mais elementos aumenta a probabilidade de se obter um resultado falso positivo.
