Los filtros Bloom se utilizan para verificar rápidamente si un valor es:
- definitivamente no en una colección, o
- posiblemente está en una colección.
La forma de hacerlo es con múltiples funciones hash. En lo que respecta a los filtros de floración, una función hash es algo que toma un valor y escupe un índice que generalmente cambiará cuando cambie el valor de entrada.
Digamos que tiene dos de estas funciones hash.
- ¿Cómo funciona el algoritmo iPod shuffle?
- En el algoritmo O (n) para encontrar el elemento máximo en una matriz, ¿cuál es el valor esperado del número total de cambios en el valor de una variable que mantiene el máximo sobre el paso de una matriz?
- ¿Cómo se pueden usar los bucles para procesar matrices?
- ¿Cuáles son las cosas más incomprendidas sobre programación competitiva y concursos de programación como ACM ICPC?
- ¿Qué hay de malo en mi implementación de tipo de fusión?
La función hash uno, cuando se le da “A”, escupe 2.
La función hash uno, cuando se le da “B”, escupe 3.
La función hash uno, cuando se le da “C”, escupe 0.
La función hash uno, cuando se le da “D”, escupe 1.
La función hash dos, cuando se le da “A”, escupe 0.
La función hash dos, cuando se le da “B”, escupe 2.
La función hash dos, cuando se le da “C”, escupe 2.
La función hash dos, cuando se le da “D”, escupe 2.
Entonces digamos que tenías una lista:
[“A”, “B”]
Luego realizó un preprocesamiento y ejecutó cada uno de sus valores a través de estas dos funciones hash, luego estableció los bits correspondientes a las salidas en 1.
Diremos que el bit 0 está a la derecha … Terminas con esto:
1101
Entonces, ¿qué te dice esto?
¿Puedo determinar si “A” estaba en mi colección?
Bueno, no, pero puede ser.
Ejecute “A” a través de ambas funciones hash. Apunta a los bits 0 y 2.
Es posible que esos mismos bits se hayan invertido debido a que “C” está en la colección, para que pueda ver la ambigüedad y por qué no lo sabemos con certeza.
¿Está “B” en mi colección?
Las funciones hash, para B, habilitan los bits 2 y 3.
Bueno, podría ser, porque los bits 2 y 3 están configurados en 1. De hecho, podríamos descubrir que B está realmente en la colección, porque nada más puede ser responsable de configurar el bit 3 a 1, pero los filtros de floración no se usan para eso. camino. Tome el valor que desea verificar, vea qué bits se voltea y luego verifique esos bits. Hacer eso es lo que hace que los filtros de floración sean muy rápidos (tan rápido como ejecutar sus funciones hash una vez).
¿Está “C” en mi colección?
No sabemos, por la misma razón que no estamos seguros acerca de “A”. Aunque podría ser.
¿Está “D” en mi colección?
Las funciones hash generan 1 y 2.
Vemos que el 1 bit no está habilitado. Por lo tanto, podemos determinar que “D” definitivamente NO está en mi colección.
¿Ves cómo funciona? En este ejemplo, la probabilidad de que un valor esté realmente en la colección si se invierten los bits es mucho menor de lo que desea. Las posibilidades se pueden aumentar si tiene funciones hash que tienen muchas menos colisiones y genera valores en un rango más amplio de bits.
Si la probabilidad de inclusión de un elemento es lo suficientemente alta, entonces es potencialmente lo suficientemente buena para algunos propósitos. Si el filtro de floración dice que un valor “posiblemente está” en la colección, con un 90% de posibilidades de ser cierto, entonces podría ser una forma fácil de decidir si actuar sobre ese valor presente, entonces, en el improbable caso de que sea no, sufriendo el costo (superado en gran medida por el beneficio potencial) de deshacer la acción.
Si k es el número de funciones hash, la probabilidad de que el bit no esté establecido en 1 por ninguna de las funciones hash es 
