La indexación de motores de búsqueda es la recopilación, análisis y almacenamiento de datos para facilitar la recuperación de información rápida y precisa . El diseño de índices incorpora conceptos interdisciplinarios de lingüística , psicología cognitiva , matemáticas, informática e informática . 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, vídeo, [2] audio, [3] y gráficos [4] .
Los metabuscadores 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 normalmente realizan 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 propósito 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 todos los documentos del corpus , lo que requeriría un tiempo y una potencia informática considerables. Por ejemplo, mientras que se puede consultar un índice de 10.000 documentos 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 la 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 cumplir con 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 informáticos 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 debe continuar respondiendo a las consultas de búsqueda. Se trata de 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, toma el texto y lo almacena 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 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 que sea más difícil mantener una arquitectura paralela, distribuida y totalmente sincronizada. [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 una 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 en la consulta para 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 posición de la palabra; por tanto, se considera un índice booleano . Dicho índice 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 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 manera diferente a una matriz bidimensional . El índice es similar al término matrices de documentos empleado por 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 . [dieciséis]
Para la búsqueda de frases, se utiliza una forma especializada de índice invertido llamado í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 apariciones de la frase especificada en la consulta se recuperan navegando por esta lista 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). Entonces, si buscamos la aparición de la frase "Primera bruja", haríamos:
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 completa mediante una combinación o reconstrucción. Una reconstrucción es similar a una fusión, pero primero elimina el contenido del índice invertido. La arquitectura puede diseñarse para admitir indexación incremental, [18] donde una combinación identifica el documento o documentos que se agregarán o actualizarán y luego analiza cada documento en palabras. Para mayor precisión técnica, una combinación combina documentos recién indexados, que generalmente residen en la memoria virtual, con la caché de índice que reside en uno o más discos duros de la computadora.
Después del análisis, el indexador agrega el documento al que se hace referencia a la lista de documentos para las palabras apropiadas. En un motor de búsqueda más grande, el proceso de encontrar cada palabra en el índice invertido (para informar que ocurrió dentro de un documento) puede consumir demasiado tiempo, por lo que este proceso comúnmente se divide en dos partes: el desarrollo de un índice directo y un proceso que clasifica 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 directo almacena una lista de palabras para cada documento. La siguiente es una forma simplificada del índice directo:
La razón detrás del desarrollo de un índice directo es que a medida que se analizan los documentos, es mejor almacenar intermediamente las palabras por documento. La delimitación permite el procesamiento asincrónico del sistema, lo que evita parcialmente el cuello de botella de la 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 consta de un documento y una palabra, recopilados por documento. Convertir el índice directo a un índice invertido es solo una cuestión de ordenar los pares por palabras. En este sentido, el índice invertido es un índice directo ordenado por palabras.
Generar o mantener un índice de motor de búsqueda a gran escala representa un desafío importante 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.
Dado este escenario, un índice sin comprimir (suponiendo un índice simple y no combinado ) para 2 mil millones de páginas web necesitaría almacenar 500 mil millones de entradas de palabras. A 1 byte por carácter, o 5 bytes por palabra, esto requeriría sólo 2500 gigabytes de espacio de almacenamiento. [ cita necesaria ] 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 desventaja es el tiempo y la potencia de procesamiento necesarios para realizar la compresión y descompresión. [ cita necesaria ]
En particular, 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 tanto, la compresión es una medida de costo. [ cita necesaria ]
El análisis de documentos separa los componentes (palabras) de un documento u otra forma 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 denomina más comúnmente tokenización . A veces también se le llama 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 del habla , lexing o análisis léxico . Los términos "indexación", "análisis" y "tokenización" se utilizan indistintamente en la jerga corporativa.
El procesamiento del lenguaje natural es objeto de continua investigación y mejora tecnológica. La tokenización presenta muchos desafíos a la hora de extraer la información necesaria de los documentos para su indexación y respaldar una búsqueda de calidad. La tokenización para la indexación implica múltiples tecnologías, cuya implementación comúnmente se mantiene como secreto corporativo. [ cita necesaria ]
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 sólo 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 qué constituye una palabra individual o distinta denominada token. Un programa de este tipo se denomina comúnmente tokenizador , analizador o lexer . Muchos motores de búsqueda, así como otros programas de procesamiento de lenguaje natural, incorporan programas especializados para el análisis, 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 están representados por códigos numéricos, algunos de los cuales son caracteres de control que no se imprimen. 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 (superior, inferior, mixto, propio), idioma o codificación, categoría léxica (parte del discurso, como 'sustantivo' o 'verbo'), posición, oración. número, posición de la oración, longitud y 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 siguientes dependen del idioma (como la derivación y el etiquetado de partes del discurso ). El reconocimiento de idioma es el proceso mediante el cual un programa de computadora 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 automatizado del lenguaje es objeto de investigación en curso en el procesamiento del lenguaje natural . Encontrar a qué idioma pertenecen las palabras puede implicar el uso de una tabla de reconocimiento de idiomas .
Si el motor de búsqueda admite múltiples formatos de documentos , los documentos 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 superflua en el índice, lo que conduciría a resultados de búsqueda deficientes. El análisis de formato es la identificación y el manejo del contenido de formato integrado en los documentos que controla la forma en que el documento se representa en una pantalla de computadora o se interpreta mediante 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 los distintos formatos de archivo. Ciertos formatos de archivos 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 manejar varios formatos incluyen el uso de una herramienta de análisis comercial disponible públicamente ofrecida por la organización que desarrolló, mantiene o posee el formato, y escribir un analizador personalizado .
Algunos motores de búsqueda admiten la inspección de archivos almacenados en un formato de archivo comprimido o cifrado. Cuando se trabaja con un formato comprimido, el indexador primero descomprime el documento; Este paso puede dar como resultado uno o más archivos, cada uno de los cuales debe indexarse por separado. Los formatos de archivos comprimidos comúnmente admitidos incluyen:
El análisis de formato puede implicar métodos de mejora de la calidad para evitar incluir "mala información" en el índice. El contenido puede manipular la información de formato para incluir contenido adicional. Ejemplos de abuso de formato de documentos para spamdexing :
Algunos motores de búsqueda incorporan reconocimiento de secciones, la identificación de 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 organizadas. Muchos documentos en la web , como boletines e informes corporativos, contienen contenido erróneo y secciones laterales que no contienen material primario (de lo que trata el documento). Por ejemplo, este artículo muestra 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 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 muestren 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 verse degradadas debido al contenido mezclado y a la proximidad inadecuada de 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. Por ejemplo, parte del contenido de Internet se procesa mediante JavaScript. Si el motor de búsqueda no representa la página y no evalúa el JavaScript dentro de la página, no "verá" este contenido de la misma manera e indexará el documento incorrectamente. Dado que algunos motores de búsqueda no se preocupan por los problemas de renderizado, muchos diseñadores de páginas web evitan mostrar contenido a través de JavaScript o utilizan la etiqueta Noscript para garantizar que la página web esté indexada correctamente. Al mismo tiempo, este hecho también puede explotarse para hacer que el indexador del motor de búsqueda "vea" contenido diferente al del espectador.
La indexación a menudo tiene que reconocer las etiquetas HTML para organizar la prioridad. Indexar prioridad baja a margen alto para etiquetas como fuerte y enlace para optimizar el orden de prioridad si esas etiquetas están al principio del texto no podría resultar relevante. Algunos indexadores como Google y Bing garantizan que el motor de búsqueda no tome los textos grandes como fuente relevante debido a la fuerte compatibilidad del sistema tipográfico. [23]
La indexación de metaetiquetas juega un papel importante en la organización y categorización del contenido web. Los documentos específicos suelen contener metainformación incrustada, como autor, palabras clave, descripción e idioma. Para 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 sólo indexaba las palabras clave en las metaetiquetas para el índice directo; el documento completo no sería analizado. En aquel momento, la indexación de texto completo no estaba tan bien establecida, ni el hardware de las computadoras era capaz de soportar dicha tecnología. El diseño del lenguaje de marcado HTML inicialmente incluía soporte para metaetiquetas con el único propósito de indexarlos de manera adecuada y sencilla, sin requerir tokenización. [24]
A medida que Internet creció durante la década de 1990, muchas corporaciones físicas se "conectaron" y establecieron sitios web corporativos. Las palabras clave utilizadas para describir 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 al colocar la página web en un lugar destacado de los resultados de búsqueda para consultas de búsqueda específicas. El hecho de que estas palabras clave se especificaran subjetivamente estaba dando lugar a la indexación de spam , lo que llevó a muchos motores de búsqueda a adoptar tecnologías de indexación de texto completo en la década de 1990. Los diseñadores de motores de búsqueda y las empresas sólo podían colocar un número determinado 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", se cambió la ecuación del valor de vida del cliente para incorporar contenido más útil al sitio web con la esperanza de retener al visitante. En este sentido, la indexación de texto completo fue más objetiva y aumentó la calidad de los resultados de los motores de búsqueda, ya que estaba un paso más lejos 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 tecnologías de indexación de texto completo.
En la búsqueda de escritorio , muchas soluciones incorporan metaetiquetas para proporcionar a los autores una forma de personalizar aún más cómo el motor de búsqueda indexará el contenido de varios archivos que no es evidente en el contenido del archivo. La búsqueda en el 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.