Desarrollo de motores de búsqueda utilizando herramientas open source

1.6.1 Lucene

Lucene es el corazón de la mayoría de los motores de búsqueda de hoy en día. Básicamente acepta el texto que se va a buscar, lo almacena en una estructura de datos (índice invertido) y, luego, acepta varios tipos de consultas de búsqueda y devuelve un conjunto de resultados que coinciden con los criterios de búsqueda.

Muchas soluciones de búsqueda basadas en servidor, como Apache Solr o ElasticSearch, están construidas sobre Lucene y marcan una evolución en el desarrollo de motores de búsqueda. El objetivo del diseño de estas herramientas es ofrecer un tipo de soluciones que proporcionen escalabilidad y alta disponibilidad a la base que trae Lucene como motor de búsqueda.

En los últimos años han surgido diferentes proyectos de la fundación Apache que también se consideran parte del universo de Lucene. Aunque estos proyectos son independientes, y más conocidos en otros contextos, se pueden integrar de forma sencilla con Lucene. Entre estos proyectos podemos destacar Hadoop, Mahout (un framework para aprendizaje automático), Nutch (una aplicación de búsqueda basada en Lucene) y Tika (que permite analizar documentos en diferentes formatos, como PDF, y se puede utilizar para alimentar con datos un índice de Lucene).

• Hadoop: http://hadoop.apache.org

• Mahout: http://mahout.apache.org

• Nutch: http://nutch.apache.org

• Tika: http://tika.apache.org

Apache Lucene guarda toda la información en una estructura llamada índice invertido. Se trata de una estructura de datos donde para cada término que encontramos en los diferentes documentos, obtiene los índices donde aparecen. Puede pensar en el índice invertido como en una estructura de datos donde estos están orientados a términos en lugar de a documentos.

Entre los conceptos clave que podemos encontrar en Lucene destacan:

• Index: colección de documentos con similares características.

• Type: partición lógica que contiene aquellos documentos que comparten información a través de un atributo.

• Document: unidad básica de información.

• Mapping: incluye datos sobre cómo la información se almacena en el índice en forma de atributos y propiedades, y sobre cómo se debe tratar un campo a la hora de hacer las búsquedas, a nivel de extraer tokens de una determinada cadena de búsqueda.

• Relevancia: son los algoritmos utilizados para clasificar los resultados basados en la consulta.

• Corpus: colección de todos los documentos del índice.

• Segmentos: datos fragmentados que almacenan el índice invertido y permiten buscar en el índice de una manera eficiente.

1.6.2 Índice invertido

El índice invertido es el corazón del motor de búsqueda. Es como una estructura en formato diccionario en un formato clave-valor, donde las claves son los términos que hemos generado con los n-gramas de todos los documentos. Cada índice invertido almacena la posición y el identificador del documento. Para cada término nos dice en qué documentos (indica la posición) aparece cada uno.

El índice invertido se crea por temas de optimización y son las estructuras de datos las que permiten realizar búsquedas sobre los documentos. Por ejemplo, Lucene, debido a su índice invertido, es uno de los motores más rápidos la hora de buscar un término en un campo. Cada campo que se indexa en Lucene se convierte en una estructura de búsqueda rápida para su tipo particular donde, por ejemplo, los campos de texto se dividen en tokens y los campos numéricos se convierten en sus representaciones binarias.

1.6.3 Apache Solr

Apache Solr es un motor de búsqueda de código abierto basado en la librería de búsqueda, escrita en Java, Lucene. Al haber sido desarrollado durante varios años y con las colaboraciones de la comunidad de desarrolladores, ha conseguido mejorar sus funcionalidades con el paso del tiempo. Apache Solr, además, provee diversas API para realizar desarrollos que precisen del uso del motor de búsqueda para recuperar información, y es muy sencillo trabajar con él gracias a su funcionalidad transparente al usuario. Para su ejecución, requiere de una máquina o servidor local y tener instalada la JVM (Java virtual machine) en el sistema.

1.6.4 ElasticSearch

ElasticSearch es un motor de búsqueda open source y, al igual que Apache Solr, está basado en la librería de búsqueda de Java Lucene. Sin embargo, ElasticSearch ha centrado su desarrollo en optimizar su funcionamiento y ha intentado ofrecer siempre funcionalidades que operan como motor de búsqueda de forma óptima. Esto quiere decir que, aunque provee numerosas API de desarrollo, intenta dejar la funcionalidad ajena al proceso de búsqueda a selección del desarrollador. Aun así, ElasticSearch es hoy en día uno de los mejores motores de búsqueda debido a lo bien construido que está y a una gran comunidad de usuarios que respalda el proyecto.

El hecho de que ElasticSearch utilice Lucene para resolver las búsquedas supone una ventaja en comparación con otros sistemas de consulta de bases de datos SQL. Una llamada a una API nos permite realizar búsquedas utilizando objetos JSON, lo cual resulta mucho más flexible y da a cada parámetro de búsqueda dentro del objeto un peso, importancia y/o prioridad diferentes.

Por ejemplo, insertar un documento en ElasticSearch es tan fácil como llamar al API REST que proporciona y enviar un objeto JSON mediante el método POST; si va a actualizar un documento, se utiliza el método PUT. Entre las ventajas que ofrece ElasticSearch destacamos:

• Podemos añadir un documento sin crear un índice.

• Si el índice no ha sido creado, ElasticSearch creará automáticamente el tipo de asignación y los campos al añadir un documento.

• ElasticSearch lo que hace internamente es deducir los tipos de datos basados en los del documento.

• En ElasticSearch, todas las conversiones de tipos se gestionan automáticamente. La búsqueda de un término es archivada por ElasticSearch utilizando el formato correcto para el campo.

1.6.5 Otros motores de búsqueda

Dentro del mercado IT podemos encontrar otros motores de búsqueda, entre los que podemos destacar:

• Splunk (https://www.splunk.com) es una plataforma y un motor de búsqueda orientado a las anaĺíticas para el Big Data.

• Algolia (https://www.algolia.com). Algolia’s Search es un producto que se ofrece como un SaaS (software as a service). Se trata de un servicio al que se accede a través de una plataforma web y que permite al usuario subir colecciones de documentos y realizar consultas sobre ellos. Para interactuar con la plataforma, aparte del propio servicio web, el servicio ofrece API (interfaz de programación de aplicaciones) de acceso para poder acceder desde otras aplicaciones a los recursos de Algolia.

• Amazon CloudSearch (http://aws.amazon.com) es un motor de búsqueda para soluciones software con servicio cloud que se oferta desde Amazon Web Services. Es el producto más conocido de computación de servicios en la nube de la compañía Amazon. Este motor de búsqueda permite, tras registrarse en la plataforma, subir documentos y realizar búsquedas en ellos. Para construir aplicaciones que empleen los recursos de Amazon CloudSearch, la plataforma provee una API que permite el desarrollo de aplicaciones diversas, aunque principalmente de tipo web.

• SearchBlox (https://www.searchblox.com) es un producto de pago, que sus distribuidores definen como el mejor sustituto para ElasticSearch o Google Search Appliance. El servicio se ofrece como búsqueda en la nube, al igual que entornos como Microsoft Azure Search o Algolia. Sin embargo, ofrecen también la instalación del servicio en local en cierto tipo de servidores. El servicio provee también un potente sistema de búsqueda accesible a través de una API para desarrolladores, que permite a los usuarios que lo deseen emplear este servicio en caso de necesitarlo.

• Sphinx Search Server (http://sphinxsearch.com) es otro motor de búsqueda de código abierto desarrollado en C++. A pesar de ser muy potente, es relativamente complejo de manejar, debido a que se ha diseñado para ser altamente configurable y porque la mayor parte de la documentación y recursos que aporta son muy escasos. Sin embargo, es un motor de búsqueda muy completo y versátil, que puede actuar en ocasiones de gestor de bases de datos, y con una fuerte comunidad detrás que lo mantiene actualizado. Sphinx es una de las alternativas recomendadas para aquellos que busquen personalizar su motor de búsqueda ya que, a través de diferentes opciones, ofrece la posibilidad de afinar el algoritmo de relevancia, así como de indicar índices o determinar parámetros que deberán ser tenidos en cuenta en cada búsqueda.

1.7 HERRAMIENTAS DE PROCESAMIENTO DE LENGUAJE NATURAL (PLN)

Las tecnologías de procesamiento de lenguaje natural son un conjunto de herramientas lingüísticas que permiten extraer información relativa a características léxicas, morfosintácticas y semánticas de un determinado texto.

Existen muchas propuestas en este ámbito, y entre ellas destacan las siguientes:

• OpenNLP (https://opennlp.apache.org) es un proyecto de la fundación Apache que consiste en una librería de aprendizaje automático cuyo objetivo es el procesamiento del lenguaje humano en texto. Posee soporte para las tareas de procesamiento de lenguaje natural (PLN) más comunes. No tiene soporte para el uso de distintos idiomas, pero posee una serie de modelos entrenados en diferentes idiomas para propósitos específicos. En el caso del español, encontramos cuatro modelos entrenados en reconocimiento de entidades: personas, organizaciones, localizaciones y misceláneo. Cualquier extractor de interés que no esté en los modelos tendría que ser entrenado para su objetivo específico.

• CoreNLP (https://stanfordnlp.github.io/CoreNLP) es un proyecto de la Universidad de Stanford que provee una serie de herramientas de análisis de lenguaje humano (figura 1.5). Proporciona instrumentos para un amplio análisis gramático, además de diferentes elementos de extracción de la información. Posee soporte oficial para seis idiomas, aunque no todos tienen disponibles todas las funciones. La integración con otros proyectos se realiza a través de una serie de API en distintos lenguajes. A nivel práctico, esta herramienta es utilizada por la Biblioteca Virtual Miguel de Cervantes, concretamente en el componente correspondiente al analizador sintáctico: http://data.cervantesvirtual.com/analizador-sintactico-automatico.

• FreeLing (http://nlp.lsi.upc.edu/freeling/node/1) es un proyecto de la Universitat Politècnica de Catalunya (figura 1.6). Se trata de una librería con una serie de herramientas open source para el análisis de lenguaje humano. Está escrita en C++ y tiene soporte para muchos idiomas y dialectos españoles, pero carece de una comunidad sólida que utilice la herramienta de manera asidua; tampoco cuenta con una documentación tan extensa como las propuestas anteriores.

Tanto CoreNLP como FreeLing proporcionan una web para demostraciones en la que puede insertar texto y extraer características.

http://nlp.stanford.edu:8080/corenlp/process

Figura 1.5 Prueba de texto con CoreNLP.

http://nlp.lsi.upc.edu/freeling/demo/demo.php

Figura 1.6 Prueba de texto con FreeLing.

Capítulo 2
APACHE LUCENE

Apache Lucene (http://lucene.apache.org) es una librería para la recuperación de información que permite añadir funcionalidades de búsqueda a cualquier aplicación realizada en Java. En los últimos años, se ha convertido en la librería de referencia para implementar herramientas de recuperación de información, llegando a ser casi un estándar. Es importante destacar que Lucene no es una herramienta de búsqueda en sí misma, ya que no proporciona una interfaz de usuario, sino una librería más a bajo nivel que proporciona funcionalidades de recuperación de información que se pueden añadir a cualquier aplicación.

Apache Lucene ha sido ampliamente usada por su utilidad en la implementación de motores de búsqueda y es útil para cualquier aplicación que requiera indexado y búsqueda de textos. A pesar de que Lucene está desarollada en Java, podemos encontrar implementaciones en otros lenguajes, que podemos ver en http://cwiki.apache.org/lucene-java/LuceneImplementations.

Entre los principales objetivos de este capítulo podemos destacar:

• Comprender la arquitectura a nivel de clases e interfaces que proporciona Lucene.

• Conocer y comprender la funcionalidad de los componentes básicos de un motor de búsqueda basado en Apache Lucene.

• Comprender el concepto de índice invertido de Apache Lucene.

• Conocer el proceso de tokenización y búsqueda en Apache Lucene.

2.1 INTRODUCCIÓN A APACHE LUCENE

Apache Lucene permite a los desarrolladores integrar funciones de indexación y búsqueda de información textual dentro de sus proyectos. También permite la búsqueda de texto completo, es decir, permite buscar en un conjunto de documentos de texto uno o más términos definidos por el usuario. Para poder utilizar Lucene, es necesario seguir una serie de pasos o fases para conseguir realizar búsquedas efectivas: indexación y búsqueda.

• Indexación: el proceso de indexación consiste en analizar y extraer de entre toda la información disponible la verdaderamente relevante. Posteriormente, con esa información se crea el índice a partir del cual se realizarán las búsquedas. El índice es una estructura de datos que permite acceso rápido a la información (algo similar a lo que podría ser el índice de un libro).

• Búsqueda: el proceso de búsqueda consiste en consultar el índice para obtener los documentos donde aparecen unas determinadas palabras o una determinada expresión de consulta.

En la base de la arquitectura de Lucene se encuentra el concepto de documento (Document) que contiene campos (Fields) de texto. Esta flexibilidad permite a Lucene ser independiente del formato del fichero. Lucene soporta la indexación de textos que se encuentran en muchos tipos de documentos, como documentos PDF, páginas HTML y documentos de Microsoft Word.

El índice es el elemento más importante en el proceso de búsqueda con Lucene y se considera el corazón de un motor de búsqueda, ya que en él se almacenan todos los términos de todos los documentos. Se trata de un tipo de índice invertido, que consiste principalmente en una tabla donde se guarda la posición de cada término. No obstante, para poder crear un índice, primero es necesaria la extracción de todos los términos de todos los documentos —proceso que cada usuario o desarrollador puede configurar individualmente—. En la configuración, los desarrolladores establecen qué campos quieren incluir en el índice.

Los objetos con los que Lucene trabaja son documentos de cualquier tipo. Estos documentos contienen una serie de campos e incluyen información relativa a la información que queremos almacenar (como el nombre del autor, el título del documento o el nombre del archivo). Cada campo tiene una designación y un valor único, de forma que, al crear el índice, el usuario puede decidir qué metadatos quiere incluir.

En la indexación de los documentos, tiene lugar también un proceso que se conoce como tokenización. Para una máquina, un documento es ante todo un conjunto de información. Incluso cuando se pasa del nivel de los bits al de contenido legible para los humanos, un documento sigue estando compuesto por una serie de signos: letras, puntuación, espacios, etc.

A partir de estos datos, se crean los segmentos de tokenización y, posteriormente, los términos (en su mayoría palabras) que finalmente van a poder buscarse. La forma más sencilla de ejecutar este tipo de tokenización es ir separando en tokens cada vez que se encuentre un espacio en blanco. Sin embargo, este método pierde su utilidad cuando un término está compuesto por varias palabras separadas, como puede ser el caso de “sin embargo”. Para solucionarlo, se recurre a diccionarios adicionales que se pueden implementar también en el código Lucene.

La principal ventaja que aporta este motor de búsqueda es que devuelve los resultados de la búsqueda ordenados en función de la similitud con los términos de búsqueda introducidos por el usuario.

Lucene, primero, crea un índice invertido para los documentos en una colección. Como vimos, un índice invertido consiste en una lista alfabética de todas las palabras que aparecen en los documentos de texto. Cada entrada en esta lista contiene punteros que hacen referencia a todos los documentos que contienen cada palabra. De esta forma, cuando un usuario busca una palabra, el algoritmo se coloca en la posición apropiada en el índice y devuelve los documentos a los que se hace referencia.

La indexación invertida es una técnica rápida y fiable para generar índices de búsqueda, incluso para grandes cantidades de datos. Por ejemplo, una colección de textos que contiene 1 000 documentos con un promedio de 200 palabras cada uno, tendría un total de aproximadamente 200 000 palabras. Si la búsqueda de una palabra tuviera que pasar por toda la colección, el algoritmo tendría que hacer 200 000 comparaciones de palabras.

Por el contrario, el índice invertido contiene una sola entrada para cada palabra. El número de entradas dependerá de los documentos a indexar pero, por regla general, el tamaño de un índice invertido casi siempre estará por debajo del número total de palabras. Por ejemplo, si tenemos una colección de documentos de 200 000 palabras, esto podría generar un índice invertido de 10 000 palabras.

Otra de las ventajas de usar un índice invertido es que es más fácilmente escalable, ya que el número de palabras diferentes (el vocabulario) crece de forma más lenta que el número total de palabras. En algún momento, los nuevos documentos añadidos a la colección generarán muy pocas o ninguna entrada nueva en el índice, ya que las entradas existentes en el índice recibirán más referencias (punteros) para las palabras correspondientes a los nuevos documentos.

De esta forma, la frecuencia real de las palabras en un documento o una colección de documentos se acercará a la distribución descrita por la Ley de Zipf a medida que la colección de documentos se hace más grande.

La Ley de Zipf (https://es.wikipedia.org/wiki/Ley_de_Zipf) describe una distribución estadística de frecuencias de palabras presentes en todos los idiomas donde la probabilidad de que una palabra aparezca en un documento es inversamente proporcional a la frecuencia de aparición de cada una de las palabras. Dicha ley establece que la palabra más frecuente de un texto aparece el doble de veces que la siguiente más frecuente, tres veces más que la tercera más frecuente, cuatro veces más que la cuarta más frecuente, y así sucesivamente.

De esta forma, en términos matemáticos, la ley afirma que si se ordenan todas las palabras por frecuencia de uso, la segunda más frecuente aparece 1/2 veces el número de veces que aparece la más frecuente; la tercera, 1/3 veces; y, en general, la que ocupa la posición n aparece 1/n veces que la más frecuente.

2.2 MÓDULOS Y FUNCIONALIDADES DE APACHE LUCENE

Lucene permite indexar y realizar búsquedas sobre cualquier conjunto de datos que se puedan extraer de un texto, independientemente de cuál sea la fuente, el formato o el idioma. Esto permite que se puedan indexar y buscar datos almacenados en ficheros contenidos en páginas web o en servidores remotos, documentos almacenados en sistemas de archivos locales, ficheros de texto, documentos de Word, XML, HTML, archivos PDF o cualquier otro formato del que se pueda extraer información textual.

La búsqueda de texto es un proceso que consiste en encontrar términos en un índice para acceder a los documentos en los que aparecen. Tanto la recolección de datos como la generación de documentos son tareas específicas de cada aplicación y que, por lo tanto, Lucene no implementa. Además, tampoco proporciona ningún tipo de interfaz, por lo que cada aplicación deberá generar las suyas propias. Entre los módulos que aporta Lucene podemos destacar:

• Análisis de documentos (Analyze Document): Lucene proporciona diferentes analizadores que permiten controlar este proceso y ofrece la posibilidad de personalizar los analizadores que encontramos por defecto o crear uno nuevo combinando sus funcionalidades para tokenizar y filtrar los tokens, de manera que el proceso de creación de tokens puede ser personalizado.

• Indexado de documentos (Index Document): módulo que permite añadir los documentos al índice. Lucene almacena los documentos en una estructura de índice invertido, lo que hace más eficiente el almacenamiento del índice en el disco y agiliza las búsquedas.

• Construcción de la consulta (Build Query): cuando un usuario utiliza una aplicación de búsqueda, generalmente lo hace a través de un formulario web en el que introduce una consulta que el navegador envía al servidor web que contiene el motor de búsqueda. Una vez recibida, se debe transformar en una Query del motor de búsqueda; este proceso es el que engloba el módulo de “Construcción de la consulta”.

• Ejecución de la consulta (Run Query): es el proceso de consultar el índice de búsqueda y recuperar los documentos que coinciden con la Query solicitada. Lucene encapsula este paso, proporcionando una API para realizarlo de forma sencilla; aunque también permite personalizarlo, de forma que se pueda realizar el filtrado y ordenamiento de los resultados.

• Interpretación de resultados (Render Results): consiste en generar una lista de resultados que el usuario pueda entender y utilizar de forma sencilla. Esta lista se genera a partir de la lista interna de identificadores de documentos ordenados que concuerdan con una consulta.

El proceso de análisis comienza con la tokenización del texto, es decir, con la extracción de cadenas o palabras que lo componen, y que se conocen como tokens. Para generar los tokens, se aplican al texto diferentes procesos, como la extracción de palabras, la eliminación de los signos de puntuación, la normalización (paso a minúsculas), el stemming (reducción de las palabras a su forma raíz) o la lematizacion (la transformación de las palabras a su forma básica). Los tokens, combinados con el nombre de su campo asociado, forman los términos.

La aproximación de Lucene se basa en combinar diferentes modelos de espacio vectorial y booleano, y ofrece la posibilidad de decidir cuál de ellos usar a la hora de realizar una consulta. La fase de ejecución de la consulta termina cuando Lucene devuelve una lista de documentos que se debe transformar en una salida que el usuario pueda comprender y analizar.

Para la indexación y recuperación del contenido textual de los documentos que gestiona bastaría con utilizar alguno de los analizadores que proporciona por defecto Lucene. Pero si se quieren potenciar las búsquedas de modo que no se produzca demasiado ruido en los resultados y se encuentren documentos similares, hay que conseguir que los documentos estén lo más normalizados posible.

El proceso de normalización de los documentos se puede realizar utilizando alguna de las librerías que facilitan los siguientes procesos:

• Eliminación de stopwords: son palabras de uso frecuente que no se tienen en cuenta ni en el proceso de indexación ni en el de búsqueda.

• Stemming: es un método para obtener la cadena raíz —no necesariamente léxica— de una palabra, mediante el que las palabras se reducen a su raíz lingüística o a su stem. El proceso de stemming es muy útil para el inglés, aunque para el castellano no siempre se puede aplicar porque el stem de una palabra no tiene por qué coincidir con su raíz léxica.

Al analizar los datos de los que forma parte el proceso de tokenización, Lucene también ejecuta un proceso de normalización. Esto significa que los términos se convierten a una forma estandarizada, de modo que, por ejemplo, todas las mayúsculas se escriben en minúscula. Además, Apache Lucene introduce una clasificación mediante una serie de algoritmos (por ejemplo, a través de la medida TD-IDF), con la que es posible obtener los resultados más relevantes.

Lucene se encarga de construir y gestionar lo que se denomina índice invertido, una estructura de datos especializada que permite emparejar documentos de texto con términos de consulta del usuario. Las características principales de estos motores son:

• Escalables: capaces de distribuir el trabajo (indexación y procesado de consultas) entre múltiples servidores en un clúster.

• Listo para ser desplegado: ambas soluciones vienen con ejemplos prácticos para levantar un servicio con el mínimo esfuerzo.

• Optimizados para búsquedas: son rápidos, muy rápidos, capaces de ejecutar consultas complejas en decenas de milisegundos.

• Grandes volúmenes de datos: están diseñados para almacenar índices de millones de documentos.

• Centrados en texto: la principal ventaja que aporta es la posibilidad de manejar textos, extrayendo su estructura implícita al índice del motor para mejorar la búsqueda.

• Resultados ordenados por relevancia: dependiendo de la consulta del usuario, se le devuelven documentos clasificados en base a dicha consulta por orden de relevancia.

Dado que Lucene subdivide los documentos en campos de texto y los clasifica de forma lógica, la búsqueda de texto completo con Lucene funciona de forma muy precisa y responde bien al encontrar resultados relevantes para textos y documentos similares. Mientras reconozca un texto, el formato (texto plano, PDF, HTML u otros) es lo de menos porque, en lugar de indexar archivos, Lucene trabaja con texto y metadatos, aunque los archivos se han de extraer de la biblioteca de todas las formas posibles.

Para ello, el equipo de Lucene ha desarrollado el proyecto Apache Tika (https://tika.apache.org/index.html), que es una herramienta para el análisis, traducción e indexación de textos. La herramienta lee texto y metadatos de diferentes tipos de archivos y, posteriormente, extrae el texto y lo pone a disposición para su tratamiento posterior. Esta herramienta consta de un analizador (parser) y un detector. El analizador examina los textos y estructura el contenido en una jerarquía ordenada, mientras que el detector tipifica el contenido (por ejemplo, reconociendo el tipo de archivo y el tipo de contenido a partir de los metadatos).

Entre las funciones y características más importantes de Lucene podemos destacar:

• Indexación rápida, tanto en fases como por lotes (hasta 150 GB por hora, según sus desarrolladores).

• Uso económico de la memoria RAM.

• Escrito por completo en Java y, por lo tanto, multiplataforma (las variantes en lenguajes de programación alternativos son Apache Lucy y Lucene.NET).

• Interfaz para plugins.

• Búsqueda por campos de texto (categorías como contenido, título, autor, palabra clave), también para varios al mismo tiempo.

• Clasificación por campos de texto.

• Listado de los resultados de la búsqueda según similitud o relevancia.