Filtro de Bloom
Un filtro de Bloom es una estructura de datos que permite a los ordenadores ver si un elemento determinado aparece en un conjunto. Para ello, los filtros de Bloom utilizan funciones hash. Para cada elemento que se añade, se calcula un valor hash. Cuando se añade un nuevo elemento, su valor hash se compara con el de los demás elementos del conjunto. Un filtro Bloom es una estructura de datos probabilística. Es posible obtener un falso positivo, pero no un falso negativo. En otras palabras, una consulta devuelve "posiblemente en el conjunto" o "definitivamente no en el conjunto". Se pueden añadir elementos al conjunto, pero no eliminarlos. Por cada elemento añadido, la probabilidad de obtener un falso positivo aumenta.
Edward Bloom propuso el filtro de Bloom en 1970. En el artículo, Bloom supone que existe un algoritmo para separar las palabras al final de una línea. Según el ejemplo, la mayoría de las palabras tienen patrones de separación silábica sencillos. Pero alrededor del 10% de las palabras requieren búsquedas que requieren mucho tiempo para obtener la regla correcta. Su caso era el de separar con guiones unas 500.000 palabras. Vio que el uso de las técnicas "normales" de hashing sin errores, almacenando los patrones de separación silábica, requeriría mucha memoria. Descubrió que utilizando su técnica, podía eliminar la mayoría de las búsquedas. Por ejemplo, un área de hash de sólo el 15% del tamaño necesario por un hash ideal sin errores sigue eliminando el 85% de los accesos al disco.
En general, se necesitan menos de 10 bits por elemento para una probabilidad de falso positivo del 1%, independientemente del tamaño o del número de elementos del conjunto.
Preguntas y respuestas
P: ¿Qué es un filtro Bloom?
R: Un filtro de Bloom es una estructura de datos que permite a los ordenadores ver si un elemento dado aparece en un conjunto. Para ello, utiliza funciones hash calculando el valor hash de cada elemento añadido y comparándolo con los demás elementos del conjunto.
P: ¿Qué tipo de estructura de datos es un filtro de Bloom?
R: Un filtro de Bloom es una estructura de datos probabilística, lo que significa que existe la posibilidad de obtener falsos positivos pero no falsos negativos.
P: ¿Quién propuso el filtro de Bloom?
R: Edward Bloom propuso el filtro de Bloom en 1970.
P: ¿Cuál fue el ejemplo de Edward para utilizar su técnica?
R: El ejemplo de Edward consistía en separar por sílabas unas 500.000 palabras; descubrió que utilizando su técnica podía eliminar la mayoría de las búsquedas y reducir los accesos al disco en un 15%.
P: ¿Cuántos bits por elemento se necesitan para una probabilidad de falso positivo del 1%?
R: Se necesitan menos de 10 bits por elemento para una probabilidad de falso positivo del 1%, independientemente del tamaño o del número de elementos del conjunto.
P: ¿Es posible eliminar elementos de un filtro de floración una vez que se han añadido?
R: No, sólo se pueden añadir elementos al conjunto, pero no eliminarlos.
P: ¿Añadir más elementos aumenta o disminuye la probabilidad de obtener un resultado falso positivo?
R: Añadir más elementos aumenta la probabilidad de obtener un resultado falso positivo.
