¿Cuáles son los motores de búsqueda más utilizados?
Los motores de búsqueda son sistemas que recopilan y organizan recursos de información en Internet y luego los consultan por usted. Incluye tres partes: recopilación de información, clasificación de información y consulta del usuario.
Un motor de búsqueda es un sitio web que le brinda servicios de "recuperación" de información. Utiliza ciertos programas para clasificar toda la información en Internet para ayudar a las personas a buscar la información que necesitan en el vasto mar de. Internet.
Los primeros motores de búsqueda recopilaban las direcciones de servidores de recursos en Internet, las dividían en diferentes directorios según los tipos de recursos que proporcionaban y luego los clasificaban capa por capa.
Las personas que quieran encontrar la información que desean pueden ingresar capa por capa según su clasificación, y finalmente llegar al destino y encontrar la información que desean.
Este es en realidad el método más primitivo y sólo es adecuado cuando no hay mucha información en Internet.
Con el crecimiento geométrico de la información en Internet, han surgido motores de búsqueda reales. Estos motores de búsqueda conocen el comienzo de cada página del sitio web y luego buscan todos los hipervínculos en Internet, representando todas las palabras. se colocan en una base de datos.
Este es el prototipo del buscador actual.
Con la aparición de Yahoo!, el desarrollo de los motores de búsqueda también ha entrado en una época dorada y su rendimiento es más superior que antes.
Los motores de búsqueda actuales ya no sirven sólo para buscar información web, sino que se han vuelto más completos y perfectos.
Tomemos como ejemplo la autoridad de motores de búsqueda Yahoo! Desde marzo de 1995, cuando el chino-estadounidense Yang Zhiyuan y otros fundaron Yahoo!, han pasado de ser un único motor de búsqueda a tener comercio electrónico. , servicios de información de noticias, servicios de correo electrónico personal gratuito y otros servicios de red, que ilustran completamente el proceso de desarrollo de los motores de búsqueda desde uno único hasta uno completo.
Sin embargo, debido al funcionamiento de los motores de búsqueda y al rápido desarrollo de Internet, los resultados de búsqueda son cada vez más insatisfactorios.
Por ejemplo, una búsqueda de la palabra "computadora" puede arrojar millones de páginas de resultados.
Esto se debe a que los motores de búsqueda optimizan los resultados de búsqueda a través de la relevancia del sitio web. Esta relevancia está determinada por la posición de la palabra clave en el sitio web, el nombre del sitio web, las etiquetas y otras fórmulas.
Esto es lo que hace que los resultados de búsqueda de los motores de búsqueda sean numerosos y complejos.
Debido al desarrollo y cambios de Internet, la base de datos del motor de búsqueda también debe contener enlaces inactivos.
En este artículo presentamos Google, que es el prototipo de un motor de búsqueda a gran escala. Los motores de búsqueda se utilizan ampliamente en el hipertexto.
El diseño de Google puede rastrear e indexar páginas web de manera eficiente y los resultados de sus consultas son mejores que los de otros sistemas existentes.
La base de datos con hipervínculos y texto completo del prototipo contiene al menos 24.000.000 de páginas web.
Podemos descargarlo desde ://google.stanford.edu/.
Diseñar un motor de búsqueda es un trabajo desafiante.
Los motores de búsqueda indexan cientos de millones de páginas web que contienen una gran cantidad de palabras muy diferentes.
Y cada día se responden miles de consultas.
En Internet, aunque los grandes motores de búsqueda son muy importantes, rara vez se estudian en los círculos académicos.
Además, debido al rápido desarrollo de la tecnología y al aumento masivo de páginas web, construir un motor de búsqueda ahora es completamente diferente a hace tres años.
Este artículo describe en detalle nuestro motor de búsqueda a gran escala. Hasta donde sabemos, este es el primer artículo publicado que lo describe con tanto detalle.
Además de los problemas encontrados al aplicar técnicas tradicionales de búsqueda de datos a un número tan grande de páginas web, existen muchos desafíos técnicos nuevos, incluida la aplicación de información adicional en hipertexto para mejorar los resultados de búsqueda.
Este artículo resolverá este problema y describirá cómo utilizar información adicional en hipertexto para construir un sistema práctico a gran escala.
Cualquiera puede publicar información a voluntad en Internet. Cómo lidiar eficazmente con estos hipertextos desorganizados *** es también el tema en el que se centrará este artículo.
Palabras clave World Wide Web, motor de búsqueda, recuperación de información, PageRank, Google 1 Introducción La Web plantea nuevos desafíos a la recuperación de información.
La cantidad de información en la Web está creciendo rápidamente y, al mismo tiempo, constantemente llegan nuevos usuarios sin experiencia para experimentar el arte de la Web.
A la gente le gusta utilizar hipervínculos para navegar por Internet, normalmente empezando por páginas web importantes o motores de búsqueda como Yahoo.
Todo el mundo piensa que la Lista (directorio) contiene efectivamente los temas que interesan a todos, pero es subjetiva, costosa de establecer y mantener, lenta de actualizar y no puede incluir todos los temas esotéricos.
Los motores de búsqueda automatizados basados en palabras clave a menudo arrojan demasiadas coincidencias de baja calidad.
Para agravar el problema, algunos anuncios intentan engañar a los motores de búsqueda automatizados para captar la atención de la gente.
Creamos un gran motor de búsqueda para resolver muchos problemas en el sistema existente.
La aplicación de la estructura del hipertexto mejora enormemente la calidad de la consulta.
Nuestro sistema se llama Google, el nombre de la ortografía popular de googol, que es 10 elevado a 100. Esto coincide con nuestro objetivo de construir un gran motor de búsqueda.
1.1 Motor de búsqueda de Internet: ampliación: 1994-2000 La tecnología de los motores de búsqueda tuvo que crecer rápidamente (escale dramáticamente) para mantenerse al día con el crecimiento exponencial del número de sitios web.
En 1994, el primer motor de búsqueda web, World Wide Web Worm (WWWW), podía recuperar 110.000 páginas web y documentos web.
En noviembre de 1994, los principales motores de búsqueda afirmaban poder recuperar entre 2.000.000 (WebCrawler) y 100.000.000 de archivos web (de Search Engine Watch).
Es previsible que para el año 2000, el número de páginas web con capacidad de búsqueda supere el 1'000'000'000.
Al mismo tiempo, las visitas a los motores de búsqueda también crecerán a un ritmo alarmante.
En marzo y abril de 1997, World Wide Web Worm recibió un promedio de 1.500 consultas por día.
En noviembre de 1997, Altavista afirmó que estaba atendiendo aproximadamente 20.000.000 de consultas por día.
A medida que crezcan los usuarios de Internet, hacia el año 2000, los motores de búsqueda automatizados manejarán cientos de millones de consultas cada día.
El objetivo de diseño de nuestro sistema es resolver muchos problemas, incluida la calidad y la escalabilidad, e introducir tecnología de motor de búsqueda escalable para actualizarlo a una cantidad tan grande de datos.
1.2 Google: escalando con la Web Construir un motor de búsqueda que pueda adaptarse a la escala de la Web actual enfrentará muchos desafíos.
La tecnología de rastreo web debe ser lo suficientemente rápida para mantenerse al día con la velocidad de los cambios de las páginas web (mantenerlas actualizadas).
El espacio para almacenar índices y documentos debe ser lo suficientemente grande.
Los sistemas de indexación deben ser capaces de manejar eficientemente cientos de miles de millones de datos.
El procesamiento de consultas debe ser rápido, de cientos a miles por segundo.
A medida que la Web sigue creciendo, estas tareas se vuelven cada vez más difíciles.
Sin embargo, la eficiencia de ejecución y el costo del hardware también están aumentando rápidamente, lo que puede compensar parcialmente estas dificultades.
Hay varios factores que vale la pena destacar, como el tiempo de búsqueda del disco y la solidez del sistema operativo.
En el proceso de diseño de Google, tuvimos en cuenta tanto la tasa de crecimiento de la Web como las actualizaciones tecnológicas.
El diseño de Google se adapta bien para manejar conjuntos de datos masivos.
Puede utilizar eficientemente el espacio de almacenamiento para almacenar índices.
Las estructuras de datos optimizadas permiten un acceso rápido y eficiente (consulte la Sección 4.2).
Además, esperamos que el costo de almacenamiento e indexación sea lo más pequeño posible en relación con la cantidad de archivos de texto y páginas web HTML rastreadas (consulte el Apéndice B).
Para un sistema centralizado como Google, estas medidas han dado como resultado una escalabilidad satisfactoria del sistema (propiedades de escala).
1. 3 Objetivos de diseño 1.3.1 Mejorar la calidad de la búsqueda Nuestro principal objetivo es mejorar la calidad de los motores de búsqueda web.
En 1994, algunas personas pensaron que crear un índice de búsqueda completo facilitaría la búsqueda de cualquier dato.
Según Best of the Web 1994 - Navigators, "Los mejores servicios de navegación facilitan la búsqueda de cualquier información en la Web (cuando se pueden registrar todos los datos)".
Sin embargo, la Web en 1997 era completamente diferente.
Usuarios recientes de motores de búsqueda han confirmado que la integridad del índice no es el único criterio para evaluar la calidad de la búsqueda.
Los resultados de búsqueda que interesan a los usuarios suelen estar ocultos entre "resultados basura".
De hecho, en noviembre de 1997, sólo uno de los cuatro principales motores de búsqueda comerciales podía encontrarse a sí mismo (estaba entre los primeros diez resultados obtenidos al buscar su propio nombre).
La razón principal de este problema es que la cantidad de índices de documentos ha aumentado en varios órdenes de magnitud, pero la cantidad de documentos que los usuarios pueden ver no ha aumentado.
Los usuarios todavía sólo quieren ver las primeras docenas de resultados de búsqueda.
Por lo tanto, a medida que *** crece, necesitamos herramientas para hacer que los resultados sean precisos (el número de documentos relevantes en las primeras docenas de resultados devueltos).
Dado que se seleccionan docenas de documentos entre miles de documentos que son algo relevantes, de hecho, el concepto de relevancia se refiere a los mejores documentos.
La alta precisión es importante, incluso a expensas de la respuesta (el número total de documentos relevantes que el sistema puede devolver).
Afortunadamente, la información proporcionada por los enlaces de hipertexto puede ayudar a mejorar las búsquedas y otras aplicaciones.
Especialmente la estructura y el texto del enlace proporcionan mucha información para juzgar la relevancia y realizar un filtrado de alta calidad.
Google utiliza tanto la estructura de enlaces como el texto ancla (ver Secciones 2.1 y 2.2).
1.3.2 Investigación académica sobre motores de búsqueda A medida que pasa el tiempo, además del rápido desarrollo, la Web se comercializa cada vez más.
En 1993, sólo el 1,5% de los servicios Web derivaban de nombres de dominio.
En 1997, superó el 60%.
Al mismo tiempo, los motores de búsqueda han entrado en el negocio desde el ámbito académico.
Hasta ahora, la mayoría de los motores de búsqueda son propiedad de empresas y se han revelado pocos detalles técnicos.
Esto da como resultado que la tecnología de los motores de búsqueda todavía funcione en gran medida en la oscuridad y tienda a hacer publicidad (consulte el Apéndice A).
El principal objetivo de Google es promover el desarrollo y conocimiento de este campo en el ámbito académico.
Otro objetivo del diseño es ofrecer a todos un sistema práctico.
Las aplicaciones son muy importantes para nosotros porque creemos que algunas de las investigaciones más interesantes implicarán aprovechar la gran cantidad de datos de uso que están disponibles en los sistemas de red modernos (sistemas web).
Por ejemplo, cada día se realizan decenas de millones de estudios.
Sin embargo, obtener estos datos es muy difícil, principalmente porque no tienen valor comercial.
Nuestro objetivo de diseño final es establecer una arquitectura que pueda soportar nuevas investigaciones sobre datos web masivos.
Para respaldar nuevas investigaciones, Google guardó los documentos capturados reales en forma comprimida.
Uno de los objetivos del diseño de Google es establecer un entorno que permita a otros investigadores entrar rápidamente en este campo, procesar cantidades masivas de datos web y obtener resultados satisfactorios que son difíciles de obtener mediante otros métodos.
El sistema se estableció en un corto período de tiempo. Varios artículos ya han utilizado la base de datos creada por Google y otros están en proceso de comenzar.
Otro objetivo nuestro es establecer un entorno similar a un laboratorio espacial, donde los investigadores e incluso los estudiantes puedan diseñar o realizar algunos experimentos con nuestros datos web masivos.
2. Características del sistema El motor de búsqueda de Google tiene dos características importantes que ayudan a obtener resultados de búsqueda de alta precisión.
El primer punto es utilizar la estructura de enlaces de la Web para calcular el valor de Rank de cada página web, llamado PageRank, que se describirá en detalle en la página 98.
El segundo punto es que Google utiliza hipervínculos para mejorar los resultados de búsqueda.
2.1 PageRank: Clasificación de páginas web El gráfico de citas (enlaces) de la Web es un recurso importante, pero los motores de búsqueda actuales lo han ignorado en gran medida.
Construimos un gráfico que contiene 518'000'000 de hipervínculos, lo que es una muestra significativa.
Estos gráficos pueden calcular rápidamente el valor de PageRank de una página web. Es un estándar objetivo que se ajusta mejor a la evaluación de la gente sobre la importancia de una página web. Se basa en juzgar la importancia a través de citas.
Por tanto, en la web, PageRank puede optimizar los resultados de las consultas de palabras clave.
Para la mayoría de los temas, obtenemos resultados sorprendentes utilizando PageRank para optimizar la coincidencia de texto simple en consultas de títulos de páginas (demostración disponible en google.stanford.edu).
El PageRank también ayuda mucho con la búsqueda de texto completo en el sistema principal de Google.
2.1.1 Cálculo del PageRank La teoría de las citas en la recuperación de literatura se aplica a la Web. El número de enlaces que citan una página web refleja la importancia y la calidad de la página web hasta cierto punto.
PageRank desarrolló esta idea de que los enlaces entre páginas web son desiguales.
El PageRank se define de la siguiente manera: Suponemos que T1...Tn apunta a la página web A (por ejemplo, se cita).
El parámetro d es el factor de frenado, por lo que el resultado está entre 0 y 1.
Normalmente d es igual a 0,85.
d se presentará en detalle en la siguiente sección.
C(A) se define como el número de enlaces de la página web A a otras páginas web. El valor de PageRank de la página web A viene dado por la siguiente fórmula: PR(A) = (1-d). ) + d (PR(T1) /C(T1) + ... + PR(Tn)/C(Tn)) Tenga en cuenta que la forma de PageRank se distribuye a cada página web, por lo que la suma de PageRank de todas las páginas web es 1.
El PageRank o PR(A) se puede calcular utilizando un algoritmo iterativo simple, normalizando correspondientemente los principales vectores propios de la matriz de enlaces web.
Para un sitio web de tamaño mediano, se necesitarían varias horas para calcular el valor de PageRank para 26'000'000 de páginas web.
Hay algunos detalles técnicos que están fuera del alcance de este artículo.
2.1.2 Juicio intuitivo PageRank se considera un modelo de comportamiento del usuario.
Supongamos que navegar por Internet es aleatorio. Seguimos haciendo clic en enlaces y nunca volvemos. Al final nos aburrimos y elegimos aleatoriamente otra página web para empezar a navegar de nuevo.
La probabilidad de acceder aleatoriamente a una página web es su valor de PageRank.
El factor de frenado d es la posibilidad de cansarse de visitar aleatoriamente una página web y seleccionar aleatoriamente otra página web.
Para una sola página web o un grupo de páginas web, se añade una variable importante al factor de frenado d.
Esto permite que un individuo engañe deliberadamente al sistema para obtener un valor de PageRank más alto.
Disponemos de otros algoritmos de PageRank, ver página 98.
Otro juicio intuitivo es que si una página web tiene muchas páginas web apuntando a ella, o algunas páginas web con un alto valor de PageRank apuntan a ella, entonces esta página web es muy importante.
Intuitivamente, en la Web, si muchas páginas web hacen referencia a una página web, entonces vale la pena leer esa página web.
Si una página web es citada aunque sea una vez por una página de inicio importante como Yahoo, vale la pena visitarla.
Si la calidad de una página web no es alta o tiene un enlace inactivo, las páginas de inicio como Yahoo no enlazarán con ella.
PageRank maneja estos dos factores y los pasa de forma recursiva a través de enlaces de red.
& nbsp; 2.2 Texto de descripción del enlace (Anchor Text) Nuestro motor de búsqueda realiza un procesamiento especial del texto del enlace.
La mayoría de los motores de búsqueda asocian el texto del enlace con la página en la que se encuentra el enlace.
Además, vincúlelo a la página a la que apunta el enlace.
Esto tiene varias ventajas.
En primer lugar, el texto de descripción del enlace suele describir la página con mayor precisión que la página misma.
En segundo lugar, el texto de descripción del enlace puede enlazar a documentos que los motores de búsqueda de texto no pueden recuperar, como imágenes, programas y bases de datos.
Es posible hacer que la página web devuelta sea imposible de recuperar.
Tenga en cuenta que las páginas que no se pueden rastrear causarán problemas.
No se puede comprobar su validez antes de ser devueltos al usuario.
En este caso, el motor de búsqueda puede devolver una página web que no existe en absoluto, pero hay un hipervínculo que apunta a ella.
Sin embargo, este resultado se puede detectar, por lo que este tipo de problema rara vez ocurre.
El texto de descripción del enlace es la promoción de la página web enlazada. Esta idea se utiliza en World Wide Web Worm, principalmente porque ayuda a buscar información que no es texto y puede ampliar la búsqueda con una pequeña cantidad de descargas. documentos.
Hacemos un uso intensivo del texto de descripción del enlace porque ayuda a mejorar la calidad de los resultados de búsqueda.
Existen dificultades técnicas a la hora de utilizar descripciones de enlaces de forma eficaz debido a la gran cantidad de datos que deben procesarse.
Ahora podemos capturar 24'000'000 páginas web y hemos recuperado más de 259'000'000 textos de descripción de enlaces.
2.3 Otras funciones Además del PageRank y el texto de descripción del enlace de la aplicación, Google también tiene otras funciones.
En primer lugar, todas las visitas tienen información de ubicación, por lo que se puede aplicar ampliamente la proximidad en la búsqueda.
En segundo lugar, Google rastrea algunos detalles de la apariencia visual, como el tamaño de fuente.
El texto grande y en negrita es más importante que otro texto.
En tercer lugar, la base de conocimientos almacena las páginas web originales en texto completo.
3 Trabajos relacionados La historia de la investigación de recuperación web es breve.
World Wide Web Worm () es uno de los primeros motores de búsqueda.
Más tarde surgieron varios motores de búsqueda para investigaciones académicas, y la mayoría de ellos ahora son propiedad de empresas públicas.
En comparación con el crecimiento de la Web y la importancia de los motores de búsqueda, hay muy pocos artículos excelentes sobre la tecnología de los motores de búsqueda actuales.
Según Michael Mauldin (científico jefe de Lycos Inc), "varios servicios (incluido Lycos) prestan gran atención a los detalles de estas bases de datos.
" Aunque en el motor de búsqueda A Se ha trabajado mucho en ciertas características.
El trabajo representativo incluye la entrega de resultados de motores de búsqueda comerciales existentes o la creación de pequeños motores de búsqueda personalizados.
Por último, hay mucha investigación sobre sistemas de recuperación de información, especialmente en organizaciones organizadas*** (colecciones bien controladas).
En las dos secciones siguientes, analizaremos qué áreas de los sistemas de recuperación de información necesitan mejoras para funcionar mejor en la Web.
3.1 Recuperación de información El sistema de recuperación de información nació hace unos años y se ha desarrollado rápidamente.
Sin embargo, los objetos de la mayoría de las investigaciones sobre sistemas de recuperación de información son estructuras organizadas individuales a pequeña escala, como colecciones de artículos científicos o noticias sobre temas relacionados.
De hecho, el principal punto de referencia para la recuperación de información, la Text Retrieval Conference (), utiliza *** organizados a pequeña escala como punto de referencia.
El punto de referencia de la colección grande es de solo 20 GB. En comparación, los 24 millones de páginas web que capturamos representaron 147 GB.
Un sistema que funciona bien en TREC no necesariamente produce buenos resultados en la Web.
Por ejemplo, el modelo de espacio vectorial estándar intenta devolver el documento que es más similar a la solicitud de consulta, tratando tanto la solicitud de consulta como el documento como vectores compuestos por las palabras que aparecen en ellos.
En un entorno web, esta estrategia suele devolver documentos muy breves, que suelen ser la consulta más unas pocas palabras.
Por ejemplo, la consulta "Bill Clinton" devuelve páginas web que contienen sólo "Bill Clinton Sucks", que es lo que vemos en los principales motores de búsqueda.
Existe cierto debate en Internet acerca de que los usuarios deberían ser más precisos sobre lo que quieren consultar y utilizar más palabras en sus solicitudes de consulta.
Estamos totalmente en desacuerdo con esta opinión.
Si un usuario realiza una consulta como "Bill Clinton", debería obtener resultados ideales porque hay mucha información de alta calidad sobre este tema.
Como en los ejemplos dados, creemos que los estándares de recuperación de información deben evolucionar para poder procesar datos web de manera efectiva.
3.2 La diferencia entre colecciones bien organizadas (Colecciones Bien Controladas) y la Web La Web es una colección completamente desorganizada de colecciones heterogéneas de una gran cantidad de documentos.
Los documentos en la Web tienen mucha heterogeneidad tanto en información intrínseca como implícita.
Por ejemplo, los documentos utilizan diferentes lenguajes (tanto humanos como programáticos), vocabulario (direcciones [de correo electrónico], enlaces, códigos postales, números de teléfono, números de productos), tipos (texto, HTML, PDF, imágenes, sonidos) y algunos incluso son archivos creados por máquinas (archivos de registro o resultados de una base de datos).
La información que se puede inferir del documento pero que no está contenida en el documento se denomina información implícita.
La información implícita incluye la reputación de la fuente, la frecuencia de actualización, la calidad, las visitas y las citas.
No sólo existen varias fuentes posibles de información implícita, sino que la información que se detecta también es muy diferente, variando en varios órdenes de magnitud.
Por ejemplo, el uso de una página de inicio importante, como la de Yahoo, alcanza millones de visitas al día, en comparación con un artículo histórico anónimo que sólo puede visitarse una vez cada diez años.
Evidentemente, los motores de búsqueda procesan estos dos tipos de información de forma diferente.
Otra diferencia clara entre la Web y una estructura organizada es el hecho de que no existen restricciones para subir información a la Web.
El uso flexible de este para publicar cualquier información que tenga un impacto significativo en los motores de búsqueda, el bloqueo de rutas y la manipulación deliberada de los motores de búsqueda con fines de lucro se han convertido en un problema grave.
Estas cuestiones no han sido abordadas por los sistemas cerrados tradicionales de recuperación de información.
Se trata de esfuerzos de metadatos, que no se aplican en los motores de búsqueda web, porque ningún texto en la página web pretenderá ante el usuario un intento de manipular el motor de búsqueda.
Incluso hay empresas que manipulan específicamente los motores de búsqueda para obtener beneficios.
4 Anatomía del sistema Primero, proporcionamos una discusión de alto nivel sobre la arquitectura.
A continuación, describa en detalle las estructuras de datos importantes.
Finalmente, se examinarán rigurosamente las principales aplicaciones: rastreo web, indexación y búsqueda.
Figura 1. Arquitectura de Google de alto nivel 4.1 Descripción general de la arquitectura de Google En esta sección, veremos cómo funciona todo el sistema (proporcione un nivel alto), consulte la Figura 1.
Las aplicaciones y estructuras de datos no se analizan en esta sección, pero sí en secciones posteriores.
Para mayor eficiencia, la mayor parte de Google está implementado en c o c++, que puede ejecutarse en Solaris o Linux.
En el sistema de Google, el rastreo web (descarga de páginas web) lo completan varios rastreadores distribuidos.
Un servidor de URL es responsable de proporcionar una lista de URL a los rastreadores.
La página web capturada se entrega al servidor de almacenamiento.
Luego, el servidor de almacenamiento comprime las páginas web y las almacena en el repositorio de la base de conocimientos.
Cada página web tiene un ID, llamado docID. Cuando se analiza una nueva URL desde la página web, se le asigna un docID.
El indexador y clasificador son los encargados de establecer la función de índice.
El indexador lee documentos de la base de conocimiento, los descomprime y los analiza.
Cada documento se convierte en un conjunto de apariciones de palabras, llamadas visitas.
Los hits registran la palabra, su posición en el documento, el tamaño de fuente más cercano y las mayúsculas y minúsculas.
El indexador distribuye estas visitas en un conjunto de depósitos, lo que produce un índice parcialmente ordenado.
Otra función importante del indexador es analizar todos los enlaces de la página web y almacenar información importante y relevante en el archivo de anclaje de descripción del enlace.
Este archivo contiene suficiente información para determinar la información de cada enlace que enlaza y enlaza con el nodo, y el texto del enlace.
El solucionador de URL lee el archivo de anclaje de descripción del enlace, convierte la URL relativa en una URL absoluta y luego la convierte en un docID.
Indiza el texto de descripción del enlace y lo asocia con el docID al que apunta.
Al mismo tiempo, se establece una base de datos de enlaces compuesta por pares de docID.
Se utiliza para calcular el valor de PageRank de todos los documentos.
Los barriles clasificados por docID se envían al clasificador, y luego se clasifican según wordID para establecer un índice invertido.
Esto debe hacerse correctamente para que se necesite poco espacio para raspar.
El clasificador también proporciona una lista de docID y compensaciones para crear un índice invertido.
Un programa llamado DumpLexicon combina esta lista con el diccionario producido por el indexador para crear un nuevo diccionario para uso del buscador.
Este buscador utiliza un servidor web, utiliza el diccionario generado por DumpLexicon y utiliza el índice inverso y el PageRank a nivel de página anteriores para responder las preguntas de los usuarios.
4.2 Estructura de datos principal La estructura de datos optimizada de Google puede capturar una gran cantidad de documentos, crear índices y consultas a un costo relativamente bajo.
Aunque las tasas de CPU y de entrada y salida han aumentado rápidamente en los últimos años.
La búsqueda del disco todavía tarda 10 ms.
Los sistemas de Google están diseñados para evitar búsquedas en disco siempre que sea posible.
Esto tiene un gran impacto en el diseño de estructuras de datos.
4.2.1 Archivos grandes BigFiles se refiere a un sistema de múltiples archivos generado por archivos virtuales, que se direccionan con datos enteros con una longitud de 64 bits.
La asignación de espacio entre múltiples sistemas de archivos se realiza automáticamente.
El paquete BigFiles también maneja descriptores de archivos asignados y no asignados.
Dado que el sistema operativo no cubre nuestras necesidades, BigFiles también soporta opciones básicas de compresión.
4.2.2 Base de conocimientos Figura 2. Estructura de datos del repositorio La base de conocimientos contiene todo el HTML de cada página web.
Cada página web está comprimida con zlib (ver RFC1950).
La elección de la tecnología de compresión debe considerar tanto la velocidad como la relación de compresión.
Elegimos la velocidad de zlib en lugar de la alta tasa de compresión de bzip.
La relación de compresión de bzip para la base de conocimientos es cercana a 4:1.
La relación de compresión usando zlib es 3:1.
Los documentos se almacenan en la base de conocimientos uno por uno, con el prefijo docID, longitud y URL, como se muestra en la Figura 2.
No se requieren otras estructuras de datos para acceder a la base de conocimientos.
Esto ayuda con la coherencia y las actualizaciones de los datos.
Para reconstruir el sistema utilizando otras estructuras de datos, solo necesitamos modificar la base de conocimiento y los archivos de lista de errores del rastreador.
4.2.3 Índice de archivos El índice de archivos guarda cierta información sobre el documento.
El índice está organizado en el orden de docID, ISAM de ancho fijo (modo de acceso secuencial al índice).
Cada registro incluye el estado actual del archivo, un puntero a la base de conocimiento, suma de verificación del archivo y varias tablas estadísticas.
Si se ha rastreado un documento, el puntero apunta al archivo docinfo, que es un archivo de ancho variable que contiene la URL y el título.
De lo contrario, el puntero apunta a la lista de URL que contiene esta URL.
Este diseño permite estructuras de datos compactas y la capacidad de acceder a un registro en una consulta con un solo tiempo de búsqueda de disco.
También hay un archivo para convertir URL en docID.
Es una lista de sumas de verificación de URL y sus correspondientes ID de documento, ordenados por suma de verificación.
Para conocer el docID de una URL, es necesario calcular la suma de verificación de la URL y luego realizar una búsqueda binaria en el archivo de suma de verificación para encontrar su docID.
Al fusionar este archivo, un lote de URL se puede convertir en los docID correspondientes.
Los analizadores de URL utilizan esta tecnología para convertir URL en docID.
Este modo de actualización por lotes es crucial; de lo contrario, cada enlace requiere una consulta. Si se utiliza un disco, los datos de 322.000.000 de enlaces costarán más de un mes.
4.2.4 Diccionarios Los diccionarios vienen en varias formas diferentes.
Una diferencia importante con respecto a los sistemas anteriores es que los requisitos de memoria de los diccionarios se pueden satisfacer a un precio razonable.
En el sistema actualmente implementado, una máquina con 256M de memoria puede cargar el diccionario en la memoria.
El diccionario actual contiene 14.000.000 de palabras (aunque algunas palabras raramente utilizadas no se han agregado al diccionario).
Se implementa en dos partes: un vocabulario (una cadena contigua separada por valores nulos) y una tabla hash de punteros.
Hay alguna información auxiliar en el vocabulario para diferentes funciones, que está fuera del alcance de este artículo.
4.2.5 lista de aciertos La lista de aciertos es una lista de palabras que aparecen en un documento, incluida la posición, el tamaño de fuente y las mayúsculas y minúsculas.
La lista de resultados ocupa mucho espacio y se utiliza en índices hacia adelante y hacia atrás.
Por tanto, cuanto más eficiente sea su representación, mejor.
Consideramos varias opciones para la posición de codificación, el tamaño de fuente y las mayúsculas y minúsculas: codificación simple (3 enteros), codificación compacta (que admite una asignación óptima de bits) y codificación Huffman.
Consulte la Figura 3 para obtener detalles sobre Hit.
Nuestra codificación compacta utiliza 2 bytes por visita.
Hay dos tipos de golpes, golpes especiales y golpes ordinarios.
Los resultados especiales incluyen URL, título, texto de descripción del enlace y metaetiqueta.
Un acierto normal incluye todo lo demás.
Incluye bits de caracteres en mayúsculas y minúsculas, tamaño de fuente y 12 bits utilizados para describir la posición de la palabra en el documento (todas las posiciones que exceden 4095 se marcan como 4096).
El tamaño de fuente se expresa como un tamaño relativo con respecto a otras partes del documento, ocupando 3 bits (en realidad solo se utilizan 7 valores, porque la marca 111 es un acierto especial).
El hit especial consta de indicadores en mayúsculas y minúsculas, el tamaño de fuente es 7 bits para indicar que es un hit especial, se usan 4 bits para indicar el tipo de hit especial y 8 bits son Se utiliza para indicar la posición.
Para la posición de ocho bits del anclaje, se utilizan 4 bits para indicar la posición en el anclaje y 4 bits para indicar el hash de la tabla hash del docID en el que aparece el anclaje.
Las consultas de frases son limitadas y no tienen suficientes anclajes para algunas palabras.
Esperamos actualizar el método de almacenamiento de anclaje para resolver el problema de bits de dirección insuficientes y bits de campo docIDhash.