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.


AlegsaOnline.com - 2020 / 2022 - License CC3