Si eres fanático de la teoría de conjuntos, estarás de acuerdo en que hay dos grupos de personas que escriben programas de computadora: los que saben qué es un filtro Bloom y los que no. ¿Cómo podrías probar de manera eficiente para ver si alguien es de un conjunto u otro? Bueno, podrías utilizar un filtro Bloom. [SamWho] nos explica todo en términos generales que puedes aplicar en cualquier situación.
El filtro Bloom realiza una compensación por su velocidad. Está sujeto a falsos positivos pero no a falsos negativos. Es decir, si un algoritmo de filtro Bloom le dice que X no es parte de un conjunto, es correcto. Pero si te dice que sí, es posible que tengas que investigar más para ver si es cierto.
Si no puede decirte que algo está definitivamente en un conjunto, ¿para qué molestarse? Por lo general, cuando utiliza un filtro Bloom, desea reducir la búsqueda en una gran cantidad de datos. El ejemplo de la publicación habla de tener una base de datos de 20 megabytes de URL "malas". Quiere advertir a los usuarios si ingresan una, pero descargar esa base de datos es prohibitivo. Pero un filtro Bloom podría ser tan pequeño como 1.8 megabytes. Sin embargo, habría una probabilidad de 1 entre 1000 de obtener un falso positivo.
Aumente el tamaño de la base de datos a 3.59 megabytes y podrá reducir los falsos positivos a uno entre un millón. Presumiblemente, si obtiene un resultado positivo, podría aceptar el riesgo de que sea falso o podría trabajar más para buscar más.
Imagine, por ejemplo, un dispositivo o programa de caché web. Muchas páginas web se cargan una vez y nunca más. Si los almacena todos en caché, perderá mucho tiempo y sacará otras cosas del caché. Pero si pruebas la URL de una página con un filtro Bloom, puedes mejorar bastante las cosas. Si la URL puede existir en el filtro Bloom, entonces probablemente la haya visto antes, por lo que es posible que desee almacenarla en caché.
Si dice que no lo ha hecho, puede agregarlo al filtro para que, si alguna vez se accede nuevamente, se almacene en caché. Claro, a veces una página mostrará un falso positivo. ¿Así que lo que? Simplemente almacenarás en caché la página la primera vez, que es lo que hiciste antes de todos modos. Si eso sucede sólo el 0.1% de las veces, igual ganas.
En términos simples, el filtro Bloom procesa cada elemento utilizando tres algoritmos diferentes y establece bits en una matriz según el resultado. Para probar un elemento, calcula los mismos hashes y ve si alguno de los bits correspondientes está establecido en cero. Si es así, el artículo no puede estar en el conjunto. Por supuesto, no hay garantía de que la configuración de los tres bits signifique que el conjunto contiene el elemento. Esos tres bits pueden configurarse para elementos totalmente diferentes.
¿Por qué ayuda aumentar el número de bits? La publicación responde a eso y analiza otras optimizaciones, como un número diferente de funciones hash y el conteo.
La publicación hace un gran trabajo al explicar el filtro, pero si desea un ejemplo más concreto en C, es posible que desee leer esta publicación siguiente. O busque código en su idioma favorito. hemos hablado de Manejo de cadenas de Python con filtros Bloom antes. Incluso hemos visto una propuesta para Agregalos al autobús de tránsito.
- Distribución de relaciones públicas y contenido potenciado por SEO. Consiga amplificado hoy.
- PlatoData.Network Vertical Generativo Ai. Empodérate. Accede Aquí.
- PlatoAiStream. Inteligencia Web3. Conocimiento amplificado. Accede Aquí.
- PlatoESG. Carbón, tecnología limpia, Energía, Ambiente, Solar, Gestión de residuos. Accede Aquí.
- PlatoSalud. Inteligencia en Biotecnología y Ensayos Clínicos. Accede Aquí.
- Fuente: https://hackaday.com/2024/02/22/filters-are-in-bloom/
