Un Bloom filter es una estructura de datos probabilística que ahorra espacio y responde consultas de pertenencia a conjuntos con un giro: puede tener falsos positivos pero nunca falsos negativos. "Definitivamente no presente" es seguro; "posiblemente presente" necesita una verificación real.
Un array de bits de bits y funciones hash. Para un elemento, establezca los bits a los que se hace hash. Para , verifique esos bits — si alguno es 0, el elemento definitivamente está ausente.
mkkkbits: [0 0 0 0 0 0 0 0]
add "cat": hash->bits 1,4,6 -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
class BloomFilter:
def __init__(self, m, hashes):
self.bits = [0]*m
self.m, self.hashes = m, hashes # list of hash fns
def add(self, x):
for h in self.hashes:
self.bits[h(x) % self.m] = 1
def __contains__(self, x): # False = certain; True = maybe
return all(self.bits[h(x) % self.m] for h in self.hashes)
| Operación | Tiempo | Espacio |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |
Sin falsos negativos; la tasa de falsos positivos disminuye conforme m (y k ajustado) crece.
Los Bloom filters evitan barato trabajo caro: las bases de datos (p. ej., Cassandra, HBase) los utilizan para evitar lecturas de disco para claves que definitivamente no están en el disco.
Encarnan un compensación clásica de sistemas — acepte una pequeña tasa de error acotada a cambio de una reducción enorme en memoria e I/O.