Calculadora de Filtro de Bloom (Tamanho, Funções de Dispersão, Taxa de Falsos Positivos)

O que faz esta ferramenta

Um filtro de Bloom responde a «este elemento está no conjunto?» com «de certeza que não» ou «provavelmente sim», usando um pequeno vetor de bits e várias funções de dispersão. Para n elementos e uma taxa de falsos positivos p, o tamanho ótimo é m = −n ln p ÷ (ln 2)² bits, e o melhor número de funções é k = (m ÷ n) ln 2, o que dá cerca de 1,44 × log₂(1 ÷ p) bits por elemento. Uma taxa de 1 % custa cerca de 9,6 bits por elemento e uma de 0,1 % cerca de 14,4, sejam quais forem os elementos. A taxa de falsos positivos sobe depressa se inserir mais elementos do que o planeado, e um filtro de Bloom normal não permite apagar.

Fórmula

m = −n ln p ÷ (ln 2)² · k = (m ÷ n) ln 2 · p = (1 − e^(−k n ÷ m))^k

Variáveis

Exemplo resolvido

Limitações

• O resultado é uma estimativa baseada apenas nos valores que introduziu. Situações reais incluem muitas vezes fatores que esta calculadora desconhece.
• A fórmula assume condições ideais: sem perdas por atrito, sem resistência do ar e sem perdas de rendimento, a não ser que as introduza.