La indexación de motores de búsqueda es la recopilación, el análisis y el almacenamiento de datos para facilitar la recuperación rápida y precisa de la información . El diseño de índices incorpora conceptos interdisciplinarios de la lingüística , la psicología cognitiva , las matemáticas, la informática y la ciencia de la computación . Un nombre alternativo para el proceso, en el contexto de los motores de búsqueda diseñados para encontrar páginas web en Internet, es indexación web .
Los motores de búsqueda populares se centran en la indexación de texto completo de documentos en línea en lenguaje natural . [1] También se pueden buscar tipos de medios como imágenes, videos, [2] audio, [3] y gráficos [4] .
Los motores de metabúsqueda reutilizan los índices de otros servicios y no almacenan un índice local, mientras que los motores de búsqueda basados en caché almacenan permanentemente el índice junto con el corpus . A diferencia de los índices de texto completo, los servicios de texto parcial restringen la profundidad indexada para reducir el tamaño del índice. Los servicios más grandes suelen realizar la indexación en un intervalo de tiempo predeterminado debido al tiempo requerido y los costos de procesamiento, mientras que los motores de búsqueda basados en agentes indexan en tiempo real .
El objetivo de almacenar un índice es optimizar la velocidad y el rendimiento en la búsqueda de documentos relevantes para una consulta de búsqueda. Sin un índice, el motor de búsqueda escanearía cada documento del corpus , lo que requeriría un tiempo y una potencia de cálculo considerables. Por ejemplo, mientras que un índice de 10.000 documentos se puede consultar en milisegundos, un escaneo secuencial de cada palabra en 10.000 documentos grandes podría llevar horas. El almacenamiento informático adicional necesario para almacenar el índice, así como el aumento considerable del tiempo necesario para que se realice una actualización, se compensan con el tiempo ahorrado durante la recuperación de información.
Los factores principales en el diseño de la arquitectura de un motor de búsqueda incluyen:
Las arquitecturas de los motores de búsqueda varían en la forma en que se realiza la indexación y en los métodos de almacenamiento del índice para satisfacer los diversos factores de diseño.
Un desafío importante en el diseño de motores de búsqueda es la gestión de procesos de computación en serie. Hay muchas oportunidades para condiciones de carrera y fallas coherentes. Por ejemplo, se agrega un nuevo documento al corpus y el índice debe actualizarse, pero el índice simultáneamente necesita continuar respondiendo a las consultas de búsqueda. Esta es una colisión entre dos tareas en competencia. Considere que los autores son productores de información y un rastreador web es el consumidor de esta información, capturando el texto y almacenándolo en un caché (o corpus ). El índice directo es el consumidor de la información producida por el corpus y el índice invertido es el consumidor de la información producida por el índice directo. Esto se conoce comúnmente como un modelo productor-consumidor . El indexador es el productor de información buscable y los usuarios son los consumidores que necesitan buscar. El desafío se magnifica cuando se trabaja con almacenamiento distribuido y procesamiento distribuido. En un esfuerzo por escalar con mayores cantidades de información indexada, la arquitectura del motor de búsqueda puede involucrar computación distribuida , donde el motor de búsqueda consta de varias máquinas que operan al unísono. Esto aumenta las posibilidades de incoherencia y hace más difícil mantener una arquitectura totalmente sincronizada, distribuida y paralela. [14]
Muchos motores de búsqueda incorporan un índice invertido al evaluar una consulta de búsqueda para localizar rápidamente los documentos que contienen las palabras de la consulta y luego clasificarlos por relevancia. Debido a que el índice invertido almacena una lista de los documentos que contienen cada palabra, el motor de búsqueda puede utilizar el acceso directo para encontrar los documentos asociados con cada palabra de la consulta y así recuperar rápidamente los documentos coincidentes. La siguiente es una ilustración simplificada de un índice invertido:
Este índice sólo puede determinar si una palabra existe dentro de un documento en particular, ya que no almacena información sobre la frecuencia y la posición de la palabra; por lo tanto, se considera un índice booleano . Un índice de este tipo determina qué documentos coinciden con una consulta, pero no clasifica los documentos coincidentes. En algunos diseños, el índice incluye información adicional, como la frecuencia de cada palabra en cada documento o las posiciones de una palabra en cada documento. [15] La información de posición permite que el algoritmo de búsqueda identifique la proximidad de las palabras para respaldar la búsqueda de frases; la frecuencia se puede utilizar para ayudar a clasificar la relevancia de los documentos para la consulta. Estos temas son el foco central de investigación de la recuperación de información .
El índice invertido es una matriz dispersa , ya que no todas las palabras están presentes en cada documento. Para reducir los requisitos de memoria de almacenamiento de la computadora , se almacena de forma diferente a una matriz bidimensional . El índice es similar al término matrices de documentos que se emplean en el análisis semántico latente . El índice invertido puede considerarse una forma de tabla hash. En algunos casos, el índice es una forma de árbol binario , que requiere almacenamiento adicional pero puede reducir el tiempo de búsqueda. En índices más grandes, la arquitectura suele ser una tabla hash distribuida . [16]
Para la búsqueda de frases, se utiliza una forma especializada de índice invertido denominado índice posicional. Un índice posicional no solo almacena el ID del documento que contiene el token, sino también la posición exacta del token dentro del documento en la lista de publicaciones . Las ocurrencias de la frase especificada en la consulta se recuperan navegando por estas listas de publicaciones e identificando los índices en los que aparecen los términos deseados en el orden esperado (el mismo que el orden en la frase). Por lo tanto, si buscamos la ocurrencia de la frase "First Witch", haríamos lo siguiente:
Las listas de publicaciones se pueden navegar mediante una búsqueda binaria para minimizar la complejidad temporal de este procedimiento. [17]
El índice invertido se llena mediante una fusión o reconstrucción. Una reconstrucción es similar a una fusión pero primero elimina el contenido del índice invertido. La arquitectura puede estar diseñada para soportar la indexación incremental, [18] donde una fusión identifica el documento o los documentos que se agregarán o actualizarán y luego analiza cada documento en palabras. Para mayor precisión técnica, una fusión combina los documentos recién indexados, que generalmente residen en la memoria virtual, con la caché del índice que reside en uno o más discos duros de computadora.
Después del análisis, el indexador añade el documento referenciado a la lista de documentos correspondiente a las palabras adecuadas. En un motor de búsqueda más grande, el proceso de encontrar cada palabra en el índice invertido (para informar que se encuentra dentro de un documento) puede consumir demasiado tiempo, por lo que este proceso se suele dividir en dos partes: el desarrollo de un índice directo y un proceso que ordena el contenido del índice directo en el índice invertido. El índice invertido se llama así porque es una inversión del índice directo.
El índice de avance almacena una lista de palabras para cada documento. A continuación se muestra una forma simplificada del índice de avance:
La razón detrás del desarrollo de un índice directo es que a medida que se analizan los documentos, es mejor almacenar de manera intermedia las palabras por documento. La delineación permite el procesamiento asincrónico del sistema, lo que evita parcialmente el cuello de botella de actualización del índice invertido. [19] El índice directo se ordena para transformarlo en un índice invertido. El índice directo es esencialmente una lista de pares que consisten en un documento y una palabra, cotejados por el documento. Convertir el índice directo en un índice invertido es solo una cuestión de ordenar los pares por las palabras. En este sentido, el índice invertido es un índice directo ordenado por palabras.
La generación o el mantenimiento de un índice de motor de búsqueda a gran escala representa un desafío significativo en términos de almacenamiento y procesamiento. Muchos motores de búsqueda utilizan una forma de compresión para reducir el tamaño de los índices en el disco . [20] Considere el siguiente escenario para un motor de búsqueda de Internet de texto completo.
En este escenario, un índice sin comprimir (suponiendo que se trata de un índice simple y no combinado ) para 2 mil millones de páginas web necesitaría almacenar 500 mil millones de entradas de palabras. Con 1 byte por carácter, o 5 bytes por palabra, esto requeriría 2500 gigabytes de espacio de almacenamiento solamente. [ cita requerida ] Este requisito de espacio puede ser incluso mayor para una arquitectura de almacenamiento distribuido tolerante a fallas. Dependiendo de la técnica de compresión elegida, el índice se puede reducir a una fracción de este tamaño. La compensación es el tiempo y la potencia de procesamiento necesarios para realizar la compresión y la descompresión. [ cita requerida ]
Cabe destacar que los diseños de motores de búsqueda a gran escala incorporan el costo del almacenamiento, así como los costos de la electricidad para alimentar el almacenamiento. Por lo tanto, la compresión es una medida de costo. [ cita requerida ]
El análisis de documentos descompone los componentes (palabras) de un documento u otro tipo de medio para insertarlos en los índices directo e invertido. Las palabras encontradas se denominan tokens y, por lo tanto, en el contexto de la indexación de motores de búsqueda y el procesamiento del lenguaje natural , el análisis se conoce más comúnmente como tokenización . A veces también se lo denomina desambiguación de límites de palabras, etiquetado , segmentación de texto , análisis de contenido , análisis de texto, minería de texto , generación de concordancia , segmentación de voz , análisis léxico o análisis léxico . Los términos "indexación", "análisis" y "tokenización" se usan indistintamente en la jerga corporativa.
El procesamiento del lenguaje natural es objeto de investigación y mejora tecnológica continuas. La tokenización presenta muchos desafíos a la hora de extraer la información necesaria de los documentos para su indexación con el fin de respaldar una búsqueda de calidad. La tokenización para la indexación implica múltiples tecnologías, cuya implementación suele mantenerse como secreto corporativo. [ cita requerida ]
A diferencia de los humanos alfabetizados , las computadoras no comprenden la estructura de un documento en lenguaje natural y no pueden reconocer automáticamente palabras y oraciones. Para una computadora, un documento es solo una secuencia de bytes. Las computadoras no "saben" que un carácter de espacio separa las palabras en un documento. En cambio, los humanos deben programar la computadora para identificar lo que constituye una palabra individual o distinta, a la que se denomina token. Este tipo de programa se denomina comúnmente tokenizador , analizador sintáctico o analizador léxico . Muchos motores de búsqueda, así como otro software de procesamiento de lenguaje natural, incorporan programas especializados para el análisis sintáctico, como YACC o Lex .
Durante la tokenización, el analizador identifica secuencias de caracteres que representan palabras y otros elementos, como la puntuación, que se representan mediante códigos numéricos, algunos de los cuales son caracteres de control no imprimibles. El analizador también puede identificar entidades como direcciones de correo electrónico , números de teléfono y URL . Al identificar cada token, se pueden almacenar varias características, como el caso del token (mayúsculas, minúsculas, mixtas, propias), el idioma o la codificación, la categoría léxica (parte del discurso, como "sustantivo" o "verbo"), la posición, el número de oración, la posición de la oración, la longitud y el número de línea.
Si el motor de búsqueda admite varios idiomas, un paso inicial común durante la tokenización es identificar el idioma de cada documento; muchos de los pasos posteriores dependen del idioma (como la lematización y el etiquetado de partes del discurso ). El reconocimiento de idiomas es el proceso mediante el cual un programa informático intenta identificar o categorizar automáticamente el idioma de un documento. Otros nombres para el reconocimiento de idiomas incluyen clasificación de idiomas, análisis de idiomas, identificación de idiomas y etiquetado de idiomas. El reconocimiento automático de idiomas es el tema de investigación en curso en el procesamiento del lenguaje natural . Encontrar a qué idioma pertenecen las palabras puede implicar el uso de un gráfico de reconocimiento de idiomas .
Si el motor de búsqueda admite varios formatos de documentos , estos deben estar preparados para la tokenización. El desafío es que muchos formatos de documentos contienen información de formato además del contenido textual. Por ejemplo, los documentos HTML contienen etiquetas HTML, que especifican información de formato, como inicios de nuevas líneas, énfasis en negrita y tamaño o estilo de fuente . Si el motor de búsqueda ignorara la diferencia entre contenido y "marcado", se incluiría información extraña en el índice, lo que generaría resultados de búsqueda deficientes. El análisis de formato es la identificación y el manejo del contenido de formato incrustado en los documentos que controla la forma en que el documento se presenta en una pantalla de computadora o es interpretado por un programa de software. El análisis de formato también se conoce como análisis de estructura, análisis de formato, eliminación de etiquetas, eliminación de formato, normalización de texto, limpieza de texto y preparación de texto. El desafío del análisis de formato se complica aún más por las complejidades de varios formatos de archivo. Algunos formatos de archivo son propietarios y se divulga muy poca información, mientras que otros están bien documentados. Los formatos de archivo comunes y bien documentados que admiten muchos motores de búsqueda incluyen:
Las opciones para trabajar con varios formatos incluyen el uso de una herramienta de análisis comercial disponible públicamente que ofrece la organización que desarrolló, mantiene o posee el formato, y la escritura de un analizador personalizado .
Algunos motores de búsqueda admiten la inspección de archivos almacenados en un formato comprimido o cifrado. Cuando se trabaja con un formato comprimido, el indexador primero descomprime el documento; este paso puede generar uno o más archivos, cada uno de los cuales debe indexarse por separado. Los formatos de archivos comprimidos que se admiten comúnmente incluyen:
El análisis de formato puede implicar métodos de mejora de la calidad para evitar la inclusión de "información incorrecta" en el índice. El contenido puede manipular la información de formato para incluir contenido adicional. Ejemplos de abuso del formato de documentos para indexación de spam :
Algunos motores de búsqueda incorporan el reconocimiento de secciones, la identificación de las partes principales de un documento, antes de la tokenización. No todos los documentos de un corpus se leen como un libro bien escrito, dividido en capítulos y páginas organizados. Muchos documentos en la web , como boletines informativos e informes corporativos, contienen contenido erróneo y secciones laterales que no contienen material principal (aquello sobre lo que trata el documento). Por ejemplo, los artículos en el sitio web de Wikipedia muestran un menú lateral con enlaces a otras páginas web. Algunos formatos de archivo, como HTML o PDF, permiten que el contenido se muestre en columnas. Aunque el contenido se muestra o se representa en diferentes áreas de la vista, el contenido de marcado sin procesar puede almacenar esta información de forma secuencial. Las palabras que aparecen secuencialmente en el contenido fuente sin procesar se indexan secuencialmente, aunque estas oraciones y párrafos se representen en diferentes partes de la pantalla de la computadora. Si los motores de búsqueda indexan este contenido como si fuera contenido normal, la calidad del índice y la calidad de la búsqueda pueden degradarse debido al contenido mixto y la proximidad inadecuada de las palabras. Se observan dos problemas principales:
El análisis de secciones puede requerir que el motor de búsqueda implemente la lógica de representación de cada documento, esencialmente una representación abstracta del documento real, y luego indexe la representación en su lugar. Por ejemplo, algunos contenidos de Internet se representan mediante JavaScript. Si el motor de búsqueda no representa la página y evalúa el JavaScript dentro de la página, no "vería" este contenido de la misma manera e indexaría el documento incorrectamente. Dado que algunos motores de búsqueda no se preocupan por los problemas de representación, muchos diseñadores de páginas web evitan mostrar contenido mediante JavaScript o utilizan la etiqueta Noscript para garantizar que la página web se indexe correctamente. Al mismo tiempo, este hecho también se puede aprovechar para hacer que el indexador del motor de búsqueda "vea" un contenido diferente al del visor.
La indexación a menudo tiene que reconocer las etiquetas HTML para organizar la prioridad. La indexación de baja prioridad a alto margen a etiquetas como strong y link para optimizar el orden de prioridad si esas etiquetas están al principio del texto podría no resultar relevante. Algunos indexadores como Google y Bing se aseguran de que el motor de búsqueda no tome los textos largos como fuente relevante debido a la fuerte compatibilidad del sistema de tipos. [23]
La indexación de metaetiquetas desempeña un papel importante en la organización y categorización de contenido web. Los documentos específicos a menudo contienen información meta incrustada, como autor, palabras clave, descripción e idioma. En el caso de las páginas HTML, la metaetiqueta contiene palabras clave que también se incluyen en el índice. La tecnología anterior de los motores de búsqueda de Internet solo indexaba las palabras clave en las metaetiquetas para el índice directo; no se analizaba el documento completo. En ese momento, la indexación de texto completo no estaba tan bien establecida, ni el hardware informático era capaz de soportar dicha tecnología. El diseño del lenguaje de marcado HTML inicialmente incluía soporte para metaetiquetas con el mismo propósito de ser indexado de manera correcta y fácil, sin necesidad de tokenización. [24]
A medida que Internet fue creciendo en los años 90, muchas empresas tradicionales se pasaron a la red y crearon sitios web corporativos. Las palabras clave utilizadas para describir las páginas web (muchas de las cuales eran páginas web orientadas a empresas similares a folletos de productos) cambiaron de palabras clave descriptivas a palabras clave orientadas al marketing diseñadas para impulsar las ventas colocando la página web en los primeros puestos de los resultados de búsqueda para consultas de búsqueda específicas. El hecho de que estas palabras clave se especificaran de forma subjetiva estaba dando lugar al spamdexing , que llevó a muchos motores de búsqueda a adoptar tecnologías de indexación de texto completo en los años 90. Los diseñadores y las empresas de motores de búsqueda solo podían colocar una determinada cantidad de "palabras clave de marketing" en el contenido de una página web antes de vaciarla de toda la información interesante y útil. Dado ese conflicto de intereses con el objetivo empresarial de diseñar sitios web orientados al usuario que fueran "fijos", la ecuación del valor de vida del cliente se modificó para incorporar más contenido útil al sitio web con la esperanza de retener al visitante. En este sentido, la indexación de texto completo era más objetiva y aumentaba la calidad de los resultados de los motores de búsqueda, ya que era un paso más allá del control subjetivo de la ubicación de los resultados de los motores de búsqueda, lo que a su vez impulsó la investigación de las tecnologías de indexación de texto completo.
En la búsqueda de escritorio , muchas soluciones incorporan metaetiquetas para ofrecer a los autores una forma de personalizar aún más la forma en que el motor de búsqueda indexará el contenido de varios archivos que no es evidente en el contenido del archivo. La búsqueda de escritorio está más bajo el control del usuario, mientras que los motores de búsqueda de Internet deben centrarse más en el índice de texto completo.