Filtro de Bloom: de certeza que não ou provavelmente sim

Cada palavra coloca k bits a 1 numa sequência de m bits. Para pesquisar uma palavra, verificam-se os seus k bits: basta um 0 para provar que nunca foi inserida; se todos forem 1, só podemos dizer que provavelmente foi. Insira as palavras passo a passo e depois escreva uma palavra à sua escolha.

Exemplo resolvido — Filtro de Bloom: de certeza que não ou provavelmente sim

Bits a 1	20 de 64 (31,3%)
Bits por palavra	8,00
Melhor k segundo a estimativa habitual	5,55
Estimativa habitual da taxa de falsos positivos	3,06%
Estimativa a partir dos bits realmente a 1	3,05%
Medição em 10.000 cadeias nunca inseridas	335 de 10.000 (3,35%)

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

Um filtro de Bloom permite verificar se um elemento pertence a um conjunto, usando uma sequência de m bits e k funções de dispersão. Ao inserir um elemento, colocam-se a 1 os k bits nas posições indicadas pelas funções. A pesquisa verifica os mesmos k bits: se algum estiver a 0, o elemento de certeza que não pertence ao conjunto; se todos estiverem a 1, provavelmente pertence. Uma resposta “provavelmente sim” errada é um falso positivo. Após a inserção de n elementos, a estimativa habitual da taxa de falsos positivos é (1 − e^−kn/m)^k, uma aproximação exponencial da fórmula que Bloom apresentou em 1970. O seu mínimo ocorre em k = (m/n) ln 2.

O que significa cada símbolo

m: o número de bits do filtro
k: o número de funções de dispersão e, portanto, de bits que cada palavra coloca a 1 e que cada pesquisa verifica
n: o número de palavras inseridas
X: o número de bits a 1 depois de inseridas as n palavras

Pressupõe: As k posições de uma palavra são obtidas por dispersão dupla, a partir de dois valores de dispersão: a posição i é (h₁ + i·h₂) mod m. O valor h₁ resulta da função FNV-1a aplicada à palavra; h₂ resulta da função djb2, com uma mistura adicional e ajustado para ser ímpar. Como m é uma potência de dois, as k posições de cada palavra são sempre distintas. A estimativa habitual trata cada uma das kn posições como uma escolha aleatória independente. A dispersão dupla e um m pequeno fazem com que o filtro real se afaste desse pressuposto. A taxa de falsos positivos é medida nas 10 000 cadeias de caracteres de 0 a 9999: é exata para essas cadeias, mas não para todas as palavras possíveis.

Dezasseis funções de dispersão dão piores resultados do que uma 🖖

Prima Cinco funções e leia a tabela por baixo dos resultados. Com 128 bits e 16 palavras, 1 função de dispersão deixa passar 12,82% das cadeias nunca inseridas; com 5 passam 2,50%, o menor valor da coluna; com 16 passam 32,01%, um resultado pior do que com 1. Cada função adicional obriga a pesquisa a verificar mais um bit, o que ajuda, mas também coloca mais um bit a 1 em cada inserção, o que prejudica. De 1 a 5, a taxa desce a cada passo. A partir daí sobe, com uma pequena descida em 15. Bloom identificou o ponto de viragem em 1970: ocorre quando cerca de metade dos bits estão a 1. Com 5 funções de dispersão, estão a 1 precisamente 60 destes 128 bits, e a estimativa habitual dá como melhor valor k = (m/n) ln 2 = 8 × 0,693 = 5,55.

Contar os bits a 1 melhora a estimativa habitual 🖖

Prima Dezasseis funções. A estimativa habitual indica 9,76%; o filtro deixa passar 32,01%. A estimativa pressupõe que estão a 1 cerca de 128 × (1 − e⁻²) = 110,7 bits, mas estas 16 palavras colocam 119 bits a 1. Elevando a fração realmente ocupada à potência 16, (119/128)¹⁶, obtém-se 31,15%, um valor próximo da medição. Com um k tão elevado, uns poucos bits a 1 a mais têm grande peso, porque todos os 16 bits verificados têm de estar a 1. Entre as configurações desta página que produzem algum falso positivo, a estimativa baseada nos bits realmente a 1 é a mais próxima da taxa medida em 5 356 de 6 051 casos, quando a proximidade se avalia pela razão entre a estimativa e a medição. Um filtro real pode contar os seus próprios bits a 1 e, assim, estimar a sua taxa melhor do que a fórmula habitual. Estas 16 palavras de animais também formam um conjunto pouco favorável: com outros 150 conjuntos de 16 palavras, um filtro deste tamanho apresenta uma taxa média de 14,4%, ainda acima da estimativa.

Elimina-se uma palavra e outra desaparece 🖖

Prima Eliminar owl e avance até ao fim. A palavra owl colocou a 1 os bits 37, 58 e 15. A palavra fox, inserida a seguir, usou as posições 14, 15 e 16 e encontrou o bit 15 já a 1. Ao colocar os bits de owl a 0, coloca-se também a 0 o bit 15 de fox. A pesquisa de fox devolve então “de certeza que não”, embora a palavra esteja no filtro. É um falso negativo, o único erro que um filtro de Bloom garante nunca cometer. Um bit regista apenas que alguma palavra o colocou a 1, sem guardar qual foi; por isso, não é seguro repô-lo a 0. Neste filtro de 64 bits, a eliminação de seis das oito palavras faria desaparecer também outra palavra. A solução habitual consiste em guardar um pequeno contador em cada posição, em vez de um bit, somando 1 na inserção e subtraindo 1 na eliminação. Isso exige mais memória.

Quantos bits bastariam para o filtro de translineação de Bloom, de 1970? 4 passos
Em 1970, Burton Bloom apresentou o exemplo de um programa de translineação para 500 000 palavras. Algumas regras simples permitem dividir 450 000 dessas palavras no fim da linha; as restantes 50 000 têm de ser consultadas num dicionário em disco. Bloom propôs manter na memória principal um filtro dessas 50 000 palavras, aceitando que 1 em cada 16 palavras de divisão simples provocasse um acesso desnecessário ao disco. De quantos bits precisa o filtro, quantas funções de dispersão deve usar e quantas leituras do disco continuam a ser necessárias? Depois, configure esta página com o mesmo número de bits por palavra e faça a medição.

Abrir este problema na ferramenta
1. Com o melhor valor de k, a estimativa habitual exige log₂(1/p) / ln 2 bits por palavra. Para p = 1/16, obtém-se 4 / 0,6931 = 5,77 bits por palavra, pelo que o filtro ocupa 50 000 × 5,77 = 288 539 bits. O próprio Bloom indicou “menos de 300 000 bits”. O melhor k é 5,77 × ln 2 = 4; com 4 funções de dispersão, espera-se que metade dos bits estejam a 1.
  
  $\frac{lo g _{2} 16}{ln 2} = \frac{4}{0.6931} = 5.77 bits per word, 50000 \times 5.77 = 288539 bits, k = 5.77 \times ln 2 = 4$
2. As 50 000 palavras de divisão difícil continuam a exigir uma leitura do disco. A estas juntam-se 1 em cada 16 palavras de divisão simples, ou seja, mais 450 000 / 16 = 28 125 leituras. São 78 125 leituras do disco para 500 000 palavras, ou 15,6%. Bloom arredondou o resultado para 78 000, uma redução de 84% em relação à consulta do disco para todas as palavras.
  
  $50000 + \frac{450 000}{16} = 78125 disk reads of 500000 (15.6%)$
3. O comprimento da palavra não entra nestes cálculos. O filtro ocupa 5,77 bits por palavra, quer a palavra seja “cat” ou “incomprehensibilities”. Já uma tabela de dispersão convencional, segundo os cálculos de Bloom, precisava em média de pelo menos 19 bits para representar cada palavra. Cada redução de p para metade acrescenta 1 / ln 2 = 1,44 bits por palavra: para 1 em 64, seriam 6 / 0,6931 = 8,66.
  
  $\frac{1}{l n 2} = 1.44 bits per halving of p, \frac{6}{0.6931} = 8.66 for p = \frac{1}{64}$
4. Esta página permite inserir até 64 palavras, mas a estimativa depende apenas de m/n e de k. Defina m = 256, n = 44 (5,82 bits por palavra) e k = 4. Dos 256 bits, 122 estão a 1, ou seja, 47,7%. Das 10 000 cadeias nunca inseridas, 535 recebem a resposta “provavelmente sim”: 5,35%, abaixo de 1/16 = 6,25%, a taxa para a qual o filtro foi dimensionado. A estimativa habitual para este filtro é de 6,11%.
  
  $\frac{256}{44} = 5.82 : \frac{535}{10 000} = 5.35% < \frac{1}{16} = 6.25%$
Resposta

288 539 bits e 4 funções de dispersão, com 78 125 leituras do disco para 500 000 palavras. Com as 44 palavras da página em 256 bits, a taxa medida é de 5,35%, dentro do objetivo. Este resultado corresponde a um filtro de 44 palavras. A página não permite verificar se 50 000 palavras em 288 539 bits produziriam uma taxa igualmente próxima de 1/16, pois está limitada a 64 palavras.

$288539 bits, k = 4, 78125 disk reads$

Percurso de aprendizagem

Referências (1)

The method itself, the turning point at half the bits set in the first insight, and the hyphenation example the worked problem recomputes: Burton H. Bloom, "Space/time trade-offs in hash coding with allowable errors," Communications of the ACM 13(7), July 1970, pp. 422–426.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.

Filtro de Bloom: de certeza que não ou provavelmente sim

A teoria — Filtro de Bloom: de certeza que não ou provavelmente sim

O que significa cada símbolo

Dezasseis funções de dispersão dão piores resultados do que uma 🖖

Contar os bits a 1 melhora a estimativa habitual 🖖

Elimina-se uma palavra e outra desaparece 🖖

Problema resolvido na íntegra

O que custa pouco numa estrutura de dados