En ciencias da computación, un filtro de Bloom é unha estrutura de datos probabilística que ocupa pouco espazo, concibida por Burton Howard Bloom en 1970, e que serve para comprobar se un elemento pertence a un conxunto. Os falsos positivos son posibles, pero os falsos negativos non: unha consulta devolve «posiblemente no conxunto» ou «definitivamente non no conxunto». Os elementos pódense engadir ao conxunto, pero non retirar (aínda que isto se pode resolver coa variante do filtro de Bloom con contador); canto máis elementos se engaden, maior é a probabilidade de falsos positivos.
Bloom propuxo a técnica para aplicacións nas que a cantidade de datos de orixe requiriría unha memoria excesivamente grande se se aplicasen técnicas de hashing «convencionais» libres de erros. Deu o exemplo dun algoritmo de guionización para un dicionario de 500.000 palabras, das cales o 90 % seguen regras de guionización simples, pero o 10 % restante require custosos accesos a disco. Cunha área hash de só o 18 % do tamaño necesario para un hash ideal sen erros, a técnica de Bloom elimina o 87 % dos accesos a disco.
En xeral, para unha probabilidade de falso positivo do 1 % requírense menos de 10 bits por elemento, independentemente do tamaño ou do número de elementos do conxunto.
Descrición do algoritmo Un filtro de Bloom baleiro é un vector de bits de bits, todos a 0. Está equipado con funcións hash distintas, que asignan os elementos do conxunto a unha das posicións posibles do vector. Para ser óptimas, as funcións hash deberían estar uniformemente distribuídas e ser independentes. Tipicamente, é unha constante pequena que depende da taxa de erro desexada , mentres que é proporcional a e ao número de elementos que se van engadir.
Para engadir un elemento, pásase por cada unha das funcións hash para obter posicións do vector. Póñense a 1 os bits desas posicións.
Para comprobar se un elemento está no conxunto, pásase polas funcións hash para obter posicións. Se algunha das posicións ten un 0, o elemento non está no conxunto con seguridade; se estivese, todos os bits se terían posto a 1 cando se inseriu. Se todos son 1, ou o elemento está no conxunto, ou os bits foron postos a 1 por casualidade durante a inserción doutros elementos, o que dá un falso positivo. Nun filtro de Bloom simple non hai xeito de distinguir os dous casos, aínda que técnicas máis avanzadas poden resolvelo.
O requisito de deseñar funcións hash independentes distintas pode ser prohibitivo para grande. Cunha boa función hash de saída ampla, hai pouca correlación entre os distintos campos de bits, polo que se poden xerar varias funcións «distintas» dividindo a súa saída en varios campos. Alternativamente, pásanse valores iniciais distintos a unha función hash que acepte un valor inicial. A independencia entre as funcións pódese relaxar cun aumento insignificante da taxa de falsos positivos.
Retirar un elemento deste filtro simple é imposible, porque non hai xeito de saber cales dos bits deberían poñerse a 0. Aínda que pór a cero calquera deses bits abondaría para retiralo, tamén retiraría calquera outro elemento que se mape a ese bit. Unha retirada puntual pódese simular cun segundo filtro que conteña os elementos retirados, pero os falsos positivos do segundo filtro convértense en falsos negativos do filtro composto.
Vantaxes de espazo e tempo miniatura|360px|alt=Filtro de Bloom usado para acelerar as respostas nun sistema de almacenamento chave-valor.|Filtro de Bloom usado para acelerar as respostas nun sistema de almacenamento chave-valor. Os valores gárdanse nun disco con tempos de acceso lentos; as decisións do filtro de Bloom son moito máis rápidas.
Aínda que arrisca falsos positivos, o filtro de Bloom ten unha vantaxe substancial de espazo sobre outras estruturas de datos para representar conxuntos, como as árbores binarias de busca auto-equilibradas, os tries, as táboas hash ou os vectores simples. A maioría destas requiren gardar os propios elementos, mentres que os filtros de Bloom non gardan os elementos en absoluto. Un filtro de Bloom cun 1 % de erro e un valor óptimo de require só uns 9,6 bits por elemento, independentemente do tamaño dos elementos. Esta vantaxe vén en parte da súa compacidade, herdada dos vectores, e en parte da súa natureza probabilística. A taxa de falso positivo do 1 % pódese reducir nun factor de dez engadindo só uns 4,8 bits por elemento.
Con todo, se o número de valores potenciais é pequeno e moitos deles poden estar no conxunto, o vector de bits determinista, que require só un bit por elemento potencial, pode superar doadamente o filtro de Bloom. As táboas hash gañan vantaxe de espazo e tempo se comezan a ignorar as colisións e só gardan se cada cubo contén unha entrada; neste caso convértense efectivamente en filtros de Bloom con .
Nun filtro de Bloom de tamaño fixo, engadir un elemento ou comprobar a pertenza require operacións hash, independentemente do número de elementos xa inseridos, sen contar o custo de calcular os hash de cada chave. Isto non é exclusivo dos filtros de Bloom: un vector de bits para un universo pequeno tamén admite operacións de pertenza de tempo constante. As táboas hash poden ser máis rápidas na práctica segundo a implementación e a carga.
Probabilidade de falsos positivos miniatura|360px|alt=Probabilidade de falso positivo p en función do número de elementos n e do tamaño do filtro m.|A probabilidade de falso positivo p en función do número de elementos n do filtro e do tamaño do filtro m. Asumiuse un número óptimo de funcións hash k = (m/n) ln 2.
Supoñamos que unha función hash selecciona cada posición do vector con igual probabilidade. Se m é o número de bits do vector, a probabilidade de que un bit non se poña a 1 por unha función hash durante a inserción dun elemento é
Se k é o número de funcións hash e as súas saídas son independentes, a probabilidade de que ningunha delas poña ese bit a 1 é
Usando a identidade , para m grande tense
Se inserimos n elementos, a probabilidade de que un bit siga a 0 é
a probabilidade de que estea a 1 é, polo tanto,
Agora compróbase a pertenza dun elemento que non está no conxunto. Cada unha das k posicións calculadas polas funcións hash está a 1 coa probabilidade anterior. A probabilidade de que todas estean a 1, o que faría que o algoritmo afirmase erroneamente que o elemento está no conxunto, adoita darse como
Isto non é estritamente correcto, porque supón independencia entre as probabilidades de cada bit. A probabilidade verdadeira de falso positivo, sen supoñer independencia, dáse en termos dos números de Stirling de segunda especie. Mitzenmacher e Upfal dan unha análise alternativa que chega á mesma aproximación sen supoñer independencia.
Número óptimo de funcións hash Na aproximación anterior, tratando k como unha variable real, o mínimo obtense en
Na implementación, k debe ser un enteiro positivo: compáranse os valores enteiros próximos ao óptimo. A fórmula continua para estimar m, dados n e unha probabilidade obxectivo ε, é
Así, o número óptimo de bits por elemento é , co número correspondente de funcións hash . Isto significa que, para unha probabilidade de falso positivo dada, a lonxitude do filtro é proporcional ao número de elementos e o número de funcións hash só depende da probabilidade obxectivo. Goel e Gupta dan unha cota superior rigorosa sen aproximacións.
Aproximación do número de elementos O número de elementos dun filtro de Bloom pódese aproximar coa fórmula
onde é unha estimación do número de elementos do filtro, m é a lonxitude do filtro, k é o número de funcións hash e X é o número de bits postos a un.
Unión e intersección de conxuntos Os filtros de Bloom son un xeito compacto de representar un conxunto de elementos. Pódense usar para aproximar o tamaño da intersección e da unión de dous conxuntos. Para dous filtros compatibles A e B de lonxitude m, sexan , e os números de bits a 1 en A, B e no seu OR bit a bit, respectivamente. Aplicando a estimación anterior a cada filtro non saturado, obtéñense , e . O tamaño da intersección estímase por inclusión-exclusión: .
Propiedades A diferenza dunha táboa hash estándar, un filtro de Bloom de tamaño fixo pode representar un conxunto cun número arbitrariamente grande de elementos; engadir un elemento nunca falla porque a estrutura se «encha». Con todo, a taxa de falsos positivos aumenta a medida que se engaden elementos, ata que todos os bits están a 1. Para combinar filtros cómpre que teñan o mesmo tamaño, o mesmo número de funcións hash e as mesmas funcións e sementes. Nesas condicións, OR produce o mesmo filtro que inserir todos os elementos da unión. AND non dá en xeral o filtro exacto da intersección, pero conserva todos os seus elementos sen falsos negativos e pode incluír falsos positivos. Algúns tipos de código superposto pódense ver como un filtro de Bloom implementado con tarxetas perforadas. Un exemplo é o Zatocoding, inventado por Calvin Mooers en 1947.
Exemplos As moscas da froita usan un mecanismo semellante aos filtros de Bloom para detectar a novidade dos olores. Os servidores de Akamai Technologies usan filtros de Bloom para evitar que os «one-hit-wonders» se garden nas súas cachés de disco. Google Bigtable, Apache HBase, Apache Cassandra, ScyllaDB e PostgreSQL usan filtros de Bloom para reducir as consultas a disco de filas ou columnas inexistentes. O navegador Google Chrome usaba un filtro de Bloom para identificar URL maliciosas. Mozilla Firefox usa filtros de Bloom en cascada para a revocación de certificados (CRLite) e para bloquear complementos maliciosos. O buscador Bing usa filtros de Bloom xerárquicos multinivel no seu índice de busca, BitFunnel. O proxy Squid usa filtros de Bloom para os resumos de caché. Bitcoin usaba filtros de Bloom para acelerar a sincronización de moedeiros, ata que se descubriron vulnerabilidades de privacidade. O sistema de almacenamento Venti usa filtros de Bloom para detectar datos xa almacenados. O SPIN model checker usa filtros de Bloom para seguir o espazo de estados alcanzables. Medium usa filtros de Bloom para evitar recomendar artigos xa lidos. Ethereum usa filtros de Bloom para atopar rapidamente rexistros na súa cadea de bloques.
Alternativas Os filtros de Bloom clásicos usan bits de espazo por chave inserida, onde é a taxa de falso positivo. Con todo, o espazo estritamente necesario para calquera estrutura que xogue o mesmo papel é só por chave. Por tanto, os filtros de Bloom usan un 44 % máis de espazo cá estrutura óptima equivalente.
Pagh et al. fornecen unha estrutura que usa bits con operacións de tempo constante amortizado. A súa estrutura é principalmente teórica, pero está estreitamente relacionada coa amplamente usada filtro de cociente. Outra alternativa é o filtro cuckoo, baseado en variantes de hashing cuckoo; usa unha táboa hash que garda só pequenas impresións dixitais (hashes curtos) das chaves. Os filtros cuckoo admiten borrados e teñen mellor localidade de referencia cá dos filtros de Bloom.
Moitas alternativas, incluídos os filtros de cociente e cuckoo, baséanse en dispersar as chaves a impresións dixitais de bits e gardalas nunha táboa hash compacta. Putze, Sanders e Singler estudaron variantes máis rápidas ou con menos espazo; a variante rápida localiza os valores hash nun ou dous bloques do tamaño da caché do procesador, aínda que usa un 32 % máis de espazo. Graf e Lemire describen o filtro de XOR, que garda as impresións dixitais nunha táboa de hashing perfecto, é máis eficiente en memoria ( bits por chave) e máis rápido, pero require tres accesos a memoria por consulta e non se pode modificar tras a súa creación.
Extensións e aplicacións Existen máis de 60 variantes de filtros de Bloom, moitas revisións do campo e un fluxo continuo de aplicacións. Algunhas variantes difiren o suficiente da proposta orixinal como para considerarse derivacións ou ramas da estrutura.
Filtrado de caché