javascript-algorithms

Filtro Bloom (Bloom Filter)

O bloom filter é uma estrutura de dados probabilística espaço-eficiente designada para testar se um elemento está ou não presente em um conjunto de dados. Foi projetado para ser incrivelmente rápido e utilizar o mínimo de memória ao potencial custo de um falso-positivo. Correspondências falsas positivas são possíveis, contudo falsos negativos não são - em outras palavras, a consulta retorna “possivelmente no conjunto” ou “definitivamente não no conjunto”.

Bloom propôs a técnica para aplicações onde a quantidade de entrada de dados exigiria uma alocação de memória impraticavelmente grande se as “convencionais” técnicas error-free hashing fossem aplicado.

Descrição do algoritmo

Um filtro Bloom vazio é um bit array de m bits, todos definidos como 0. Também deverá haver diferentes funções de hash k definidas, cada um dos quais mapeia e produz hash para um dos elementos definidos em uma das posições m da array, gerando uma distribuição aleatória e uniforme. Normalmente, k é uma constante, muito menor do que m, pelo qual é proporcional ao número de elements a ser adicionado; a escolha precisa de k e a constante de proporcionalidade de m são determinadas pela taxa de falsos positivos planejado do filtro.

Aqui está um exemplo de um filtro Bloom, representando o conjunto {x, y, z}. As flechas coloridas demonstram as posições no bit array em que cada elemento é mapeado. O elemento w não está definido dentro de {x, y, z}, porque este produz hash para uma posição de array de bits contendo 0. Para esta imagem: m = 18 e k = 3.

Bloom Filter

Operações

Existem duas operações principais que o filtro Bloom pode operar: inserção e pesquisa. A pesquisa pode resultar em falsos positivos. Remoção não é possível.

Em outras palavras, o filtro pode receber itens. Quando vamos verificar se um item já foi anteriormente inserido, ele poderá nos dizer “não” ou “talvez”.

Ambas as inserções e pesquisas são operações O(1).

Criando o filtro

Um filtro Bloom é criado ao alocar um certo tamanho. No nosso exemplo, nós utilizamos 100 como tamanho padrão. Todas as posições são initializadas como false.

Inserção

Durante a inserção, um número de função hash, no nosso caso 3 funções de hash, são utilizadas para criar hashes de uma entrada. Estas funções de hash emitem saída de índices. A cada índice recebido, nós simplismente trocamos o valor de nosso filtro Bloom para true.

Pesquisa

Durante a pesquisa, a mesma função de hash é chamada e usada para emitir hash da entrada. Depois nós checamos se todos os indices recebidos possuem o valor true dentro de nosso filtro Bloom. Caso todos possuam o valor true, nós sabemos que o filtro Bloom pode ter tido o valor inserido anteriormente.

Contudo, isto não é certeza, porque é possível que outros valores anteriormente inseridos trocaram o valor para true. Os valores não são necessariamente true devido ao ítem atualmente sendo pesquisado. A certeza absoluta é impossível, a não ser que apenas um item foi inserido anteriormente.

Durante a checagem do filtro Bloom para índices retornados pela nossa função de hash, mesmo que apenas um deles possua valor como false, nós definitivamente sabemos que o ítem não foi anteriormente inserido.

Falso Positivos

A probabilidade de falso positivos é determinado por três fatores: o tamanho do filtro de Bloom, o número de funções de hash que utilizados, e o número de itens que foram inseridos dentro do filtro.

A formula para calcular a probabilidade de um falso positivo é:

( 1 - e -kn/m ) k

k = número de funções de hash

m = tamanho do filtro

n = número de itens inserido

Estas variáveis, k, m e n, devem ser escolhidas baseado em quanto aceitável são os falsos positivos. Se os valores escolhidos resultam em uma probabilidade muito alta, então os valores devem ser ajustados e a probabilidade recalculada.

Aplicações

Um filtro Bloom pode ser utilizado em uma página de Blog. Se o objetivo é mostrar aos leitores somente os artigos em que eles nunca viram, então o filtro Bloom é perfeito para isso. Ele pode armazenar hashes baseados nos artigos. Depois que um usuário lê alguns artigos, eles podem ser inseridos dentro do filtro. Na próxima vez que o usuário visitar o Blog, aqueles artigos poderão ser filtrados (eliminados) do resultado.

Alguns artigos serão inevitavelmente filtrados (eliminados) por engano, mas o custo é aceitável. Tudo bem se um usuário nunca ver alguns poucos artigos, desde que tenham outros novos para ver toda vez que eles visitam o site.

Referências