Hola habrozhiteli! Los algoritmos son el corazón y el alma de la informática. No puede prescindir de ellos, están en todas partes, desde el enrutamiento de la red y los cálculos genómicos hasta la criptografía y el aprendizaje automático. El "Algoritmo perfecto" lo convertirá en un verdadero profesional que establecerá tareas y las resolverá magistralmente tanto en la vida como en una entrevista al contratar cualquier empresa de TI.
En el segundo libro, Tim Rafgarden, el gurú de los algoritmos, habla sobre la búsqueda de gráficos y su aplicación, el algoritmo de búsqueda de la ruta más corta y el uso e implementación de algunas estructuras de datos: montones, árboles de búsqueda, tablas hash y el filtro Bloom.
Esta publicación presenta un extracto de Bloom Filters: The Basics.
¿De qué trata este libro?
La segunda parte del libro "Algoritmo perfecto" es un curso introductorio sobre los conceptos básicos de alfabetización sobre los siguientes tres temas.
Búsqueda gráfica y aplicaciones . Los gráficos modelan varios tipos diferentes de redes, incluyendo carreteras, comunicación, redes sociales y redes de dependencias entre tareas. Los gráficos pueden ser complejos, pero hay algunas primitivas increíblemente rápidas para hablar sobre la estructura de los gráficos. Comenzaremos con algoritmos de búsqueda de gráficos de tiempo lineal, desde aplicaciones que van desde el análisis de redes hasta la construcción de una secuencia de operaciones.
Los caminos más cortos . En el problema de la ruta más corta, el objetivo es calcular la mejor ruta en la red desde el punto A hasta el punto B. Esta tarea tiene aplicaciones obvias, como el cálculo de rutas de tráfico, y también ocurre en forma encubierta en muchas otras tareas universales. Vamos a generalizar uno de nuestros algoritmos de búsqueda de gráficos y llegaremos al famoso algoritmo de búsqueda de ruta más corta de Dijkstra.
Estructuras de datos . Este libro lo convertirá en un usuario altamente educado de varias estructuras de datos diferentes diseñadas para admitir un conjunto de objetos en evolución con sus claves asociadas. El objetivo principal es desarrollar una intuición sobre qué estructura de datos es adecuada para su aplicación. Secciones adicionales proporcionan pautas para implementar estas estructuras de datos desde cero.
Primero, discutimos los montones que pueden identificar rápidamente el objeto almacenado con la clave más pequeña, y también son útiles para ordenar, implementar una cola prioritaria e implementar el algoritmo casi lineal-temporal de Dijkstra. Los árboles de búsqueda mantienen el orden completo de las claves en los objetos almacenados y admiten una gama aún más amplia de operaciones. Las tablas hash están optimizadas para operaciones de búsqueda ultrarrápidas y están muy extendidas en los programas modernos. También observamos el filtro Bloom, un pariente cercano de la tabla hash, que usa menos espacio debido a errores aleatorios.
Puede familiarizarse con el contenido del libro con más detalle en las secciones "Conclusiones", que completan cada capítulo e identifican los puntos más importantes. Las secciones del libro, marcadas con un asterisco, son las más avanzadas en términos del nivel de información presentada. Si el libro está diseñado para una familiarización superficial con el tema, entonces el lector puede omitirlos sin perder la integridad de lo escrito.
Temas cubiertos en otras tres partes . La primera parte del libro "Algoritmo perfecto. Fundamentos "cubre las notaciones asintóticas (la notación O-large y sus parientes cercanos), los algoritmos de" divide y vencerás "y el teorema principal de relación de recurrencia: el método principal, la clasificación rápida aleatoria y su análisis, y los algoritmos de selección lineal-temporal. La tercera parte se ocupa de algoritmos codiciosos (planificación, árboles de expansión mínima, agrupación, códigos Huffman) y programación dinámica (problema de mochila, alineación de secuencias, caminos más cortos, árboles de búsqueda óptimos). La cuarta parte está dedicada a la integridad de NP, lo que significa para un diseñador de algoritmos y estrategias para resolver problemas computacionalmente insolubles, incluido el análisis heurístico y la búsqueda local.
12.5 Bloom Filters: The Basics
Los filtros Bloom son parientes cercanos de las tablas hash. Son muy compactos, pero periódicamente cometen errores. Esta sección describe cómo los filtros Bloom son buenos y cómo se implementan, mientras que la sección 12.6 establece una curva de compromiso entre la cantidad de espacio utilizado por el filtro y su tasa de error.
12.5.1. Operaciones soportadas
La razón de la existencia de los filtros Bloom es esencialmente la misma que la de una tabla hash: operaciones de inserción y visualización súper rápidas, gracias a las cuales puede recordar rápidamente lo que vio y lo que no. ¿Por qué debería molestarnos una estructura de datos diferente con el mismo conjunto de operaciones? Debido a que los filtros Bloom son preferibles a las tablas hash en aplicaciones en las que el espacio vale su peso en oro, y un error aleatorio no es un obstáculo para la transacción.
Al igual que las tablas hash con direccionamiento abierto, los filtros Bloom son mucho más fáciles de implementar e imaginar en su mente cuando solo admiten operaciones Insertar y Ver (y sin la operación Eliminar). Nos centraremos en este caso.
FILTROS DE FLUJO: OPERACIONES COMPATIBLES
Vista: con la tecla k, devuelve "sí" si k se insertó previamente en el filtro Bloom, y "no" en caso contrario.
Pegar: agregue una nueva clave k al filtro Bloom.
Los filtros Bloom son muy eficientes espacialmente; normalmente, pueden requerir solo 8 bits por inserto. ¡Esto es increíble, ya que 8 bits son completamente insuficientes para recordar incluso una clave de 32 bits o un puntero a un objeto! Por esta razón, la operación Ver en el filtro Bloom devuelve solo la respuesta "sí" / "no", mientras que en la tabla hash, esta operación devuelve un puntero al objeto deseado (si se encuentra). Es por eso que la operación Insertar ahora solo acepta la clave, y no el (puntero) del objeto.
A diferencia de todas las otras estructuras de datos que estudiamos, los filtros de Bloom pueden estar equivocados. Hay dos tipos de errores: falsos negativos cuando la operación Ver devuelve "falso" incluso si la clave solicitada ya se ha insertado anteriormente, y declaraciones falsas (o positivas) cuando la operación Ver devuelve "verdadero", aunque la clave solicitada aún no se ha insertado en el pasado . En la sección 12.5.3 veremos que los filtros Bloom básicos nunca sufren falsos negativos, pero pueden tener "elementos fantasmas" en forma de declaraciones falsas. La Sección 12.6 muestra que la frecuencia de las declaraciones falsas se puede controlar ajustando adecuadamente el uso del espacio. Una implementación típica de un filtro Bloom puede tener una tasa de error de aproximadamente 1% o 0.1%.
Los tiempos de ejecución para las operaciones Insertar y Ver son tan rápidos como en la tabla hash. Y aún mejor, se garantiza que estas operaciones se realizarán en tiempo constante, independientemente de la implementación del filtro Bloom y el conjunto de datos1. Sin embargo, la implementación y el conjunto de datos afectan la tasa de error del filtro.
Para resumir las ventajas y desventajas de los filtros Bloom sobre las tablas hash:
FILTRO DE FLUJO CONTRA LAS TABLAS DE HASH
1. Pros: más espacialmente efectivo.
2. Pros: operaciones garantizadas de tiempo permanente para cada conjunto de datos.
3. Contras: no puede almacenar punteros a objetos.
4. Contras: eliminaciones más complejas en comparación con una tabla hash con un embrague.
5. Contras: probabilidad distinta de cero de una declaración falsa.
La lista de indicadores para los filtros básicos de Bloom es la siguiente.
Tabla 12.4. Filtros básicos de Bloom: operaciones compatibles y su tiempo de ejecución. El signo de la daga (†) indica que la operación Ver tiene una probabilidad controlable pero no nula de afirmaciones falsas
Los filtros Bloom deben usarse en lugar de tablas hash en aplicaciones en las que sus ventajas son importantes y sus desventajas no son un obstáculo para la transacción.
CUANDO UTILIZAR EL FILTRO DE FLORACIÓN
Si una aplicación requiere una búsqueda rápida con un conjunto de objetos en evolución dinámica, el espacio vale su peso en oro y una pequeña cantidad aceptable de afirmaciones falsas, entonces el filtro Bloom suele ser la estructura de datos preferida.
12.5.2. Aplicaciones
A continuación, hay tres usos con escaneos repetidos, donde ahorrar espacio puede ser importante, y las declaraciones falsas no son un obstáculo para la transacción.
Correctores de ortografía. En la década de 1970, los filtros Bloom se usaban para implementar correctores ortográficos, correctores ortográficos. En la etapa de preprocesamiento, cada palabra del diccionario se inserta en el filtro Bloom. La ortografía de un documento se reduce a una sola operación: observe una palabra en un documento y marque las palabras para las que esta operación devuelve "no".
En este apéndice, una declaración falsa corresponde a una palabra no válida que el corrector ortográfico acepta sin darse cuenta. Tales errores no hicieron que los correctores ortográficos fueran ideales. Sin embargo, a principios de la década de 1970, el espacio valía su peso en oro, por lo que usar filtros Bloom en ese momento era una estrategia de ganar-ganar.
Contraseñas prohibidas Una aplicación antigua que sigue siendo válida hasta el día de hoy rastrea las contraseñas prohibidas, contraseñas que son demasiado comunes o demasiado fáciles de adivinar. Inicialmente, todas las contraseñas prohibidas se insertan en el filtro Bloom; se pueden insertar contraseñas prohibidas adicionales más adelante, según sea necesario. Cuando un usuario intenta establecer o restablecer su contraseña, el sistema busca la contraseña propuesta en el filtro Bloom. Si la búsqueda devuelve "sí", se le solicita al usuario que intente nuevamente con una contraseña diferente. Aquí, una declaración falsa se traduce en una contraseña segura, que el sistema rechaza.
Siempre que la tasa de error no sea demasiado alta, digamos no más de 1% o 0.1%, esto no importa mucho. De vez en cuando, algunos usuarios necesitarán un intento adicional para encontrar una contraseña aceptable para el sistema.
Enrutadores de internet . Varias de las impresionantes aplicaciones actuales de los filtros Bloom tienen lugar en lo profundo de Internet, donde los paquetes de datos pasan a través de enrutadores con velocidad de transmisión. Hay muchas razones por las que un enrutador puede querer recordar rápidamente lo que vio en el pasado. Por ejemplo, un enrutador puede querer encontrar la dirección IP de origen de un paquete en la lista de direcciones IP bloqueadas, rastrear el contenido de la memoria caché para evitar vistas falsas de la memoria caché o mantener estadísticas que ayuden a identificar un ataque de red de denegación de servicio. La velocidad de llegada de paquetes requiere vistas súper rápidas, y la memoria limitada del enrutador hace que el espacio valga su peso en oro. Estas aplicaciones son administradas directamente por el filtro Bloom.
12.5.3. Implementación
Mirando dentro del filtro Bloom, puede ver una implementación elegante. La estructura de datos admite una cadena de n bits o, del mismo modo, una matriz A de longitud n en la que cada elemento es 0 o 1. (Todos los elementos se inicializan a cero). Esta estructura también utiliza m funciones hash h1, h2, ..., hm , mientras que cada uno asigna el universo U de todas las claves posibles al conjunto {0, 1, 2, ..., n - 1} de posiciones en la matriz. El parámetro m es proporcional al número de bits utilizados por el filtro Bloom para la inserción y, como regla, es una pequeña constante (por ejemplo, 5).
Cada vez que se inserta una clave en un filtro Bloom, cada una de las funciones m hash establece un indicador y establece el bit correspondiente de la matriz A en 1.
FILTRO DE BLOOM: INSERTAR (EN LLAVE)
for i = 1 to m do A[hi(k)] := 1
Por ejemplo, si m = 3 y h1 (k) = 23, h2 (k) = 17 y h3 (k) = 5, la inserción de k hace que los bits 5, 17 y 23 de la matriz se establezcan iguales 1 (Fig. 12.5).
En la operación Ver, el filtro Bloom busca la huella digital que podría haber quedado en la inserción k.
FILTRO DE BLOOM: VER (TECLA CLAVE)
for i = 1 to m do if A [hi (k)] = 0 then return «» return «»
Ahora podemos ver por qué los filtros Bloom no pueden sufrir falsos negativos. Cuando se inserta la clave k, los m bits correspondientes se establecen en 1. Durante la vida útil del filtro Bloom, los bits pueden cambiar su valor de 0 a 1, pero no al revés. Por lo tanto, estos m bits permanecen 1 para siempre. Se garantiza que cada operación View k posterior devolverá la respuesta correcta de yes.
También podemos ver cómo surgen declaraciones falsas. Suponga que m = 3 y las cuatro teclas k1, k2, k3, k4 tienen los siguientes valores hash:
Supongamos que insertamos k1, k2, k3 y k4 en un filtro Bloom (Figura 12.6). Estas tres inserciones conducen a un total de nueve bits a 1, incluidos tres bits en la huella digital de la clave k1 (5, 17 y 23). En este punto, el filtro Bloom ya no puede distinguir si se insertó o no la clave k1. Incluso si k1 no se insertó en el filtro, la búsqueda devolverá "sí", que es una declaración falsa.
Intuitivamente, podemos suponer que con un aumento en el tamaño n del filtro Bloom, el número de superposiciones entre las huellas digitales de diferentes teclas debería disminuir, lo que, a su vez, conduce a un menor número de declaraciones falsas. Pero el objetivo principal del filtro Bloom es ahorrar espacio. ¿Hay un término medio donde tanto n como la frecuencia de las declaraciones falsas son simultáneamente pequeñas? La respuesta no es obvia y requiere un análisis matemático realizado en la siguiente sección.
»Se puede encontrar más información sobre el libro en
el sitio web del editor»
Contenidos»
ExtractoPara Khabrozhiteley 20% de descuento en el cupón -
AlgoritmosTras el pago de la versión en papel del libro, se envía un libro electrónico por correo electrónico.