Inicio▸Computación Distribuida y Paralela▸Filtro de Bloom — Pertenencia Probabilística a un Conjunto

🌸 Filtro de Bloom — Pertenencia Probabilística a un Conjunto

Añada elementos a un array de bits mediante k funciones hash y compruebe su pertenencia. Los filtros de Bloom nunca dan falsos negativos, pero pueden dar falsos positivos: ajuste el tamaño del array y el número de funciones hash y observe la tasa de falsos positivos.

Computación Distribuida y Paralela3DModerado60 FPS

Acerca del Filtro de Bloom

Un filtro de Bloom es una estructura de datos probabilística que responde consultas de pertenencia en tiempo O(1) y espacio O(m), donde m es el tamaño del array de bits, mucho menor que almacenar los propios elementos. Al insertar un elemento, k funciones hash independientes lo asignan a k posiciones de un array de m bits y ponen esos bits a 1. Para comprobar la pertenencia se revisan esas mismas k posiciones: si alguna es 0, el elemento está definitivamente ausente; si todas son 1, probablemente está presente. Los bits nunca se borran, por lo que los falsos negativos son imposibles, pero las colisiones de hash pueden producir falsos positivos, cuya probabilidad se aproxima mediante (1 − e^(−kn/m))^k, donde n es el número de elementos insertados.

Este simulador permite escribir palabras y añadirlas a una visualización en vivo del array de bits, consultar la pertenencia para ver aparecer falsos positivos a medida que el array se llena, y ajustar el tamaño del array m y el número de funciones hash k mediante deslizadores. La tasa de falsos positivos teórica y la tasa medida sobre 2000 consultas de prueba aleatorias se actualizan en tiempo real, haciendo visible de inmediato el equilibrio entre espacio y precisión.

Preguntas frecuentes

¿Por qué un filtro de Bloom nunca puede producir un falso negativo?

Cuando se inserta un elemento, las k posiciones de bits obtenidas mediante hash se ponen a 1 y nunca se borran. Por lo tanto, si se comprueba un elemento realmente insertado, los k bits serán 1 y el filtro informará correctamente "posiblemente en el conjunto". Un falso negativo requeriría que un bit volviera a 0, lo cual nunca ocurre.

¿Cuál es la fórmula de la probabilidad de falso positivo?

Tras insertar n elementos en un array de m bits con k funciones hash, la fracción de bits que sigue en 0 es aproximadamente e^(-kn/m), por lo que la probabilidad de que las k posiciones de un no miembro sean todas 1 es (1 - e^(-kn/m))^k. Por ejemplo, con m = 64, k = 3 y n = 10 elementos, la tasa de falsos positivos es de aproximadamente el 5%.

¿Cómo se elige el número óptimo de funciones hash k?

El valor k = (m/n) por ln 2 minimiza la tasa de falsos positivos para unos m y n dados. Muy pocas funciones hash dejan muchos bits sin marcar y reducen la discriminación; demasiadas llenan el array rápidamente y aumentan las colisiones. Para una tasa de error objetivo del 1%, el tamaño óptimo del array es de aproximadamente 9,6 bits por elemento insertado.

¿Por qué no se pueden eliminar elementos de un filtro de Bloom estándar?

Eliminar un elemento requeriría borrar sus k posiciones de bits, pero esos bits también pueden haber sido marcados por otros elementos insertados, por lo que borrarlos introduciría silenciosamente falsos negativos para esos elementos. Un filtro de Bloom con contador sustituye cada bit por un pequeño contador, que se incrementa al insertar y se decrementa al eliminar, para permitir una eliminación segura a costa de memoria adicional.

⚙ Bajo el capó

Un filtro de Bloom comprueba la pertenencia a un conjunto con k funciones hash sobre un array de bits: sin falsos negativos, con falsos positivos ajustables. Observe cómo se encienden los bits y la tasa de error sigue (1−e^(−kn/m))^k.

Filtro de Bloomhashingfalso positivoprobabilísticoCanvas 2D

3D · Renderizador Three.js / WebGL · Objetivo de 60 FPS · funciona totalmente en el cliente, sin instalación