Algoritmos de transmisión y Filtros de Bloom: variables ficticias

En el corazón de muchos algoritmos de transmisión se encuentran los filtros Bloom. Creado hace casi 50 años por Burton H. Bloom, en un momento en que la informática todavía era bastante joven, la intención original del creador de este algoritmo era intercambiar espacio (memoria) y / o tiempo (complejidad) con lo que llamaba errores permitidos Su trabajo original se titula Intercambios espacio / tiempo en Hash Coding con errores permitidos.

Puede preguntarse sobre el espacio y el tiempo que Bloom considera motivadores para su algoritmo. Imagine que necesita determinar si un elemento ya apareció en una secuencia utilizando alguna estructura de datos previamente discutida. Encontrar algo en una secuencia implica que la grabación y la búsqueda son rápidas, por lo que una tabla hash parece una opción ideal. Las tablas hash simplemente requieren agregar los elementos que desea registrar y almacenar. La recuperación de un elemento de una tabla hash es rápida porque la tabla hash utiliza valores fácilmente manipulables para representar el elemento, en lugar del elemento en sí (lo que podría ser bastante complejo). Sin embargo, almacenar ambos elementos y un índice para esos elementos tiene limitaciones. Si una tabla hash enfrenta más elementos de los que puede manejar, como los elementos en una secuencia continua y potencialmente infinita, terminará incurriendo en problemas de memoria en algún momento.

Una consideración esencial para los filtros Bloom es que pueden ocurrir falsos positivos, pero los falsos negativos no. Por ejemplo, una secuencia de datos puede contener datos de monitoreo en tiempo real para una planta de energía. Cuando se usa un filtro Bloom, el análisis de la secuencia de datos mostrará que las lecturas esperadas son probablemente parte del conjunto de lecturas permitidas, con algunos errores permitidos. Sin embargo, cuando ocurre un error en el sistema, el mismo análisis muestra que las lecturas no son parte del conjunto de lecturas permitidas. Es poco probable que los falsos positivos causen problemas, pero la ausencia de falsos negativos significa que todos permanecen seguros. Debido a la posibilidad de falsos positivos, los filtros como el filtro Bloom son estructuras de datos probabilísticos; no proporcionan una respuesta determinada, sino probable.

Hashes, las entradas individuales en una tabla hash, son rápidas porque actúan como el índice de un libro. Usas una función hash para producir el hash; la entrada es un elemento que contiene datos complejos, y el resultado es un número simple que actúa como un índice para ese elemento. Una función hash es determinista porque produce el mismo número cada vez que lo alimenta con una entrada de datos específica.Utiliza el hash para localizar la información compleja que necesita. Los filtros Bloom son útiles porque son una forma frugal de registrar rastros de muchos elementos sin tener que almacenarlos como lo hace una tabla hash. Funcionan de una manera simple y usan los siguientes como ingredientes principales:

• Un vector de bits: Una lista de elementos de bits, donde cada bit en el elemento puede tener un valor de 0 o 1. La lista es larga número de bits llamados m. Cuanto mayor es m, mejor, aunque hay formas de definir de manera óptima su tamaño.
• Una serie de funciones hash: Cada función hash representa un valor diferente. Las funciones hash pueden reducir rápidamente los datos y producir resultados uniformemente distribuidos, que son resultados que van del valor de salida mínimo al máximo del hash.