Filtro de Bloom: seguro que no, o probablemente sí

Cada palabra activa k bits en una secuencia de m bits. Para consultar una palabra, comprueba sus k bits: basta con que uno valga 0 para saber que nunca se insertó; si todos valen 1, solo puedes decir que probablemente esté. Inserta las palabras paso a paso y después escribe una que se te ocurra.

Ejemplo resuelto — Filtro de Bloom: seguro que no, o probablemente sí

Bits con valor 1	20 de 64 (31,3 %)
Bits por palabra	8,00
k óptimo según la estimación estándar	5,55
Estimación a partir de los bits activados	3,05 %
Medición sobre 10.000 cadenas nunca insertadas	335 de 10.000 (3,35 %)

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

Un filtro de Bloom permite consultar si un elemento pertenece a un conjunto mediante una secuencia de m bits y k funciones de dispersión. Al insertar un elemento, se activan los k bits que indican sus valores de dispersión. Al consultarlo, se comprueban esos mismos k bits: si alguno vale 0, seguro que no pertenece al conjunto; si todos valen 1, probablemente pertenece a él. Un «probablemente sí» incorrecto es un falso positivo. Con n elementos insertados, la estimación estándar de la tasa de falsos positivos es (1 − e^−kn/m)^k, una aproximación exponencial de la fórmula que Bloom propuso en 1970. Su mínimo se alcanza en k = (m/n) ln 2.

Qué significa cada símbolo

m: el número de bits del filtro
k: el número de funciones de dispersión y, por tanto, de bits que activa cada palabra y comprueba cada consulta
n: el número de palabras insertadas
X: el número de bits con valor 1 una vez insertadas las n palabras

Supone: Las k posiciones de una palabra se obtienen a partir de dos valores de dispersión mediante dispersión doble: la posición i es (h₁ + i·h₂) mod m. Aquí, h₁ es el valor FNV-1a de la palabra; h₂, un valor djb2 mezclado y ajustado para que sea impar; y m, una potencia de dos. Así, las k posiciones de cada palabra son siempre distintas. La estimación estándar considera que cada una de las kn posiciones se elige al azar y de forma independiente. La dispersión doble y un m pequeño hacen que el filtro real se aparte de ese supuesto. La tasa de falsos positivos se mide sobre las 10.000 cadenas de 0 a 9999: es exacta para esas cadenas, pero no para todas las palabras posibles.

Dieciséis funciones de dispersión dan peor resultado que una 🖖

Pulsa Cinco funciones y lee la tabla que aparece bajo los resultados. Con 128 bits y 16 palabras, 1 función de dispersión deja pasar al 12,82 % de las cadenas nunca insertadas; 5 dejan pasar al 2,50 %, el mínimo de la columna; 16, al 32,01 %, peor que con 1. Cada función adicional obliga a comprobar otro bit en cada consulta, lo que ayuda, pero también activa otro bit en cada inserción, lo que perjudica. De 1 a 5, la tasa baja a cada paso; a partir de ahí sube, con un pequeño descenso en 15. Bloom identificó el punto de cambio en 1970: llega cuando aproximadamente la mitad de los bits valen 1. Con 5 funciones de dispersión, 60 de estos 128 bits valen 1, y la estimación estándar sitúa el k óptimo en (m/n) ln 2 = 8 × 0,693 = 5,55.

Contar los bits que valen 1 mejora la estimación estándar 🖖

Pulsa Dieciséis funciones. La estimación estándar da un 9,76 %; el filtro deja pasar al 32,01 %. La estimación supone que hay 128 × (1 − e⁻²) = 110,7 bits activados, pero estas 16 palabras activan 119. Si elevas la proporción real de bits activados a la potencia 16, (119/128)¹⁶, obtienes un 31,15 %, cerca del valor medido. Con un k tan grande, unos pocos bits más con valor 1 influyen mucho: los 16 bits tienen que valer 1. Entre las configuraciones de esta página que producen algún falso positivo, la estimación basada en los bits activados es la más cercana a la tasa medida en 5.356 de 6.051 casos, si comparas cuánto se aleja de 1 el cociente entre cada estimación y la medición. Un filtro real puede contar sus propios bits con valor 1 y estimar así su tasa mejor que con la fórmula. Además, estos dieciséis animales forman un conjunto poco afortunado: con otros 150 conjuntos de 16 palabras, un filtro de este tamaño da una media del 14,4 %, todavía por encima de la estimación.

Eliminas una palabra y desaparece otra 🖖

Pulsa Eliminar owl y avanza hasta el final. Owl activó los bits 37, 58 y 15. Fox se insertó después en las posiciones 14, 15 y 16, y encontró el bit 15 ya a 1. Al poner a 0 los bits de owl, también pones a 0 el bit 15 de fox. Su consulta devuelve entonces «seguro que no», aunque la palabra está en el filtro. Es un falso negativo, el único error que un filtro de Bloom garantiza que nunca cometerá. Un bit solo registra que alguna palabra lo activó; no guarda cuál. Por eso no puedes desactivarlo con seguridad. En este filtro de 64 bits, eliminar seis de las ocho palabras haría desaparecer también otra palabra. La solución habitual consiste en guardar un pequeño contador en cada posición: se suma 1 al insertar y se resta 1 al eliminar. A cambio, se necesita más memoria.

¿Cuánto podía reducirse el filtro de Bloom de 1970 para la división de palabras? 4 pasos
El ejemplo que Burton Bloom presentó en 1970 era un programa para dividir 500.000 palabras con guiones al final de línea. Unas reglas sencillas resuelven 450.000; las otras 50.000 deben consultarse en un diccionario guardado en disco. Bloom propuso mantener en la memoria principal un filtro con esas 50.000 palabras y aceptar que 1 de cada 16 palabras fáciles provocara un acceso innecesario al disco. ¿Cuántos bits necesita el filtro, con cuántas funciones de dispersión, y cuántas lecturas de disco quedan? Después, configura esta página con el mismo número de bits por palabra y mide el resultado.

Abre este problema en la herramienta
1. Con el k óptimo, la estimación estándar requiere log₂(1/p) / ln 2 bits por palabra. Para p = 1/16, son 4 / 0,6931 = 5,77 bits, así que el filtro ocupa 50.000 × 5,77 = 288.539 bits. Bloom dio la cifra de «menos de 300.000 bits». El k óptimo es 5,77 × ln 2 = 4, y con 4 funciones de dispersión se espera que la mitad de los bits valgan 1.
  
  $\frac{lo g _{2} 16}{ln 2} = \frac{4}{0.6931} = 5.77 bits per word, 50000 \times 5.77 = 288539 bits, k = 5.77 \times ln 2 = 4$
2. Cada una de las 50.000 palabras difíciles sigue requiriendo una consulta al disco, al igual que 1 de cada 16 palabras fáciles: 450.000 / 16 = 28.125 consultas más. En total, son 78.125 lecturas de disco para 500.000 palabras, el 15,6 %. Bloom redondeó la cifra a 78.000: un ahorro del 84 % frente a consultar el disco para cada palabra.
  
  $50000 + \frac{450 000}{16} = 78125 disk reads of 500000 (15.6%)$
3. La longitud de las palabras no interviene en estos cálculos. El filtro necesita 5,77 bits por palabra, tanto para «cat» como para «incomprehensibilities». Bloom calculaba que una tabla de dispersión convencional necesitaba al menos 19 bits de media para representar cada palabra. Cada vez que p se reduce a la mitad, hacen falta 1 / ln 2 = 1,44 bits más por palabra: para 1 de cada 64, serían 6 / 0,6931 = 8,66.
  
  $\frac{1}{l n 2} = 1.44 bits per halving of p, \frac{6}{0.6931} = 8.66 for p = \frac{1}{64}$
4. Esta página admite como máximo 64 palabras, pero la estimación solo depende de m/n y k. Fija m = 256, n = 44 (5,82 bits por palabra) y k = 4. De los 256 bits, 122 valen 1, el 47,7 %, y 535 de las 10.000 cadenas nunca insertadas reciben un «probablemente sí»: el 5,35 %, por debajo del 1/16 = 6,25 % para el que se dimensionó el filtro. La estimación estándar para este filtro es del 6,11 %.
  
  $\frac{256}{44} = 5.82 : \frac{535}{10 000} = 5.35% < \frac{1}{16} = 6.25%$
Respuesta

288.539 bits y 4 funciones de dispersión, con 78.125 lecturas de disco para 500.000 palabras. Las 44 palabras de esta página en 256 bits dan una tasa medida del 5,35 %, dentro del objetivo. Ese resultado corresponde a un filtro concreto de 44 palabras. La página no permite comprobar si 50.000 palabras en 288.539 bits darían una tasa igual de cercana a 1/16: su límite es de 64 palabras.

$288539 bits, k = 4, 78125 disk reads$

Ruta de aprendizaje

Referencias (1)

The method itself, the turning point at half the bits set in the first insight, and the hyphenation example the worked problem recomputes: Burton H. Bloom, "Space/time trade-offs in hash coding with allowable errors," Communications of the ACM 13(7), July 1970, pp. 422–426.

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.

Filtro de Bloom: seguro que no, o probablemente sí

La teoría — Filtro de Bloom: seguro que no, o probablemente sí

Qué significa cada símbolo

Dieciséis funciones de dispersión dan peor resultado que una 🖖

Contar los bits que valen 1 mejora la estimación estándar 🖖

Eliminas una palabra y desaparece otra 🖖

Problema resuelto al detalle

Qué operaciones abarata una estructura de datos