Ya he aprendido otra cosa :D

por Áureo Ares

Filtros Bloom en web scraping.

marzo 24th, 2014

En mis aventuras con web scraping me encontré con un problema muy común al detectar automáticamente las URLs:

Cuando sabes lo que buscas es muy fácil fabricar un listado de URLs que necesitas revisar. Puede incluso ser una sola URL. Sin embargo, cuando necesitas ir detectando sobre la marcha nuevas URLs tienes que guardar un registro de las que ya has visitado. De lo contrario te encontrarás visitando las mismas páginas enlazadas entre sí una y otra vez hasta el fin de los tiempos.

Si sabemos que serán pocas las URLs a visitar, esto no es un gran problema. Simplemente nos guardamos una lista de las que vamos visitando y nos aseguramos de no repetir. El problema está cuando nos enfrentamos a sitios web muy grandes de los que necesitamos revisar una gran cantidad de páginas. Entonces eso de tener la lista de URLs en memoria se convierte rápidamente en una mala idea.

En estos casos, si las URLs en sí son relevantes (es decir, si cada URL es un dato que necesitas guardar por alguna otra razón) seguramente necesites una base de datos. Pero si lo único que necesitas saber es si ya has visitado antes una URL, los filtros Bloom son una opción increíblemente eficiente y rápida.

Bonita historia, pero ¿qué es un filtro Bloom?

No lo voy a explicar en profundidad ya que aparece muy bien explicado en la Wikipedia (inglés), incluyendo muchas referencias interesantes al final del artículo. De modo que comentaré lo más importante.

Las características principales de los filtros Bloom son las siguientes:

  • Tiene un cierto margen de error (falsos positivos), calculable y ajustable.
  • Al buscar un elemento, un resultado negativo significa que con toda seguridad no está en la lista.
  • Un resultado positivo significa que un elemento probablemente está en la lista (debido a la posibilidad de falsos positivos).
  • Requiere muy poco espacio en memoria y las consultas son muy rápidas.

El funcionamiento es muy sencillo, para implementarlo necesitaremos:

  • Encontrar una implementación ya realizada que nos guste (nos parezca apropiada) y podamos utilizar (licencia), en cuyo caso ya habremos terminado :D.

o

  • Una lista de elementos binarios (bit array).
  • Una o más funciones de hashing.

En mi caso necesitaba una implementación en Python ya que es el lenguaje que suelo utilizar para las tareas de scraping. La implementación de pybloom la verdad es que no me gustó nada y no encontré ninguna otra que me sirviese. De modo que opté por hacerme la mía.

La elección de la función de hashing es muy importante. El requisito indispensable es que sea uniforme (todos los posibles valores tienen la misma probabilidad de aparecer como resultado) y determinista (un mismo valor de entrada genera siempre el mismo valor de resultado). También es importante, aunque no imprescindible, que sea no criptográfica. Las funciones de hashing criptográficas están muy bien para otros usos, pero son más lentas (este es uno de los principales inconvenientes que le veo a pybloom). No soy ningún experto en hashing, pero leyendo un poco la que más me convence por el momento es MurmurHash3.

Resumiendo, para la implementación en Python utilicé lo siguiente:

Añadir un elemento al filtro:

Para añadir un elemento realizaremos varios hashes del mismo. Se pueden utilizar distintas funciones de hashing o una sola función con diferentes semillas. Teniendo ya una función que me gusta y sin saber cuántos hashes diferentes voy a necesitar, me parece más lógico utilizar una sola con diferentes semillas:

Los hashes mmh3 son numéricos, de modo que se pueden ajustar al tamaño del bitarray calculando el “módulo” (resto de división) con el operador “%”. El resultado es la posición del bitarray que marcamos a 1.

Buscar un elemento en el filtro:

Buscar un elemento en el filtro es muy parecido, simplemente comprobamos las posiciones que corresponderían al elemento que estamos buscando.

Ejemplo de filtro Bloom.

Imagen extraída de la Wikipedia, donde se muestra la idea básica de un filtro Bloom utilizando 3 hashes para cada elemento.

El tamaño del bitarray y el número de hashes:

La mayoría de implementaciones que encontré eran clases cuyo constructor recibía como parámetros el tamaño del bitarray y el número de hashes a utilizar. Aunque se puede utilizar de esta manera, en la práctica creo que es mucho más cómodo especificar lo que realmente me importa: el número de elementos que quiero guardar y el margen de error que estoy dispuesto a permitir.

Para esto es necesario calcular el tamaño del bitarray y el número de hashes necesarios para poder almacenar el número de elementos que queremos con un margen de error menor o igual al especificado. Las fórmulas y su explicación se pueden ver también en la Wikipedia, pero escritas en Python serían algo así:

Utilizo la función “ceil” para asegurarme de que se cumplen los requisitos (redondeando hacia arriba).

Uniones e intersecciones:

Algo que no he visto hasta la fecha en ninguna implementación de filtros Bloom, al menos en Python, son las operaciones de unión e intersección entre dos filtros (desde el punto de vista de teoría de conjuntos). Son increíblemente fáciles de implementar y en concreto la unión de filtros me ha resultado bastante útil.

Las intersecciones también pueden ser útiles, pero en mi caso (pocos o ningún elemento en común) los resultados no me han parecido lo bastante fiables.

Más abajo en el código final de la clase se puede ver la implementación de estas dos operaciones, pero es tan sencillo como realizar las operaciones a nivel de bit AND (&) y OR (|) entre los dos bitarray.

Mi implementación:

Esta es la clase que me hice. No es la que uso actualmente ya que más tarde hice un filtro Bloom escalable, más avanzado, que detallaré en otro artículo ya que este me está quedando más grande de lo que esperaba.

Los filtros Bloom tienen una infinidad de utilidades. Cabe destacar que esta clase fue creada específicamente para cubrir mis necesidades, por lo que hay algunas decisiones de implementación (como permitir añadir más elementos aunque el filtro esté al máximo de capacidad o devolver un valor vacío si no se puede realizar una unión) que pueden no ser buenas en otros contextos.

El código completo comentado, incluyendo la versión escalable, está alojado en Google Code.