Indexación de motores de búsqueda

Los factores principales a la hora de diseñar la arquitectura de un motor de búsqueda incluyen:

Factores de fusión

Cómo se introducen los datos en el índice, o cómo se añaden palabras o características temáticas al índice durante el recorrido del corpus de texto, y si varios indexadores pueden trabajar de forma asíncrona. El indexador debe comprobar primero si está actualizando contenido antiguo o añadiendo contenido nuevo. El recorrido suele estar relacionado con la política de recopilación de datos . La fusión de índices de motores de búsqueda es similar en concepto al comando SQL Merge y otros algoritmos de fusión. ^{[ 4 ]}

Técnicas de almacenamiento

Cómo almacenar los datos del índice , es decir, si la información debe comprimirse o filtrarse.

Tamaño del índice

¿Cuánto espacio de almacenamiento informático se requiere para admitir el índice?

Velocidad de búsqueda

La rapidez con la que se puede encontrar una palabra en el índice invertido . La velocidad de búsqueda de una entrada en una estructura de datos, en comparación con la rapidez con la que se puede actualizar o eliminar, es un aspecto fundamental de la informática.

Mantenimiento

Cómo se mantiene el índice a lo largo del tiempo. ^{[ 5 ]}

Tolerancia a fallos

Qué importante es que el servicio sea confiable. Los problemas incluyen lidiar con la corrupción de índices, determinar si los datos malos se pueden tratar de forma aislada, lidiar con hardware defectuoso, particionamiento y esquemas como particionamiento basado en hash o compuesto, ^{[ 6 ]} así como replicación .

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 de índices para adaptarse a los diversos factores de diseño.

árbol de sufijos

Figurativamente estructurado como un árbol, admite búsqueda en tiempo lineal. Construido almacenando los sufijos de las palabras. El árbol de sufijos es un tipo de trie . Los tries admiten hash extensible , que es importante para la indexación de motores de búsqueda. ^{[ 7 ]} Se utiliza para buscar patrones en secuencias de ADN y agrupamiento. Una desventaja importante es que almacenar una palabra en el árbol puede requerir espacio más allá del requerido para almacenar la palabra en sí. ^{[ 8 ]} Una representación alternativa es una matriz de sufijos , que se considera que requiere menos memoria virtual y admite compresión de datos como el algoritmo BWT .

Índice invertido

Almacena una lista de ocurrencias de cada criterio de búsqueda atómica, ^{[ 9 ]} normalmente en forma de tabla hash o árbol binario . ^{[ 10 ] [ 11 ]}

Índice de citas

Almacena citas o hipervínculos entre documentos para respaldar el análisis de citas, un tema de la bibliometría .

índice de n -gramas

Almacena secuencias de datos de longitud determinada para admitir otros tipos de recuperación o minería de texto . ^{[ 12 ]}

Matriz documento-término

Utilizada en el análisis semántico latente, almacena las ocurrencias de palabras en los documentos en una matriz dispersa bidimensional .

Un desafío importante en el diseño de motores de búsqueda es la gestión de procesos de computación en serie. Existen numerosas oportunidades para que se produzcan condiciones de carrera y fallos coherentes. Por ejemplo, se añade un nuevo documento al corpus y el índice debe actualizarse, pero simultáneamente el índice debe seguir respondiendo a las consultas de búsqueda. Esto supone una colisión entre dos tareas contrapuestas. Consideremos que los autores son productores de información y un rastreador web es el consumidor de esta información, que extrae el texto y lo almacena en una 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 que se puede buscar y los usuarios son los consumidores que necesitan realizar la búsqueda. El desafío se magnifica al trabajar con almacenamiento y procesamiento distribuidos. Para escalar con mayores cantidades de información indexada, la arquitectura del motor de búsqueda puede implicar 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 dificulta el mantenimiento de una arquitectura paralela, distribuida y totalmente sincronizada. ^{[ 13 ]}

Muchos motores de búsqueda incorporan un índice invertido al evaluar una consulta para localizar rápidamente los documentos que contienen las palabras de la consulta y, posteriormente, clasificarlos por relevancia. Dado que el índice invertido almacena una lista de los documentos que contienen cada palabra, el motor de búsqueda puede acceder directamente a los documentos asociados a cada palabra de la consulta para recuperar rápidamente los documentos coincidentes. A continuación, se muestra una ilustración simplificada de un índice invertido:

Este índice solo 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 . 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. ^{[ 14 ]} La información de posición permite que el algoritmo de búsqueda identifique la proximidad de las palabras para apoyar la búsqueda de frases; la frecuencia puede usarse para ayudar a clasificar la relevancia de los documentos para la consulta. Estos temas son el foco central de la investigación en 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 del ordenador , se almacena de forma diferente a una matriz bidimensional . El índice es similar a las matrices término-documento empleadas 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 , lo 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 . ^{[ 15 ]}

El índice invertido se completa 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 diseñarse para admitir la indexación incremental, ^{[ 17 ]} 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 la computadora.

Tras el análisis, el indexador añade el documento referenciado a la lista de documentos para las palabras clave correspondientes. En un motor de búsqueda grande, el proceso de encontrar cada palabra en el índice invertido (para indicar que aparece en un documento) puede resultar demasiado lento, por lo que este proceso suele dividirse en dos partes: la creación de un índice directo y la organización del contenido de este índice en el índice invertido. El índice invertido recibe este nombre porque es la inversión del índice directo.

El índice directo almacena una lista de palabras para cada documento. A continuación se muestra una forma simplificada del índice directo:

La razón de ser del desarrollo de un índice directo radica en que, a medida que se analizan los documentos, es mejor almacenar de forma intermedia las palabras de cada documento. Esta delimitación permite el procesamiento asíncrono del sistema, lo que evita parcialmente el cuello de botella de la actualización del índice invertido . ^{[ 18 ]} 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, ordenados por documento. Convertir el índice directo en un índice invertido es simplemente 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 significativo 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 . ^{[ 19 ]} Considere el siguiente escenario para un motor de búsqueda de Internet de texto completo.

• Se necesitan 8 bits (o 1 byte ) para almacenar un solo carácter. Algunas codificaciones usan 2 bytes por carácter ^{[ 20 ] [ 21 ].}
• El número promedio de caracteres en cualquier palabra dada en una página se puede estimar en 5 ( Wikipedia:comparaciones de tamaño ).

En este escenario, un índice sin comprimir (suponiendo un índice simple y no fusionado ) para 2 mil millones de páginas web necesitaría almacenar 500 mil millones de entradas de palabras. A razón de 1 byte por carácter, o 5 bytes por palabra, esto requeriría 2500 gigabytes de espacio de almacenamiento. Este requisito de espacio podría ser incluso mayor para una arquitectura de almacenamiento distribuido tolerante a fallos. Dependiendo de la técnica de compresión elegida, el índice puede reducirse a una fracción de este tamaño. La contrapartida reside en el tiempo y la potencia de procesamiento necesarios para realizar la compresión y la descompresión.

Cabe destacar que los diseños de motores de búsqueda a gran escala incorporan tanto el costo del almacenamiento como el costo de la electricidad necesaria para alimentarlo. Por lo tanto, la compresión es una medida de costo.

ambigüedad en los límites de las palabras

Los hablantes nativos de inglés podrían considerar inicialmente la tokenización una tarea sencilla, pero no ocurre lo mismo al diseñar un indexador multilingüe . En formato digital, los textos de otros idiomas, como el chino o el japonés, representan un desafío mayor, ya que las palabras no están claramente delimitadas por espacios en blanco . El objetivo durante la tokenización es identificar las palabras que los usuarios buscarán. Se emplea una lógica específica de cada idioma para identificar correctamente los límites de las palabras, lo que suele ser la razón para diseñar un analizador sintáctico para cada idioma compatible (o para grupos de idiomas con marcadores de límite y sintaxis similares).

Ambigüedad lingüística

Para facilitar la correcta clasificación de los documentos coincidentes, muchos motores de búsqueda recopilan información adicional sobre cada palabra, como su idioma o categoría léxica ( categoría gramatical ). Estas técnicas dependen del idioma, ya que la sintaxis varía entre ellos. Los documentos no siempre identifican claramente su idioma ni lo representan con precisión. Al tokenizar el documento, algunos motores de búsqueda intentan identificar automáticamente su idioma.

Diversos formatos de archivo

Para identificar correctamente qué bytes de un documento representan caracteres, es necesario gestionar correctamente el formato del archivo. Los motores de búsqueda que admiten múltiples formatos de archivo deben poder abrir y acceder al documento correctamente, así como tokenizar sus caracteres.

Almacenamiento defectuoso

La calidad de los datos en lenguaje natural no siempre es perfecta. Un número indeterminado de documentos, sobre todo en internet, no siguen estrictamente el protocolo de archivo adecuado. Es posible que se incluyan caracteres binarios por error en distintas partes de un documento. Sin el reconocimiento de estos caracteres y su tratamiento apropiado, la calidad del índice o el rendimiento del indexador podrían verse afectados.

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 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. Este programa se conoce comúnmente como tokenizador , analizador sintáctico o analizador léxico . Muchos motores de búsqueda, así como otros programas de procesamiento del 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, representados por 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 uso de mayúsculas, minúsculas, mayúsculas y minúsculas, el idioma o la codificación, la categoría léxica (parte de la oración, 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 de la oración ). 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 objeto de investigación continua 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 varios formatos de documento , estos deben prepararse para la tokenización. El desafío radica en que muchos formatos de documento 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 el inicio de nuevas líneas, el énfasis en negrita y el tamaño o estilo de fuente . Si el motor de búsqueda ignorara la diferencia entre contenido y marcado, se incluiría información irrelevante en el índice, lo que daría lugar a malos resultados de búsqueda. El análisis de formato consiste en la identificación y el manejo del contenido de formato incrustado en los documentos, que controla la forma en que el documento se muestra en la pantalla de un ordenador o es interpretado por un programa informático. 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 particularidades de los distintos formatos de archivo. Algunos formatos de archivo son propietarios y se divulga muy poca información, mientras que otros están bien documentados. Algunos formatos de archivo comunes y bien documentados que admiten muchos motores de búsqueda son:

• HTML
• Archivos de texto ASCII (un documento de texto sin formato legible por ordenador específico)
• Formato de documento portátil ( PDF ) de Adobe
• PostScript (PS)
• Látex
• Formatos de servidor de noticias de la red UseNet
• XML y derivados como RSS
• SGML
• Formatos de metadatos multimedia como ID3
• Microsoft Word
• Microsoft Excel
• Microsoft PowerPoint
• IBM Lotus Notes

Entre las opciones para trabajar con distintos formatos se incluyen el uso de una herramienta de análisis sintáctico comercial disponible públicamente que ofrece la organización que desarrolló, mantiene o es propietaria del formato, y la escritura de un analizador sintáctico personalizado .

Algunos motores de búsqueda permiten inspeccionar archivos almacenados en formato comprimido o cifrado. Al trabajar 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 archivo comprimido compatibles más comunes incluyen:

• ZIP - Archivo comprimido ZIP
• RAR - Archivo de archivo de Roshal
• CAB - Archivo de gabinete de Microsoft Windows
• Gzip - Archivo comprimido con gzip
• BZIP - Archivo comprimido con bzip2
• Archivo de cinta (TAR) , archivo de archivo Unix , no comprimido (en sí mismo)
• TAR.Z, TAR.GZ o TAR.BZ2: archivos comprimidos de Unix con Compress, GZIP o BZIP2.

El análisis de formato puede implicar métodos de mejora de la calidad para evitar incluir "información errónea" en el índice. El contenido puede manipular la información de formato para incluir contenido adicional. Ejemplos de abuso del formato de documentos para spamdexing :

• Incluir cientos o miles de palabras en una sección que está oculta a la vista en la pantalla del ordenador, pero visible para el indexador, mediante el uso de formato (por ejemplo, la etiqueta "div" oculta en HTML , que puede incorporar el uso de CSS o JavaScript para ello).
• Configurar el color de la fuente de primer plano de las palabras para que sea el mismo que el color de fondo, haciendo que las palabras queden ocultas en la pantalla del ordenador para la persona que visualiza el documento, pero no para el indexador.

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 organizadas. Muchos documentos en la web , como boletines informativos e informes corporativos, contienen contenido erróneo y secciones laterales que no contienen material principal (aquello de 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 muestre, o se represente, en diferentes áreas de la vista, el marcado sin procesar puede almacenar esta información secuencialmente. 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 del ordenador. 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 incorrecta de las palabras. Se observan dos problemas principales:

• El contenido de diferentes secciones se trata como relacionado en el índice cuando en realidad no lo está.
• El contenido de la barra lateral de la organización se incluye en el índice, pero dicho contenido no contribuye al significado del documento, y el índice está lleno de una representación deficiente de sus documentos.

El análisis de secciones puede requerir que el motor de búsqueda implemente la lógica de renderizado de cada documento, esencialmente una representación abstracta del documento real, y luego indexe dicha representación. Por ejemplo, algunos contenidos en Internet se renderizan mediante JavaScript. Si el motor de búsqueda no renderiza la página y evalúa el JavaScript dentro de ella, no "vería" este contenido de la misma manera y lo indexaría 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 mediante JavaScript o utilizan la etiqueta Noscript ( Archivado el 7 de julio de 2020 en Wayback Machine) para garantizar que la página web se indexe correctamente. Al mismo tiempo, este hecho también puede ser explotado para hacer que el indexador del motor de búsqueda "vea" un contenido diferente al del usuario.

La indexación a menudo debe reconocer las etiquetas HTML para organizar la prioridad. Indexar etiquetas de baja prioridad a alta prioridad, 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 considere los textos extensos como fuente relevante debido a la fuerte compatibilidad del sistema de tipos. ^{[ 22 ]}

La indexación de metaetiquetas desempeña 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. En las páginas HTML, la metaetiqueta contiene palabras clave que también se incluyen en el índice. La tecnología de los primeros motores de búsqueda de Internet solo indexaba las palabras clave de las metaetiquetas para el índice directo; el documento completo no se analizaba. En aquel entonces, la indexación de texto completo no estaba tan consolidada, ni el hardware informático era capaz de soportar dicha tecnología. El diseño del lenguaje de marcado HTML incluyó inicialmente soporte para metaetiquetas precisamente para que se indexaran de forma adecuada y sencilla, sin necesidad de tokenización. ^{[ 23 ]}

Con el auge de Internet durante la década de 1990, muchas empresas tradicionales se digitalizaron y crearon sitios web corporativos. Las palabras clave utilizadas para describir las páginas web (muchas de ellas corporativas, similares a folletos de productos) pasaron de ser descriptivas a estar orientadas al marketing, con el objetivo de impulsar las ventas mediante un posicionamiento destacado en los resultados de búsqueda para consultas específicas. El hecho de que estas palabras clave se especificaran de forma subjetiva dio lugar al spamdexing , lo que impulsó 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 y las empresas de motores de búsqueda solo podían incluir una cantidad limitada de palabras clave de marketing en el contenido de una página web antes de agotar toda la información interesante y útil. Dado este conflicto de intereses con el objetivo empresarial de diseñar sitios web atractivos y que fidelizaran a los usuarios, se modificó la fórmula del valor de vida del cliente para incorporar contenido más útil en el sitio web con la esperanza de retener al visitante. En este sentido, la indexación de texto completo resultó más objetiva y mejoró la calidad de los resultados de los motores de búsqueda, ya que supuso un paso más para alejarse del control subjetivo de la ubicación de los resultados, 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 que los autores puedan personalizar aún más la forma en que el motor de búsqueda indexará el contenido de diversos archivos, información que no se deduce directamente del 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 la indexación de texto completo.