La entrada de Wikipedia proporciona una buena explicación del filtro básico de Bloom y sus extensiones, incluido un análisis estadístico simple. Enlace: http://en.wikipedia.org/wiki/Blo…
El tipo más común de filtro Bloom es un conjunto de bits de tamaño n equipado con k funciones hash independientes. Cada una de estas funciones hash debe correlacionarse con un número entero en [1, n ]. Este filtro Bloom solo admite agregar objetos y buscar la presencia de un objeto en el conjunto.
La “firma” de un objeto se calcula calculando los k hashes separados del objeto, usando cada función hash independiente. Estos k enteros corresponderán a las posiciones de k bits en el conjunto de bits (tenga en cuenta que estas posiciones no son necesariamente únicas). Agregar el objeto implica simplemente establecer estos bits en 1, y buscar la presencia de un objeto implica verificar que todos los k bits estén establecidos en 1.
- ¿Qué es un algoritmo para emparejar 18 personas en los 816 grupos posibles de 3 con 6 grupos a la vez?
- ¿Qué es el algoritmo de optimización de memoria?
- ¿Cuál es el algoritmo para resolver el buscaminas?
- ¿Qué algoritmo de compresión de imagen se usa en WhatsApp?
- ¿Qué estructura de datos sería mejor para encontrar el número de estudiantes dentro de un rango de altura dado de manera escalable?
La idea detrás de por qué esto funciona es similar a cómo funciona una tabla hash; sin embargo, las colisiones se ignoran para un filtro Bloom. El uso de múltiples funciones hash ayuda al hacer que la probabilidad de una colisión sea mucho menos probable.