Un fait que j'ai toujours trouvé amusant est que Google est en fait dirigé par la bioinformatique (ok, je trouve ça drôle parce que je suis une sorte de bioinf…truc). Laissez-moi vous expliquer.
La bioinformatique a très tôt été confrontée au défi de rechercher de petits textes dans d'immenses chaînes de caractères de manière très rapide. Pour nous, la "chaîne de caractères immense" est bien sûr l'ADN. Souvent pas un seul ADN mais une base de données de plusieurs ADN de différentes espèces/individus. Les petits textes sont des protéines ou leur homologue génétique, un gène. La plupart du travail initial des biologistes computationnels était limité à trouver des homologies entre les gènes. Cela est fait pour établir la fonction des gènes nouvellement découverts en notant les similitudes avec des gènes déjà connus.
Maintenant, ces chaînes d'ADN deviennent vraiment très grandes et (perte de données!) la recherche doit être faite de manière extrêmement efficace. La majeure partie de la théorie moderne de la recherche de chaînes a donc été développée dans le contexte de la biologie computationnelle.
Cependant, il y a quelque temps, la recherche de texte conventionnelle avait atteint ses limites. Une nouvelle approche était nécessaire pour permettre la recherche de grandes chaînes en temps sublinéaire, c'est-à-dire sans regarder chaque caractère individuel. Il a été découvert que cela pouvait être résolu en prétraitant la grande chaîne et en construisant une structure de données d'index spéciale dessus. De nombreuses structures de données différentes ont été proposées. Chacune a ses forces et ses faiblesses, mais il y en a une qui est particulièrement remarquable car elle permet une recherche en temps constant. Maintenant, dans les ordres de grandeur dans lesquels Google opère, cela n'est plus strictement vrai car l'équilibrage de charge entre les serveurs, le prétraitement et d'autres éléments sophistiqués doivent être pris en compte.
Mais en essence, le prétendu index q-gram permet une recherche en temps constant. Le seul inconvénient : la structure de données devient ridiculement grande. Fondamentalement, pour permettre une recherche de chaînes comportant jusqu'à q caractères (d'où le nom), il faut une table qui a un champ pour chaque combinaison possible de q lettres (c'est-à-dire _q_S, où S est la taille de l'alphabet, disons 36 (= 26 + 10)). De plus, il doit y avoir un champ pour chaque position de lettre dans la chaîne qui a été indexée (ou dans le cas de Google, pour chaque site web).
Pour atténuer le poids de la taille, Google utilisera probablement plusieurs indices (en fait, ils le font, pour offrir des services comme la correction orthographique). Les premiers ne fonctionneront pas au niveau des caractères, mais au niveau des mots. Cela réduit q mais cela rend S infiniment plus grand, donc ils devront utiliser le hachage et les tables de collision pour faire face au nombre infini de mots différents.
À un niveau inférieur, ces mots hachés pointeront vers d'autres structures de données d'index qui, à leur tour, hacheront les caractères pointant vers des sites web.
Pour faire court, ces structures de données d'index q-gram sont sans doute la partie la plus centrale de l'algorithme de recherche de Google. Malheureusement, il n'existe pas de bons documents non techniques expliquant le fonctionnement des indices q-gram. La seule publication que je connaisse qui contient une description de la façon dont un tel index fonctionne est...hélas, mon mémoire de licence.
