Los árboles también nos ayudan a buscar documentos: un caso práctico con Mercury-settrie

La digitalización de archivos permite reproducir cientos, miles o millones de documentos en poco tiempo; pero, encontrar lo que buscamos puede resultar desalentador. En este escenario, ciertos tipos de árboles muy particulares nos ofrecen soluciones eficaces para la búsqueda de documentos.

En ciencia de datos, un árbol es una estructura jerárquica que conecta nodos, similar a las ramas de los árboles o a las raíces. Estos árboles tienen un nodo padre, a partir del cual crecen los nodos hijos. Entre las muchas estructuras de datos en árbol, nos centraremos en SetTrie, que permite realizar operaciones eficientes sobre conjuntos de datos.

Mercury-SetTrie: búsqueda eficiente de documentos en código abierto

Desde BBVA AI Factory hemos publicado recientemente una librería de código abierto llamada Mercury. Hoy nos centraremos en Mercury-settrie, un micro-repositorio disponible en esta librería que surgió de la necesidad de mejorar la implementación existente de nuestro motor de recomendación. Al codificar el algoritmo en C++ y hacerlo accesible como biblioteca de Python, obtuvimos un rendimiento 200 veces más rápido y 16 veces más eficiente en memoria que una implementación pura en Python.

SetTrie es una estructura de datos que busca y almacena conjuntos de datos de manera eficiente. Organiza los datos en una estructura de árbol, donde cada camino hacia abajo representa un conjunto. Los elementos se ordenan para permitir una búsqueda eficaz.

Una de las principales ventajas del algoritmo SetTrie es que puede utilizarse para una amplia gama de aplicaciones, como la búsqueda de texto o la compresión de datos. Además, es altamente adaptable y fácil de usar, y puede optimizarse para diferentes datos y patrones de búsqueda. En este documento presentamos el caso más sencillo: la búsqueda sobre un conjunto de documentos.

¡Manos a la obra!

Antes de continuar, asegúrate de abrir una ventana de consola. En nuestro ejemplo, utilizamos un sistema Linux. La sintaxis exacta puede variar dependiendo de la plataforma. Asegúrate de tener instalado `Python 3.8` o superior y `pip`. Actualiza `pip` a la última versión e instala `mercury-settrie`.

pip install --upgrade pip
pip install mercury-settrie

Utiliza cualquier carpeta para descargar el “The 20 Newsgroups Text Dataset”. Buscaremos cualquier documento que contenga un conjunto específico de palabras en su interior. Sólo tienes que hacer lo siguiente:

wget http://qwone.com/~jason/20Newsgroups/20news-18828.tar.gz && tar -xf 20news-18828.tar.gz

A continuación, asegúrate de que tienes tu intérprete de Python preferido, ya sea Jupyter, un IDE, o el intérprete de Python directamente, abierto y listo para usar, de modo que puedas ejecutar los ejemplos de código. En primer lugar, escribimos una función de ejemplo elemental que convierte el contenido de un archivo de texto en el conjunto de sus palabras.

def words(file_name):
    # 1. Read as a list of strings, one line per string, ignoring encoding errors.
    with open(file_name, errors = 'ignore') as f:
        txt = [s.rstrip('n') for s in f.readlines()]

    # 2. Remove anything that is not a letter or a number.
    rex = re.compile('[^a-zA-Z0-9 ]')
    txt = [rex.sub('', s) for s in txt]

    #3. Split by space and push everything into a set.
    ret = set()
    for s in txt:
        ret.update(s.split(' '))

    return ret

Ahora sólo tenemos que crear un objeto SetTrie y rellenarlo con las palabras de cada documento.

import os, re, settrie

st = settrie.SetTrie()

for path, _, ff in os.walk('20news-18828'):
    for f in ff:
        file_name = '%s/%s' % (path, f)

        st.insert(words(file_name), file_name)

¡Eso es todo! El objeto `st` es un SetTrie. Ahora, puedes consultar los datos en tiempo logarítmico. El objeto es pythonic. Se puede guardar y cargar como un pickle y devuelve un iterador como resultado de cualquier consulta. Aquí, convertimos el iterador en una lista usando `list()` y proporcionamos la consulta como un conjunto de palabras.

it = st.supersets({'SunView', 'XView'})
print(list(it))

Si has llegado hasta aquí, ya tienes una implementación sencilla de una búsqueda de documentos muy eficiente que puedes personalizar para adaptarla a tus necesidades.

Conclusiones

El algoritmo SetTrie es una solución eficiente y versátil para buscar y almacenar conjuntos de datos. Utilizando este algoritmo, podemos hacer que la búsqueda de documentos sea más rápida y eficiente a la vez que contribuimos a la conservación de nuestros bosques. Para ver todo lo que la biblioteca puede hacer, consulta la documentación y ¡empieza a utilizar mercury-settrie!