Los motores de búsqueda pueden parecer mágicos. Escribe lo que estás buscando en un cuadro de texto y, ¡ping! - Aparecen unos milisegundos después. Por supuesto, todos sabemos que Google se basa en más que una varita mágica para producir resultados de búsqueda relevantes; Pero, ¿qué usa exactamente en su lugar??

Bueno, cualquier motor de búsqueda tiene tres fases distintas: navegar por la web para encontrar y leer páginas web, indexar las páginas web encontradas y responder a las consultas de los usuarios para producir un conjunto de resultados clasificados.

En este artículo no vamos a hablar en absoluto sobre las actividades de rastreo, pero puede imaginarlo como un programa especial que lee una página web, analiza el código fuente y luego sigue los enlaces de URL encontrados. Las páginas se almacenan y se analizan más a fondo..

La indexación es un algoritmo interesante. El propósito de indexar las páginas web encontradas a través de spidering es producir resultados de búsqueda rápidos y precisos. Si no es rápido, el usuario irá a otro lado; si no es exacto, entonces ídem.

Aquí es donde Google superó a sus competidores al inicio: fue más rápido (desde la carga de la página hasta la producción de los resultados) y fue más preciso (debido a su uso del algoritmo PageRank). Una vez que el motor de búsqueda ha indexado un gran número de páginas, puede comenzar a responder a las consultas de búsqueda..

El índice debe construirse de tal manera que el motor de búsqueda pueda producir una lista de páginas web que satisfagan la consulta y clasifiquen los resultados rápidamente para que se muestren primero los resultados más relevantes y relevantes. Por lo tanto, el índice es de suma importancia, ya que el algoritmo de clasificación es igualmente significativo.

Después de todo, antes de Google y PageRank, había otros motores de búsqueda como AltaVista que sabían cómo indexar. Fue el ranking de Google que cambió todo. El tipo estándar de estructura de datos para índices de texto se conoce como un archivo invertido. Supongamos que tenemos un conjunto de documentos de texto. La primera etapa consiste en analizar el contenido analizando el texto para identificar las palabras individuales (o tokens) en el texto..

Una vez que hemos identificado las palabras, escribir un analizador es bastante simple. Podemos usar algo como una máquina de estados (o autómata) o expresiones regulares (que ciertamente fueron diseñadas para este tipo de tareas de análisis de texto). ¿Pero qué estamos buscando en realidad??

La respuesta simple e intuitiva es "los bits entre el espacio en blanco". Pero esa simple respuesta revela una diferencia entre cómo los humanos escaneamos el texto y cómo lo hace la computadora. Por ejemplo, eche otro vistazo a la primera oración en este párrafo. Al implementar esta definición como un programa (y al usar corchetes para delimitar los tokens aquí), veríamos palabras como [simple,], ['bits] y [espacio.'].

Ya que es un poco demasiado básico, podríamos refinar la definición a "las palabras son los bits entre el espacio en blanco y la puntuación". Pero, nuevamente, caemos en una trampa: para la primera oración de este párrafo, esta definición ahora produciría las palabras [eso] y [s] para la palabra 'eso'.

Entonces, probablemente la mejor respuesta, al menos a los efectos de indexar texto en inglés, es escribir un analizador que, cuando ve un carácter de puntuación, verifique el carácter después del signo de puntuación..

Si es una letra, entonces es más probable que sea una abreviatura como "es" o "es", y debería incluirse en la palabra. Aún mejor, en estos días los documentos contendrán cosas como direcciones de correo electrónico y URL. Estos pueden verse como 'palabras' por derecho propio, y este algoritmo de análisis de palabras también funcionaría con ellos.

Por supuesto, para otros idiomas, las palabras de análisis pueden requerir otros algoritmos que dependen de temas como el conjunto de caracteres que se está utilizando (el texto ideográfico, por ejemplo, sería interesante) o las reglas gramaticales del idioma. Al analizar el texto, es probable que encontremos palabras duplicadas.

Para un índice simple, como el que estamos usando aquí, todo lo que necesitamos saber es si un documento en particular incluye una palabra determinada. No estamos particularmente interesados ​​en saber si el documento usa esa palabra una vez, dos veces o mil veces. Después de todo, cuando lleguemos a mostrar la lista de resultados de búsqueda, el usuario solo hará clic en un enlace dado y se dirigirá a esa URL en particular para examinar el documento..

En nuestro ejercicio de análisis, entonces, debemos ignorar los duplicados y apuntar a una lista de palabras utilizadas. El siguiente paso es eliminar las palabras que no tienen un significado de búsqueda, ya que cada documento las utilizará. Ejemplos de estas palabras de detención (como se llaman) son 'the', 'a', 'is', 'I', 'in' y así sucesivamente (¡y esas últimas tres palabras también!).

Cada aplicación de un algoritmo de indexación de texto usará su propio conjunto de palabras de parada, y estas listas se construirán y mantendrán en tiempo de ejecución desde el contenido que se está viendo. Después de hacer todo esto, tendremos una tabla de nombres de documentos con una lista de palabras para cada documento, como se muestra en la Figura 1.

Figura 1: Un índice adelantado enumera todas las palabras que se encuentran en un documento en particular

Aquí nombré los documentos como números, y en la práctica tendríamos otra tabla que hace referencia cruzada de estos números a la URL real del documento. El siguiente paso es invertir esta tabla; después de todo, para una búsqueda se nos dará una palabra, y tenemos que identificar los documentos que contienen esta palabra.

La palabra debe ser la clave, y en el momento en que la tabla está codificada por el número de documento. Con lo que terminamos es una tabla como se muestra en la Figura 2. La tabla está codificada por palabra, y los datos de cada registro en la tabla son una lista de números de documentos. Esta estructura se conoce como un archivo invertido. Partiendo de una tabla de palabras por documento, terminamos con una tabla de documentos por palabra.

Figura 2: Este índice invertido es una lista que muestra qué documentos contienen una palabra determinada