Desarrollo de motores de búsqueda utilizando herramientas open source

1.3 FUNCIONAMIENTO DE UN MOTOR DE BÚSQUEDA

Un motor de búsqueda es un programa que permite localizar en un conjunto de documentos aquellos relacionados con una palabra o palabras clave seleccionadas. Para ofrecer esta funcionalidad, se exploran los ficheros existentes en el sistema de forma eficiente, registrando información relevante sobre ellos en una base de datos. Esta base de datos es empleada por el motor para permitir a los usuarios realizar consultas y localizar esos documentos de forma más sencilla.

Así pues, para conseguir esta funcionalidad, existen varios componentes principales que permiten al motor de búsqueda realizar estas operaciones:

• Crawler o Spider: así se denomina el proceso que recorre el conjunto de documentos almacenados, ya sea en una máquina o en una red, que recoge los metadatos y la ubicación de los mismos para, posteriormente, guardar un registro de todos ellos y permitir su rápida localización y presentación al usuario. En colecciones de documentos reducidas, esta operación no le supone una gran cargabilidad al proceso. Sin embargo, en entornos como Internet, se precisa de un proceso que esté de forma continuada verificando los enlaces que forman una web, dado que la situación de los elementos es más dinámica y varía con el tiempo.

• Índice: el índice se puede describir como el conjunto de información recopilada por el crawler y que se almacena en un registro; se denomina índice de búsqueda. Estos datos son los que emplea posteriormente el motor para escoger los elementos que cumplen con la petición del usuario a través de las palabras clave que conforman la consulta.

• Algoritmo de ordenación: si el índice es el corazón del motor de búsqueda, el algoritmo de ordenación es el cerebro, ya que es el responsable de recoger los datos del índice de la forma más adecuada posible, devolviendo al usuario los resultados por orden de relevancia. Es interesante que los datos más relevantes sean siempre los primeros en aparecer, según diferentes criterios de ordenación. Se permite que estos criterios, en ocasiones, sean personalizables bajo ciertos requisitos, lo cual dota al algoritmo de cierta flexibilidad y adaptación. Esto permite al motor adaptarse a las necesidades reales del entorno empresarial o del usuario.

De los elementos comentados, el índice se puede considerar como el corazón del motor de búsqueda. El índice y el algoritmo de ordenación empleado son los elementos diferenciadores que actualmente permiten la existencia de una gran diversidad de motores de búsqueda.

1.3.1 Buscadores de directorios

Los buscadores de directorio buscan información sobre contenidos de la página, y los resultados se presentan haciendo referencia a los contenidos y temática del sitio. Los algoritmos para este tipo de motor de búsqueda son más sencillos, y los sitios se presentan como enlaces, los cuales representan los sitios registrados. Estos tipos de buscadores no recorren los sitios web ni almacenan sus contenidos; lo que hacen es registrar algunos de los datos de la página web, como el título y la descripción (que normalmente se introducen en el momento de registrar el sitio en el directorio).

1.3.2 Buscadores jerárquicos

Este tipo de motor de búsqueda recorre las páginas coleccionando información sobre sus contenidos. Cuando se inicia una búsqueda de información concreta en los buscadores, ellos consultan su base de datos y presentan resultados clasificados por su distinción para esa búsqueda concreta. Los buscadores pueden almacenar en sus bases de datos desde la página de entrada de cada web hasta todas las páginas que residan en el servidor, una vez que el buscador la haya reconocido e indexado.

Debido a que los motores de búsqueda contienen millones —y a veces miles de millones— de páginas, muchos motores de búsqueda no solo se centran en el proceso de búsqueda, sino que también muestran los resultados en función de su importancia. Esta importancia de los resultados se determina normalmente mediante el uso de diversos algoritmos.

1.3.3 Spiders (arañas o crawlers)

Spider o araña es el nombre que se le ha dado al componente que se encarga de rastrear la web siguiendo su estructura hipertextual, para almacenar los enlaces en un lugar para su posterior análisis. En muchas ocasiones es llamado también crawler o webcrawler. Cada cierto tiempo, los spiders recorren la web para actualizar los contenidos recopilados con anterioridad; por ejemplo, los sitios de noticias y los blogs que están en constante actualización son analizados frecuentemente por estos programas. Además, los spiders pueden trabajar de forma conjunta, funcionando como una red de spiders, para obtener más documentos y almacenarlos en un repositorio o base de datos.

Figura 1.1 Funcionalidad de una araña o web crawler.

Como se puede observar en la figura 1.1, la fuente de todos los datos del motor de búsqueda es un crawler, que visita automáticamente las páginas y los índices de sus contenidos. Una vez que una página ha sido rastreada, los datos que contiene se procesan.

Los motores de búsqueda pueden realizar distintos tipos de búsquedas, ya sea por fecha, por un campo específico o por temas; en los siguientes puntos se explican algunos tipos :

• Restringido campo de búsqueda. Permite a los usuarios realizar su búsqueda sobre un determinado campo dentro de un registro almacenado de datos, por ejemplo “Título” o “Autor”.

• Consultas booleanas. Se hace uso de operadores booleanos para aumentar la precisión de una búsqueda.

• Búsqueda de concordancia. Produce una lista alfabética de todas las palabras principales que se encuentran en un texto con su contexto inmediato.

• Búsqueda de proximidad. Incluye solo los documentos que contienen dos o más palabras separadas por un número determinado de palabras.

• Expresión regular. Emplea una sintaxis para realizar consultas más complejas.

• Búsqueda facetada. Consiste en encontrar elementos o contenidos restringiendo el conjunto global de resultados a través de múltiples criterios o facetas, lo cual permitirá realizar la búsqueda mediante cualquier metadato del grafo semántico de una determinada entidad.

1.4 PROCESO DE INDEXACIÓN

El proceso de localizar y recuperar cada contenido de un archivo se conoce como indexación. Una palabra clave, asociada a un identificador de un archivo específico, se incluirá en un índice para, posteriormente, conocer la posición exacta de cada archivo y posibilitar el análisis de frecuencias de cada palabra. La mayoría de las herramientas de acceso a la web están basadas en indexación automática, que no es más que la indexación que se realiza a través de procedimientos algorítmicos.

Además, el proceso de indexación puede mejorar el rendimiento de las consultas, ya que los datos necesarios para satisfacer las necesidades de la consulta existen en el propio índice y se reduce al máximo el tamaño de los archivos; por lo tanto, se reducen también las operaciones de lectura y escritura sobre el disco.

En el proceso de indexación, para agilizar la búsqueda de grandes cantidades de datos es necesario hacer uso de índices, ya que estos mejoran la velocidad de las operaciones, de modo que el acceso a la información es más rápido.

Cuando el número de archivos a buscar es potencialmente de gran tamaño, o la cantidad de consultas de búsqueda por realizar es considerable, el problema de búsqueda a menudo se divide en dos tareas: la indexación y la búsqueda. La etapa de indexación analizará el contenido de todos los archivos y creará una lista de los términos de búsqueda, a menudo llamada índice. En la etapa de búsqueda, al realizar una consulta específica, esta se realiza utilizando el índice en lugar de utilizar el contenido de los documentos originales.

1.4.1 Rendimiento en la indexación de documentos

A la hora de almacenar documentos hay que tener en cuenta que uno de los factores más importantes es el rendimiento. Los factores que afectan al rendimiento son: el número de campos a indexar o almacenar, el número de registros que se introducen, el tamaño de los documentos a indexar y el tipo de documento que se indexa (pdf, txt, xml, etc.).

En este punto, el proceso de indexación trata de reducir al máximo el tamaño de los archivos o tablas de la base de datos, para conseguir la mejor relación entre tiempo de ejecución de las consultas y exhaustividad del fichero inverso. Para ello, vamos a introducir los siguientes conceptos:

• stopwords: se trata de una lista de palabras de uso frecuente que no se tienen en consideración ni en el proceso de indexación ni en el de búsqueda.

• stemming: es un método para obtener la raíz semántica de una palabra. Las palabras se reducen a su raíz o stem (tema).

1.4.2 Stopwords

Las stopwords son palabras que no contienen un significado importante, por lo que no serán utilizadas en las consultas de búsqueda.

Se trata de una técnica de indexación que genera una lista de palabras de uso frecuente que no se tendrán en consideración y que se omitirán tanto en el momento del proceso de indexación como en el proceso de búsqueda. El hecho de que haya palabras que no aparezcan en el índice en una base de datos se debe a que son insignificantes (como los artículos y las preposiciones). Estas palabras son excluidas de las búsquedas para agilizar el proceso de indexar y analizar las páginas web. Algunos ejemplos de estas palabras son: “un”, “y”, “pero”, “cómo”, “o” y “qué”. Los buscadores, en Internet, no pueden impedir el uso de estas palabras; por lo tanto, las ignoran.

1.4.3 Stemming

Stemming es un método que permite reducir una palabra a su raíz o stem. Hay algunos algoritmos de stemming que ayudan en sistemas de recuperación de información. El stemming aumenta el recall, que es una medida sobre el número de documentos que se pueden encontrar con una consulta. Por ejemplo, una consulta sobre “bibliotecas” también encontrará documentos en los que solo aparezca “bibliotecario”, porque el stem de las dos palabras es el mismo (“biblioteca”).

Esta técnica se suele utilizar cuando queremos que un término pueda reducirse a su común denominador, y permitirá la recuperación de todos los documentos cuyas palabras tengan la misma raíz común (por ejemplo: catálogo, catálogos, catalogación, catalogador, catalogar, catalogando, catalogado).

1.5 RECUPERACIÓN DE LA INFORMACIÓN

La recuperación de información, o information retrieval, es una disciplina que se encarga de estudiar las técnicas para buscar información dentro de documentos que no se encuentran organizados o cuando, debido a la gran cantidad de documentos, resulta difícil buscar de forma manual.

Los sistemas para la recuperación de información están formados por diferentes mecanismos, que son los que permiten realizar las búsquedas, y un spider o crawler, que es el que se encarga de recorrer la web siguiendo los enlaces que va encontrando en las páginas o documentos. Este recorrido puede realizarse tanto en profundidad como a lo ancho y, generalmente, este tipo de programas suelen estar alojados en ordenadores con gran capacidad de memoria y CPU.

Los documentos encontrados en la web son analizados por el crawler, que les da un formato común. Después, estos documentos se almacenan en alguna estructura de datos, que puede ser un sistema relacional en forma de índices para su rápido acceso. En este proceso se realiza un análisis de cada una de las páginas o documentos encontrados y, por cada palabra encontrada, se guarda la referencia del documento donde se encuentra.

Cuando el usuario escribe el criterio a buscar, los resultados se muestran de forma ordenada según una relevancia que se calcula teniendo en cuenta el modelo de recuperación utilizado.

Este último componente también se comunica con el mecanismo de formulación de consulta, que es el que utiliza los términos introducidos por el usuario y los convierte en los términos que están almacenados en el índice. De esta forma, realiza una recuperación de todos los documentos que presentan estos términos, ordenándolos por la relevancia asociada a cada documento.

A partir de una colección de documentos, se seleccionan aquellos relacionados con una pregunta de un usuario a través de un conjunto de palabras claves. La recuperación de información tiene las siguientes características:

• La información es una pieza fundamental en todos los procesos de nuestra sociedad.

• El desarrollo de las tecnologías de la información (TI) ha permitido crear sistemas y servicios de información cada vez más ágiles.

• El desarrollo de las comunicaciones ha permitido el acceso a información desde cualquier sitio de forma remota.

• Hoy en día disponemos de gran cantidad de repositorios y documentación en Internet.

A continuación, se muestran los principales pasos para la recuperación de la información (figura 1.2):

1. Obtener representación de los documentos. Generalmente, los documentos se presentan utilizando un conjunto más o menos grande de términos índice. La elección de dichos términos es el proceso más complicado.

2. Identificar la necesidad informativa del usuario. Se trata de obtener la representación de esa necesidad y plasmarla formalmente en una consulta acorde con el sistema de recuperación.

3. Búsqueda de documentos que satisfagan la consulta. Consiste en comparar las representaciones de documentos y la representación de la necesidad informativa para seleccionar los documentos pertinentes.

4. Presentación de los resultados al usuario. Puede ser desde una breve identificación del documento hasta el texto completo.

5. Evaluación de los resultados. Para determinar si son acordes con la necesidad informativa.

Figura 1.2 Pasos para un proceso de recuperación de información.

Los sistemas de recuperación basados en términos índice se apoyan en la idea fundamental de que tanto el contenido de los documentos como la necesidad informativa del usuario pueden representarse con términos índice, lo cual permite agrupar diferentes documentos para representar un concepto. Los documentos se pueden clasificar, a grandes rasgos, en dos categorías:

• Documentos primarios: informes, artículos, páginas web, etc.

• Documentos secundarios: título, autor, resumen, etc.

La necesidad informativa se expresa formalmente mediante una consulta:

• Puede emplear diferentes términos y operadores booleanos.

• Puede realizarse en lenguaje natural.

La recuperación de información se utiliza en muchas de las aplicaciones que encontramos hoy en día, por ejemplo:

• Bibliotecas digitales

• Buscadores de Internet

• Herramientas de búsqueda personal (correos electrónicos, documentos personales, etc.

1.5.1 Extracción de información

La extracción de información es un área de investigación que comprende la intersección entre lingüística computacional, machine learning, data mining, bases de datos y recuperación de información. Se trata de un proceso que consiste en obtener información relevante a partir de un conjunto de documentos. Por tanto, el problema estriba en extraer la información y convertirla en información estructurada para poder buscar, manejar y explotar la información que se desee de forma eficiente.

El objetivo final es elaborar sistemas que permitan encontrar y relacionar información relevante mientras ignoran otras informaciones no relevantes. La relevancia se determina a partir de una serie de guías que permiten especificar con la mayor exactitud posible el tipo de información a extraer.

Desde la perspectiva del procesamiento de lenguaje natural, los sistemas de extracción de información deben trabajar a distintos niveles: desde el reconocimiento de palabras hasta el análisis de frases, y desde el entendimiento a nivel de frase hasta el texto completo. A grandes rasgos, entre las principales tareas relacionadas con la extracción de la información podemos destacar:

• Extracción de entidades y relaciones:

− Entidades: con nombre y genéricas.

− Relaciones: entidades relacionadas de una forma predefinida.

− Eventos: pueden estar compuestos de múltiples relaciones.

• Subtareas comunes en la extracción:

− Preproceso: segmentación de frases, análisis morfológico y sintáctico.

− Creación de reglas y/o patrones de extracción: de forma manual, automática o mixta.

− Aplicación de reglas o patrones de extracción: para extraer nueva información.

− Post-proceso: integración de la información, resolución y desambiguación de términos.

1.5.2 Sistema de búsqueda/respuesta

Un sistema basado en búsqueda/respuesta parte de una consulta expresada en lenguaje natural y debe devolver no un documento que sea relevante (es decir, un documento que contenga la respuesta) sino la propia respuesta (normalmente, un hecho). Proporciona el fragmento de texto en el que se encuentra la respuesta a una pregunta del usuario.

A diferencia de los sistemas de recuperación de la información convencionales que utilizan técnicas estadísticas, los sistemas de búsqueda/respuesta emplean técnicas de PLN (procesamiento de lenguaje natural). Uno de los sistemas de búsqueda/respuesta más conocidos es el correspondiente al START (natural language question answering system) (figura 1.3).

http://www.ai.mit.edu/projects/infolab/globe.html

Figura 1.3 Sistema START de búsqueda/respuesta.

1.6 MOTORES DE BÚSQUEDA E INDEXADORES

Los sistemas de recuperación de información con índice invertido son sistemas caracterizados por tener una estructura de datos capaz de manejar grandes volúmenes de información orientados a texto. Esta funcionalidad está presente en los motores de búsqueda que se van a analizar en profundidad:

• Apache Lucene (https://lucene.apache.org) es una potente librería de recuperación de información que se basa en la elaboración de un índice invertido como principal estructura especializada en emparejar documentos de texto con términos de consulta. Lucene, al igual que otros motores de búsqueda, se distingue por la escalabilidad, el rápido despliegue, el manejo de grandes volúmenes de datos y la optimización orientada a búsqueda de textos en documentos.

• Apache Solr (https://lucene.apache.org/solr) es una librería open source construida sobre la librería de Lucene, que incluye una interfaz web de administración, API en distintos lenguajes para la realización de consultas y una serie de mejoras funcionales sobre las características base que trae Lucene de serie.

• ElasticSearch (https://www.elastic.co/es/), construido sobre Apache Lucene, ha basado su modelo en una API REST y ha ganado popularidad en los últimos años. Se trata de una plataforma distribuida en tiempo real de búsqueda y análisis:

− ElasticSearch distribuye y organiza la información en clúster de nodos, por lo que lo podemos ejecutar en varios servidores si nuestra aplicación necesita escalar.

− ElasticSearch es un motor de búsqueda que funciona en tiempo real, ya que los datos están indexados. De esta forma, obtenemos respuestas a nuestras consultas de forma mucho más rápida si lo comparamos con otras soluciones.

En la actualidad, es común que las aplicaciones estén respaldadas por una base de datos sobre la que se implementan las búsquedas. Sin embargo, con este enfoque, la implementación de funcionalidades de búsqueda con cierta complejidad puede llegar a ser complicada debido a las limitaciones de las bases de datos. Por ejemplo, las búsquedas pueden no llegar a ser suficientemente eficientes si el volumen de información es muy grande o si la forma en que está estructurada la información no es la adecuada. En escenarios como estos, una plataforma especialmente dedicada a la optimización de las búsquedas puede resultar una alternativa más práctica y eficiente.

Estas plataformas utilizan un modelo de datos orientado a documentos que pueden pensarse como una base de datos de una sola tabla. Un documento es simplemente un conjunto de campos, como una tupla en una tabla de una base de datos, con la diferencia de que cada columna puede ser multivaluada.

Además, permiten la implementación de funcionalidades de búsqueda sobre documentos que facilitan al usuario la localización de recursos de una manera más rápida y organizada. Tomando como referencia la web DB-Engines, podemos ver que la solución más popular hoy en día es ElasticSearch. En el siguiente URL podemos ver los motores de búsqueda más populares:

https://db-engines.com/en/ranking/search+engine

Figura 1.4 Listado de motores de búsqueda.

De los motores mostrados en la figura 1.4, analizaremos en profundidad tanto ElasticSearch como Apache Solr (ambos basados en Lucene, que nos permite realizar búsquedas por una gran cantidad de datos de un texto específico). Gracias al motor Lucene sobre el que están implementados, estos motores nos ofrecen capacidades de búsquedas de texto, autocompletado y soporte de geolocalización. Podríamos definir a estos motores de búsqueda como bases de datos NoSQL orientadas a documentos JSON, que pueden ser consultados, creados, actualizados o borrados mediante una API REST.