Filtro Bloom, una implementación en PHP
En esta ocasión voy a presentar una implementación simple de un filtro de Bloom implementado en PHP. Puedes ver la implementación en mi github: https://github.com/oscarpascualbakker/bloomfilter.
Un filtro Bloom es una estructura de datos probabilísticos que se utiliza para comprobar si un elemento es miembro de un conjunto. En esta estructura, los elementos se pueden agregar al conjunto, pero no eliminar.
Una consulta a un filtro Bloom devuelve «posiblemente en el conjunto» o «definitivamente no en el conjunto».
Un filtro Bloom es una matriz de m bits (bitarray), inicialmente todos establecidos en 0. También debe haber k funciones de hash diferentes definidas, cada una de las cuales mapea o aplica un hash a algún elemento establecido en una de las m posiciones de la matriz, generando una distribución aleatoria uniforme. Normalmente, k es una constante pequeña que depende de la probabilidad de falsos errores que vamos a permitir.
Para agregar un elemento al conjunto, es necesario realizar k funciones de hash sobre el elemento, obtener las k posiciones correspondientes en el filtro y establecer estos bits en 1.
Para verificar si un elemento está en el conjunto es necesario realizar de nuevo las k funciones de hash sobre ese elemento para obtener las posiciones en el filtro. Si alguno de los bits en estas posiciones es 0, el elemento definitivamente no está en el conjunto.
Si todas las posiciones se establecen en 1, entonces el elemento está en el conjunto o los bits se han establecido en 1 durante la inserción de otros elementos, lo que da como resultado un falso positivo.
No es posible eliminar elementos en un filtro Bloom simple, y no hay forma de distinguir entre un positivo legítimo y un falso positivo. Técnicas más avanzadas pueden resolver este problema.
Utilidades de un filtro Bloom
Los filtros Bloom son útiles en los casos en que:
- los datos a buscar son grandes
- la memoria disponible en el sistema es limitada/baja
Por este motivo el algoritmo tiene muchos usos. Dado que es un sistema que responde de forma muy rápida si un elemento está (¡probablemente!) en un conjunto o no, se usa para ahorrar tiempo y espacio.
- Sistemas de almacenamiento en caché
- Detección de contraseña débil
- Protocolo de caché de Internet
- Navegación segura en Google Chrome
- Sincronización de billetera en Bitcoin (esto fue deprecado de Bitcoin, pero formó parte de las primeras versiones)
- Rastreo de IP basado en hash
- Seguridad cibernética como análisis de virus
Espero que te haya gustado este algoritmo (entiendo que sí, si has leído hasta aquí).
¡Hasta la próxima!
