[English version]

Introducción

Indiscutiblemente, uno de los problemas habituales a los que nos tenemos que enfrentar cuando desarrollamos aplicaciones software es el de resolver las búsquedas. En realidad, me imagino que ninguno de nosotros considera que el buscar sea una tarea excesivamente compleja. A fin de cuentas, solemos utilizar las capacidades nativas del sistema de almacenamiento, el cual se supone que nos proporciona todo lo que necesitamos, aunque a veces sea necesario crear algunos índices a la hora de mejorar el rendimiento global.

PostBusquedas_00

No obstante, el problema comienza a aparecer cuando tenemos texto, y por ello me refiero a frases o párrafos Una primera aproximación podría ser la realización de búsqueda en base a patrones, pero estoy seguro que sabéis que esta búsqueda se complica un poquito más cuando tenemos que considerar mayúsculas, minúsculas o caracteres acentuados. Para complicar todo un poquito más, la búsqueda basada en patrones no es muy eficiente cuando tenemos que buscar una palabra en medio de un texto muy largo.

Llegados a este punto me podrías decir que, bueno, a fin de cuentas todos los sistemas de almacenamiento soportan algún tipo de búsqueda sobre todo el texto. De acuerdo, es así, pero, ¿os habéis preguntado alguna vez como funciona todo esto? Quizá penséis que esto, la verdad sea dicha, no tiene demasiada importancia. Dejadme deciros algo, la innovación se basa en el conocimiento anterior, entender los conceptos básicos nos ayuda a desarrollar nuevas ideas y siempre hay casos en que las soluciones por defecto no son suficientes. Por otra parte, si sentís curiosidad por cómo funcionan los sistemas NLP debéis saber que aunque estos sistemas son mucho más complejos si comparten ciertos principios básicos con las soluciones de búsqueda de esta naturaleza.

En Divisa iT hemos utilizado estas aproximaciones para construir el sistema de búsqueda nativo de Proxia. ¿Por qué algo construido en casa? Básicamente dos razones, por una parte Proxia es agnóstico respecto a la Base de datos e introducir consultas muy dependientes de implementaciones no SQL estándar es problemático y, por otra parte, porque no soy partidario de forzar a los clientes a montar entornos artificiosamente complejos salvo que ellos tengan esa necesidad o planteamiento previo.

Describiendo el problema

A la hora de plantearnos el análisis del problema, lo primero que debemos tener en cuenta es que, a decir verdad, no existe una correlación exacta entre lo que se almacena y lo que el usuario busca. Veamos porqué, nosotros almacenamos párrafos, montones de frases y palabras de distintos tipos como, por ejemplo, sustantivos, adjetivos, adverbios. El usuario final, por su parte, introduce términos muchas veces mal escritos y, seguramente, utilizando distintas palabras derivadas aunque compartan la misma raíz que lo que tenemos guardado. Para complicar un poco más las cosas, el texto podría provenir de distintos orígenes, como texto plano, documentos en formato PDF, Word o incluso Excel.

PostBusquedas_01

Así pues, tal y como podéis percibir hay varios problemas diferentes que debemos abordar a la hora de resolver el problema en su totalidad.

• Debemos extractar el texto de sus fuentes, lo cual implica que debemos poder leer documentos Word, Excel, e incluso la pesadilla que supone leer el texto de un PDF.
• Extraer palabras, como os he comentado tenemos párrafos y frases, pero como el usuario busca términos lo que debemos hacer es localizar dichos términos en nuestro texto. Así, a bote pronto, seguro que pensáis que no es tan difícil que a fin de cuentas con buscar espacios en blanco o caracteres de puntuación es suficiente. Como primera aproximación coincido con vosotros, pero seguro que si os ponéis a pensar en las peculiaridades de nuestro idioma os dais cuenta de que hay excepciones por todos los lados.
• Transformar las palabras en tokens, para poder encontrar coincidencias tenemos que transformar tanto lo que tenemos almacenado como lo que introduce el usuario a algo común, si hablamos en un planteamiento meta-lingüistico diríamos que tenemos que extraer los lexemas. Esto, como os podéis imaginar, no es excesivamente sencillo. Pero, afortunadamente, contamos con distintos algoritmos que nos permiten obtener una solución, como mínimo aproximada.
• Corregir errores ortográficos, como sabéis es inevitable, o se equivoca en las letras o las desordena. Así que debemos utilizar algoritmos y técnicas de almacenamiento que minimicen el problema.
• Soportar varios términos queremos que el usuario busque por varias palabras y, probablemente, aplicando distintas condiciones: todas, alguna o incluso todas en el mismo orden (búsqueda literal)
• Ordenar los resultados, una tarea más compleja de lo que parece. Más que nada porque, muchas veces, tenemos que aunar las expectativas del usuario final y las de nuestro cliente. El usuario final busca lo más relevante, el cliente también pero determinando él lo que es más relevante para su organización. La verdad es que encontrar el equilibrio no es generalmente sencillo.

Un montón de cosas en las que pensar, ¿no?. Pues eso no es nada, hay muchos más temas involucrados, por ejemplo, ¿tienen todas las palabras la misma importancia cuando se busca?, ¿tienen los usuarios acceso a toda la información o solo a parte de ella? Daros una explicación completa y detallada de todos estos aspectos es inabordable, así que si estáis realmente interesados os recomiendo la lectura de este libro. Aquí me voy a limitar a daros unas pinceladas de como hemos resuelto estos problemas dentro de nuestros productos en nuestra compañía.

PostBusquedas_02

Extractando texto, palabras y frases

Mi consejo, no intentéis reinventar la rueda, hay varios proyectos open-source que resuelven este problema de forma muy satisfactoria, así que podéis mirarlos, plantearos que elementos son útiles y emplearlos en vuestras soluciones.

• Si necesitamos leer PDF debéis tener en cuenta que es un tipo de documento poco agradecido, más gráfico que documental si me permitís la expresión. Herramientas como PDFBox os permitirían resolver parte de vuestros problemas, aunque os tendréis que enfrentar a otros, desarrollando ciertos heurísticos para identificar elementos que no son "semánticamente relevantes", como pueden ser los pies de página, cabeceras. Ya sin mencionar la detección de frases (crítica para las búsquedas literales)
• Si a lo que os enfrentáis es a documentos Word u OpenOffice, herramientas como POI son las más adecuadas. Bastante potentes y realmente sencillas de emplear.
• Por otra parte, al extractar palabras, como os comentaba antes, tenéis que utilizar algún algoritmo de identificación de las mismas, quizá una aproximación básica sea suficiente o quizá prefiráis utilizar alguna solución como OpenNLP tokenizer. Además, probablemente, os tocará hacer algo más como identificar abreviaturas, acrónimos, frases y todas esas cosas maravillas del lenguaje.
• Tened en cuenta, además, que no todas las palabras son igualmente importantes. Así, por ejemplo, una preposición no es, aparentemente, muy importante, así que quizá deberíamos eliminarla de nuestra lista de palabras a fin de limitar el "ruido". Para ello necesitaríamos una lista de palabras a ignorar, buscad algo en Internet, hay muchísimas más de las que, probablemente, os podéis imaginar.
• Un último aspecto a considerar es la identificación de frases, intimamente ligado con la detección de fronteras de palabras, el conocer cuando empieza y termina una frase es sumamente relevante desde el punto de vista de contextualizar una búsqueda literal sin saltarnos fronteras

Tokenización, relevancia y almacenamiento

Antes de nada, buscar los lexemas no es nada fácil, más bien todo lo contrario. Así que no intentéis nada por vuestra cuenta, existen estupendos algoritmos que os podrían ayudar a resolver este problema.

• Porter Stemming Algorithm, hay soluciones para diferntes lenguajes de programación y lenguajes humanos – español, inglés, etc. – En realidad, este algoritmo no extrae el lexema real sino una aproximación basada en las reglas de formación de palabras.
• O bien podéis usar Hunspell para extractar los lexemas. Este algoritmo se apoya en una base de datos de palabras, así que ofrece resultados mucho más precisos que los de Porter. No obstante, es más lento y un poquito más complejo de usar que el de Porter, sobre todo si utilizáis un lenguaje basado en la JVM y os toca utilizar JNI para acceder a su funcionalidad.

PostBusquedas_03

Hagáis lo que hagáis, una vez que el paso de la tokenización ha terminado es el momento de almacenar los datos. Pero antes de ello, deberíamos calcular el peso de cada token de tal forma que podamos saber como es de importante o relevante en el ámbito del documento. Aunque puede parecer algo trivial, a fin de cuentas es contar cuantas veces aparece, no es sólo una cuestión de frecuencias, sino que existen otra serie de aspectos a considerar como, por ejemplo,

• Ni todas las frases ni todos los párrafos son igual de importantes. Por ejemplo no es lo mismo el resumen que el título, el segundo es más importante pero seguro que coincidís conmigo en que por la propia naturaleza de los resúmenes estos pueden ser más relevantes para buscar que la descripción completa.
• Por otra parte en las búsquedas no nos limitamos a un único documento sino que queremos ordenar los resultados, saber entre todos los que valen cual es el más relevante (ignorando otros muchos aspectos relativos a la ordenación). Por ejemplo imaginemos la palabra "avión", no es lo mismo que aparezca dos veces en un documento de cinco palabras a que lo haga también dos veces en un documento de ochenta. ¿Cuál es más relevante de las dos?

Una vez que tenemos esto claro, ya podemos proceder a almacenar los datos. Pensemos en el caso más simple una base de datos en el que además tenemos un sistema RBAC, en esta situación os recomendaría que utilizarais tablas organizadas como índices, puesto que el rendimiento que nos ofrecen para esta problemática es muchísimo mayor que el de las tablas tradicionales, aunque se penalizan los procesos de inserción y actualización. En cualquier caso almacenar, no es sólo guardar los tokens sino que, además,

• Si quisiéramos resaltar los resultados de la búsqueda debemos almacenar las posiciones de la palabra dentro del documento.
• Si lo que queremos es resolver problemas ortográficos, no sólo necesitaremos utilizar algoritmos como el de la distancia de Levenshthein, sino que, además, tendremos que dividir nuestras palabras en bigramas, así la palabra "avión" se guardaría como "av", "vi", "io" y "on", para luego utilizar el coeficiente de Jaccard a la hora de buscar sugerencias.
• Por otra parte, si además queremos permitir que el usuario realice "búsquedas literales" el problema se nos complica un poquito más y lo que tenemos que hacer es dividir la frase en n-gramas, en nuestro caso trigramas, así por ejemplo la frae "esto es una prueba" se convertiría en "esto$es$una", "es$una$prueba", "una$prueba$", "prueba$$".

PostBusquedas_05

Búsqueda y ordenación

Por fin, ahora ya que tenemos todo colocado en su sitio podemos realizar las búsquedas, aparentemente fácil teniendo en cuenta la estructura de almacenamiento. Pero, claro, como os comentaba antes las búsquedas no sólo involucran a un único token, sino que debemos considerar distintos criterios y condiciones. Bueno, tampoco es muy complicado, un poco de lógica binaria es suficiente para resolver el problema.

PostBusquedas_07

Así pues,

• Una búsqueda de tipo Y se satisfice cuando la suma del bit asignado a cada uno de los tokens es igual al valor total esperado..
• Una búsqueda de tipo O se satisfice cuando la suma del bit asignado a cada uno de los tokens da un valor distinto de cero

Ya, para terminar, me gustaría daros una última pincelada de como ordenar los resultados de la búsqueda. El peso, tal y como lo computamos antes, es un buen punto de entrada pero sólo si los documentos tienen la misma importancia. En caso contrario podríamos aplicar distintos heurísticos en función del caso de uso que tengamos entre manos y las expectativas del usuario final, algunos ejemplos que usamos incluyen:

• Asignar a cada tipo de documento un peso teniendo en cuenta su importancia teórica.
• Considerar el número de las visitas como un criterio de importancia. Así cuántas más visitas, aparentemente es más importante. Pero claro no debemos considerar que son igual de importantes 1.000 visitas hace 3 años que 1.000 visitas en este momento, así que debemos matizar esa importancia en función de la antigüedad.

PostBusquedas_04

En resumen

Realizar búsquedas sobre el texto no es, en realidad, complejo pero existen varios aspectos a tener en cuenta. En mi opinión, adquirir conocimientos sobre como aplicar lexemización, los diferentes algoritmos involucrados y como pueden utilizarse para mejorar los sistemas de búsqueda, aun usando aproximaciones en memoria, compensan el tiempo invertido.

Por otra parte, la búsqueda "textual" es sólo uno de los distintos tipos de búsquedas que pueden plantearse sobre la información de naturaleza textual. Sólo por comentarlo, si lo que intentáis es buscar información sobre provincias, municipios o nombres de usuario quizá un algoritmo tipo Trie sea mucho más adecuado.