Un motor de búsqueda hecho en 80 líneas de Python

 (alexmolas.com)
6 puntos por GN⁺ 2024-02-08 | 1 comentarios | Compartir por WhatsApp
  • microsearch es una implementación de juguete pensada para entender directamente el funcionamiento interno de un motor de búsqueda; la clase principal del buscador tiene menos de 80 líneas, pero el proyecto es más grande si se incluyen el crawler, la API y las plantillas HTML
  • Como contexto, parte del problema de que los sitios web y blogs pequeños no suelen ser descubiertos fácilmente por los grandes motores de búsqueda; para crear los datos de búsqueda, recopila artículos de 642 feeds RSS
  • Con crawling asíncrono basado en asyncio, el tiempo de recolección se redujo de 20 minutos a 20 segundos, y el contenido limpio se guarda como datos Parquet
  • La búsqueda funciona sobre un índice invertido que conecta palabras con la cantidad de veces que aparecen por URL, y para ordenar resultados usa BM25 basado en contenido en lugar de PageRank basado en enlaces
  • Ofrece un cuadro de búsqueda y una página de resultados con una UI en FastAPI, pero todavía no incluye funciones como operadores de consulta, indexación n-gram, expansión de consultas/documentos o indexación mientras se hace crawling

Objetivo y alcance de microsearch

  • microsearch es una implementación de motor de búsqueda en Python publicada en el repositorio de GitHub
  • Su objetivo no es ser un motor de búsqueda de producción, sino crear un ejemplo de juguete utilizable que muestre cómo funciona un motor de búsqueda por dentro
  • El contenido de búsqueda está más cerca de sitios web pequeños y blogs que no suelen ser descubiertos bien en la competencia de SEO de Google
  • La implementación central del motor de búsqueda tiene menos de 80 líneas, pero el proyecto completo es más grande si se incluye el código auxiliar, como el crawler de datos, la API y las plantillas HTML
  • La implementación surgió mientras se trabajaba con Solr y Lucene para entender con más profundidad cómo funcionan los motores de búsqueda

Crawler basado en RSS

  • Para crear los datos de búsqueda, se hace crawling de feeds RSS de blogs
  • En total se usaron 642 feeds RSS
    • Unos 100 son blogs que el autor lee directamente sobre ML, ciencia de datos, matemáticas, etc.
    • Los otros ~500 se tomaron del proyecto surprisetalk blogs.hn
  • El flujo del crawling consiste en extraer las URLs de artículos de cada feed RSS, descargar el HTML de cada artículo y luego limpiar el texto principal
  • La limpieza de HTML se hace con BeautifulSoup, eliminando script y style, y convirtiendo el contenido a texto tras ordenar saltos de línea y espacios
  • Con crawling asíncrono usando aiohttp y asyncio, el tiempo de ejecución se redujo de 20 minutos a 20 segundos
  • El resultado se arma como un DataFrame con la URL y el contenido limpio, y se guarda en output.parquet

Estructura del índice invertido

  • La primera estructura de datos clave del motor de búsqueda es el índice invertido
  • El índice invertido mapea palabras clave a documentos, permitiendo encontrar rápidamente en qué documentos aparece una palabra concreta
  • La implementación usa un defaultdict con forma dict[str, dict[str, int]]
    • La clave externa es la palabra
    • La clave interna es la URL
    • El valor interno es la cantidad de veces que esa palabra aparece en el documento de esa URL
  • La clase SearchEngine tiene dos diccionarios internos
    • _index: guarda la cantidad de apariciones por palabra y URL
    • _documents: guarda el contenido original por URL
  • index(url, content) normaliza el contenido, lo separa por espacios y aumenta el contador de apariciones de cada palabra por URL
  • bulk_index() recibe una lista de URLs y contenidos para indexar varios documentos de una vez
  • get_urls(keyword) normaliza la palabra clave y devuelve las URLs que contienen esa palabra junto con su número de apariciones

Normalización de cadenas y búsqueda básica

  • La normalización de cadenas reemplaza la puntuación por espacios, ordena los espacios duplicados y convierte todo a minúsculas
  • Para reducir diferencias entre mayúsculas y minúsculas, Foo y foo se tratan como la misma palabra clave
  • Si se indexan dos documentos de ejemplo, una búsqueda de foo devuelve ambos documentos
    • Foo: Hello, World! My name is Foo!
    • Bar: Hello, World! My name is Bar, I'm not Foo!
  • En esta etapa solo se sabe si un documento contiene el término buscado y cuántas veces aparece, así que hace falta un ranking aparte para decidir el orden de los resultados

Ranker BM25

  • Para ordenar los resultados de búsqueda se usa BM25
  • Mientras que PageRank clasifica documentos en función de enlaces, BM25 calcula puntajes con base en el contenido del documento
  • SearchEngine tiene parámetros por defecto k1=1.5, b=0.75 para calcular BM25
  • La clase ofrece propiedades necesarias para el cálculo del ranking
    • posts: lista de URLs indexadas
    • number_of_documents: número total de documentos
    • avdl: longitud promedio de los documentos
  • idf(kw) calcula la frecuencia inversa de documento de una palabra clave concreta
    • número total de documentos N
    • número de documentos que contienen esa palabra clave n_kw
    • usa la fórmula log((N - n_kw + 0.5) / (n_kw + 0.5) + 1)
  • bm25(kw) calcula el puntaje BM25 para cada URL que contiene la palabra clave
  • search(query) normaliza la consulta, la divide en palabras y devuelve la suma de los puntajes BM25 por URL para cada palabra
  • En el ejemplo, si se busca solo foo, el documento Foo obtiene una puntuación más alta que Bar; si se busca foo bar, el documento Bar obtiene una puntuación más alta

Interfaz FastAPI

  • El motor de búsqueda se expone como una pequeña app de FastAPI
  • La app crea una instancia de SearchEngine y, al iniciar, lee las URLs y contenidos desde los datos Parquet para indexarlos con bulk_index()
  • Hay tres rutas principales
    • /: renderiza la página de búsqueda y pasa la lista de artículos indexados
    • /results/{query}: ejecuta la búsqueda de la consulta y muestra las 5 URLs principales en la página de resultados
    • /about: renderiza una página informativa
  • Los resultados se ordenan en orden descendente por puntaje y luego se seleccionan solo las top-N URL
  • La UI y la UX todavía tienen mucho margen de mejora, pero la búsqueda funciona rápido y los resultados no son malos

Funciones faltantes y limitaciones

  • A esta implementación le faltan varias funciones que se esperarían en un motor de búsqueda real
  • No hay operadores de consulta
    • Por ejemplo, no soporta búsquedas que excluyan palabras específicas como how to build a search engine -solr de Google
  • No hay indexación n-gram
    • No se soporta una búsqueda como "search engine" para encontrar solo documentos donde las dos palabras aparezcan en ese orden concreto
  • No hay expansión de consulta o de documento
    • Si se busca engine, no se recuperan automáticamente documentos que contengan engines
  • El crawling y la indexación están separados
    • Se podrían integrar para indexar en cuanto llegue cada documento, y ese proceso también podría hacerse asíncrono

Siguientes pasos

  • El proyecto permitió ganar más intuición sobre cómo funciona Solr internamente
  • También confirmó que el código asíncrono tiene un gran efecto en tareas centradas en IO
  • El siguiente paso es añadir búsqueda semántica al motor de búsqueda
  • Ya se ha experimentado con modelos de embeddings y ANN, y el próximo trabajo es incorporar esa función en microsearch

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-02-08
Opiniones de Hacker News

  • Esto está realmente genial. Estoy creando con Pandas un motor de búsqueda BM25 bastante rápido para pruebas locales: https://github.com/softwaredoug/searcharray
    La razón por la que uso Pandas es que BM25 por sí solo no alcanza, y quiero calcular y combinar fácilmente con pandas/numpy otros factores como actualidad y popularidad.
    Como referencia, la búsqueda de frases es la parte difícil. El matching de frases tiene muchos casos límite, y también hay que considerar cosas como el slop. También hay que comprimir la información de posición usando la menor memoria posible: https://github.com/softwaredoug/searcharray/blob/main/searcharray/utils/roaringish.py

    • Trabajé el matching de frases en un proyecto de juguete: https://github.com/vasilionjea/lofi-dx/blob/main/test/search/inverted-search.test.ts#L140
      Creo que lo probé de forma bastante exhaustiva, pero me gustaría recibir feedback. Codifiqué la información de posición con delta encoding y luego en base36.
    • Me da curiosidad si agregar análisis de sentimiento ayudó con el procesamiento de frases o si más bien lo perjudicó. Las frases son difíciles de manejar, y estoy pensando qué se podría hacer para mejorar el rendimiento.
    • Me intriga que hayas encontrado este artículo tan rápido y hayas comentado. Me gustaría saber si usas algún tipo de herramienta de monitoreo de búsquedas que revisa la primera página para encontrar palabras clave de interés, o si fue casualidad.

  • Es cierto. La mayor parte de lo difícil en búsqueda está en manejar la escala de los datos. La lógica en sí puede ser sorprendentemente fácil, o se puede hacer fácil.
    Claro que también se puede volver infinitamente compleja, pero este proyecto eliminó muy bien lo innecesario. Si uno lo enfoca no como el problema de hacer un motor de búsqueda más grande, sino como el de hacer los datos físicamente más pequeños o aumentar la relación señal-ruido, se puede llegar bastante lejos.

  • Si uno mira src/microsearch/engine.py, hay código como SearchEngine.__init__(self, k1: float = 1.5, b: float = 0.75), pero no tengo idea de qué son k1 o b, y no hay ni un solo comentario en todo el archivo.
    ¿Hoy en día los comentarios ya no están de moda? _documents parece tener como clave la URL y como valor el contenido de esa URL, pero podría estar equivocado. Podría haber sido un material para aprender y extender cómo crear un motor de búsqueda, pero la falta de documentación hace que la calidad del código se sienta decepcionante.

    • Esa parte se explica en el artículo, y el artículo en sí funciona como documentación del código. El enlace de BM25 lleva al trasfondo matemático, y si buscas un poco más sobre los parámetros de BM25 también aparecen artículos relacionados que tratan cómo elegirlos.
    • Para hacer que el título del artículo llamara la atención, había que reducir al máximo la cantidad de líneas de código ;)
      Bromas aparte, estoy de acuerdo en que normalmente es mejor tener documentación y código juntos. Pero en este caso, como es un proyecto educativo, se decidió separar código y documentación, y documentar el código en la publicación del blog.
    • Estoy en móvil y no puedo verlo en detalle, pero k1 y b son valores de ponderación estándar usados en TF-IDF o BM25, y aquí corresponden a BM25.
      Sería útil que hubiera comentarios, pero para alguien familiarizado con este problema también son nombres inmediatamente reconocibles.
    • k1 y b son parámetros de ajuste de la función de ranking BM25. No son nombres inventados por el autor original; casi todas las implementaciones y libros de texto usan esos nombres de variables.
      Para que alguien que conoce el campo de recuperación de información lo entienda, de hecho lo correcto es nombrarlos k1 y b: https://en.wikipedia.org/wiki/Okapi_BM25
    • Cuando veo patrones como a: float, siempre me viene a la mente la charla de Rich Hickey: “no necesitas tipos, necesitas nombres correctos”.
      Realmente detesto esa tendencia, que se siente como venida de Go, de usar variables de una sola letra sin explicación y abusar del sistema de tipos como si fuera una herramienta auxiliar para los nombres. Los nombres pueden transmitir información semántica sobre lo que hace el programa, así que hay que usarlos bien.

  • No entiendo qué sentido tiene presumir la cantidad de líneas de código y no el total de \r\n, cuando se usan dependencias externas.
    No hay una unidad SI para medir una base de código, pero creo que la carga cognitiva debería medirse de alguna forma.

    • No es un criterio oficial, pero en nuestro equipo a veces aludimos a https://grugbrain.dev y decimos “este código no es grug” o “este código es bastante grug”.
    • El motor de búsqueda de 80 líneas en sí no usa dependencias externas. Solo importa collections, math y string, todo de la biblioteca estándar.
      Aunque, para ser más precisos, tal vez habría que llamarlo “motor del motor de búsqueda”. El crawler y la interfaz no están incluidos en esas 80 líneas, pero se necesitan de alguna forma, y la implementación presentada aumenta bastante tanto las líneas como las bibliotecas. Aun así, esas bibliotecas no tienen que ver con el motor de búsqueda en sí. Si empezamos a contar dependencias generales como pandas o fastapi, quizá también tendríamos que contar los millones de líneas del sistema operativo, el firmware de la tarjeta de red y la complejidad del hardware.
    • ¿Hay alguna razón por la que no debamos celebrar el logro de la industria de hacer posible construir algo así en 80 líneas?
    • Aquí sí tiene sentido. Si hubiera sido “un motor de búsqueda hecho en 4000 líneas de Python”, la mayoría lo habría dejado pasar, pero 80 líneas es lo bastante corto como para echarle un vistazo.
    • A la vieja usanza, está la complejidad ciclomática.

  • Me gusta. También es posible hacer un motor de recomendaciones de menos de 20 líneas para usar junto con el motor de búsqueda. Si guardas logs de sesión de las URL clicadas, puedes mirar una ventana deslizante después de la URL actual en cada sesión y crear una lista de recomendaciones dando más peso a los enlaces más cercanos.
    Si ordenas los resultados de recomendación y te quedas solo con los N primeros, obtienes una lista de URL recomendadas para una URL específica. Con algunos ajustes, también puedes mezclar en el log las búsquedas ingresadas y las URL clicadas para generar sugerencias ortográficas.

  • Muy genial y educativo. Pero no lo desplieguen :-)
    Hace tiempo necesité algo parecido, aunque a una escala un poco mayor, con decenas de miles de documentos, y la respuesta, como siempre, fue sqlite. Estructuralmente es igual a lo de aquí, pero con la capa de persistencia del índice invertido escrita por otra persona.

    • Uso SQLite FTS en casi todos lados y nunca me ha decepcionado.
    • De hecho, hasta incluye la misma fórmula. Gracias a este comentario me llegó como una especie de “escalofrío de comprensión”.

  • Google, si buscas con comillas dobles como "search engine", solo muestra resultados donde esas dos palabras aparecen en ese orden.
    Al menos en algunos casos, aunque lamentablemente no siempre. Lo que quieren los usuarios avanzados es “grep para la web”, no “que Google les diga lo que quiere mostrarles”.

    • Puedo asegurar que casi nadie quiere realmente “grep para la web”. Comparado incluso con un motor de búsqueda que haga apenas una expansión de consulta mínima, grep para la web es claramente peor.
      Es cierto que Google se toma demasiadas libertades al interpretar las consultas, pero hay muchas formas de procesamiento que cualquier motor de búsqueda hace y que son claramente mejores que no hacer nada. El problema de la búsqueda de Google hoy es que cuesta inferir por qué aparecen esos resultados, y parece ser porque depende demasiado de embeddings para comparar cadenas. Es frustrante cuando "cat food" coincide con "dog restaurant": en el espacio de embeddings están semánticamente cerca, pero el resultado no encaja con el razonamiento humano.

  • No me parece justo decir que son 80 líneas de código si se usan bibliotecas externas como feedparser, bs4, etc.

    • Estaría de acuerdo si estuviera hecho encima de elasticsearch, pero si la parte del motor de búsqueda real está implementada en esas 80 líneas, me parece justo. Las bibliotecas importadas son del tipo de cosas que conviene no implementar uno mismo.
      A veces hay artículos de “crea tu propio motor de búsqueda” que en realidad son guías para instalar searxng o yacy, pero este no es uno de esos casos.
    • Si esas dependencias son muy comunes y mainstream, me parece bien.

  • Está bueno. Agregarle una función de búsqueda difusa tampoco parece demasiado difícil. Por ejemplo, hacer que una búsqueda de "hackrnew" coincida con "hackernews", encontrando resultados cuya distancia de edición de prefijo esté por debajo de cierto umbral.
    La idea básica es tener otro índice invertido adicional, pero usando como clave los n-gramas (normalmente 3-gramas) de las palabras de la colección de documentos, y como postings las palabras o IDs de palabras donde aparece ese n-grama. Se puede usar el lema de que si PED(x, y) <= delta, entonces |N(x) ∩ N(y)| >= |N(x)| - n ∙ delta. Calculas los n-gramas de la entrada x, traes los postings de cada n-grama y combinas los duplicados para obtener cuántos n-gramas comparte con cada palabra candidata y. Si ese número supera el criterio, recién ahí calculas la PED real; si no, la omites, reduciendo mucho los cálculos costosos.
    Luego basta con consultar el índice existente con la lista de palabras obtenida. Usé este enfoque hace tiempo al hacer un motor de búsqueda difusa en JS del lado del cliente para https://dont.watch/. Si miras dentro del código JS, verás que el índice invertido y el índice de n-gramas comprimido se entregan tal cual como archivo JS. El motor de búsqueda real tiene unas 300 líneas de JS, sin dependencias externas, y solo incluye heurísticas muy básicas para mejorar los resultados.

    • Con ese enfoque, ¿cuánto aumenta el tamaño del índice?