Un hecho que siempre he encontrado gracioso es que Google está dirigido por la bioinformática ('kay, me parece gracioso porque soy un bioinf ... cosita). Dejame explicar.
La bioinformática desde el principio tuvo el desafío de buscar textos pequeños en cadenas gigantescas muy rápido. Para nosotros, la "cuerda gigantesca" es, por supuesto, ADN. A menudo no es un solo ADN sino una base de datos de varios ADN de diferentes especies/individuos. Los textos pequeños son proteínas o su contraparte genética, un gen. La mayor parte del primer trabajo de biólogos computacionales se restringió para encontrar homologías entre los genes. Esto se hace para establecer la función de genes recién encontrados al observar similitudes con genes que ya se conocen.
Ahora, estas cadenas de ADN se hacen muy grandes y la búsqueda (con pérdidas) tiene que hacerse de manera extremadamente eficiente. La mayor parte de la teoría moderna de la búsqueda de cadenas se desarrolló así en el contexto de la biología computacional.
Sin embargo, hace bastante tiempo, se agotó la búsqueda de texto convencional. Se necesitaba un nuevo enfoque que permitiera buscar cadenas grandes en tiempo sublineal, es decir, sin mirar cada carácter individual. Se descubrió que esto se puede resolver preprocesando la cadena grande y construyendo una estructura de datos de índice especial sobre ella. Se han propuesto muchas estructuras de datos diferentes. Cada uno tiene sus fortalezas y debilidades, pero hay uno que es especialmente notable porque permite una búsqueda en tiempo constante.Ahora, en los órdenes de magnitud en los que opera Google, esto ya no es estrictamente cierto porque debe tenerse en cuenta el equilibrio de carga en los servidores, el preprocesamiento y algunas otras cosas sofisticadas.
Pero en esencia, el llamado q-gram index permite una búsqueda en tiempo constante. La única desventaja: la estructura de datos se vuelve ridículamente grande. Esencialmente, para permitir una búsqueda de cadenas con hasta q caracteres (de ahí el nombre), se requiere una tabla que tiene un campo para cada combinación posible de q letras (es decir, qS, donde S es del tamaño del alfabeto, digamos 36 (= 26 + 10)). Además, debe haber un campo para cada posición de letra en la cadena indexada (o en el caso de google, para cada sitio web).
Para mitigar el tamaño, Google probablemente use múltiples índices (de hecho, do, para ofrecer servicios como la corrección ortográfica). Los más altos no funcionarán en el nivel de personaje sino en el nivel de palabra. Esto reduce q pero hace que S sea infinitamente más grande, así que tendrán que usar hashing y tablas de colisión para hacer frente al infinito número de palabras diferentes.
En el siguiente nivel, estas palabras hash apuntarán a otras estructuras de datos de índice que, a su vez, tendrán caracteres hash que apuntan a sitios web.
En pocas palabras, estas q -las estructuras de datos de índice de gráficos son sin duda la parte más central del algoritmo de búsqueda de Google. Lamentablemente, no hay buenos documentos no técnicos que expliquen cómo funcionan los q -gram índices. La única publicación que sé que contiene una descripción de cómo funciona dicho índice es ... ay, mi bachelor thesis.
Solo para aclarar 'massive': cientos de miles de servidores. Supongo que ninguno fuera de Google sabe el número real y debe estar cambiando todo el tiempo. –
-1 No es tan simple ... –