Le plus simple des algorithmes de recherche examine les éléments un à un, jusqu’à trouver le bon ou épuiser la liste. C’est exactement ce que fait le mot-clé in de Python.
Le coût dépend de la position de l’élément cherché : une seule comparaison s’il est en tête, $n$ s’il est en queue, et $n$ aussi s’il est absent, car il faut alors tout examiner pour en être sûr. C’est ce pire cas qu’on retient pour juger un algorithme : la recherche séquentielle est linéaire, son coût croît comme $n$. Sans aucune information sur l’ordre des éléments, on ne peut d’ailleurs pas faire mieux : tant qu’un élément n’a pas été regardé, il pourrait être celui qu’on cherche.
Trouver le plus grand élément demande lui aussi un seul passage : on garde en mémoire le meilleur rencontré jusqu’ici, et on le remplace dès qu’on trouve mieux. Et le deuxième plus grand ? On peut chercher le maximum, l’écarter, puis chercher de nouveau : deux passages, environ $2n$ comparaisons. Ou bien tenir à jour les deux meilleurs au cours d’un seul passage.
En 1883, l’auteur d’Alice au pays des merveilles, Charles Dodgson de son vrai nom, mathématicien à Oxford, publie un pamphlet sur les tournois de tennis. Le vainqueur d’un tournoi à élimination directe est bien le meilleur joueur ; mais le finaliste malheureux, qui reçoit le second prix, n’est souvent pas le second meilleur. Celui-ci a très bien pu perdre dès le premier tour… contre le futur vainqueur.
L’observation donne un algorithme. Le second meilleur a forcément été battu par le champion, et par lui seul. Un tournoi désigne le maximum en $n-1$ matchs ; il suffit ensuite d’organiser un petit tournoi entre les $\log_2 n$ adversaires battus par le champion. Total : environ $n+\log_2 n$ comparaisons, au lieu de $2n$. On montre qu’on ne peut pas faire mieux.
Pour savoir si un mot de $m$ lettres apparaît dans un texte de $n$ lettres, l’idée naturelle est de faire glisser le mot le long du texte et de comparer, à chaque position, les lettres une à une. Il y a $n-m+1$ positions, et jusqu’à $m$ comparaisons pour chacune : dans le pire des cas, de l’ordre de $n\times m$ comparaisons. Ce pire cas n’a rien d’exotique : chercher aaaab dans une longue suite de a le réalise, et les textes très répétitifs, comme l’ADN, s’en approchent.
Combien de comparaisons de caractères faut-il au minimum pour s’assurer qu’un mot de $3$ lettres est absent d’un texte de $10$ lettres, avec la méthode naïve ?
Il y a $10-3+1=8$ positions, et dans le pire des cas $3$ comparaisons à chacune, soit $24$. Attention : en Python, texte[i:i+m] == mot ressemble à une seule opération, mais cache bien $m$ comparaisons.
En 1977, Robert Boyer et J Strother Moore renversent le point de vue : comparer le mot de droite à gauche. Si la dernière lettre de la fenêtre ne figure nulle part dans le mot, aucune des $m$ positions qui la contiennent ne peut convenir, et l’on peut sauter d’un coup de $m$ positions. Nigel Horspool simplifie la méthode en 1980 : une petite table, calculée une fois pour toutes sur le mot, donne pour chaque lettre la longueur du saut. Paradoxe : plus le mot cherché est long, plus la recherche va vite, puisque les sauts s’allongent.
Le pire cas de Horspool reste de l’ordre de $n\times m$ (le dernier exemple de l’animation le montre). D’autres algorithmes garantissent un coût proportionnel à $n+m$ quoi qu’il arrive, comme celui de Knuth, Morris et Pratt (1977), qui ne relit jamais une lettre du texte. Mais pour des textes ordinaires, les grands sauts de Boyer et Moore font merveille : c’est pourquoi l’outil grep des systèmes Unix, qui fouille des fichiers entiers en un clin d’œil, n’examine même pas la plupart des caractères qu’il parcourt.
En 2009, l’entreprise RockYou se fait dérober les mots de passe de 32 millions de comptes, stockés en clair. La liste des 14 millions de mots de passe distincts, le fichier rockyou.txt, est devenue un outil classique des tests de sécurité : un mot de passe qui y figure se casse en une fraction de seconde. Le premier de la liste, par nombre d’utilisateurs ? 123456.
Dans un dictionnaire papier, personne ne cherche un mot en lisant toutes les pages depuis la première. On ouvre au milieu, on regarde si le mot cherché vient avant ou après, et l’on recommence dans la bonne moitié. C’est possible parce que les mots sont triés : une seule comparaison élimine la moitié des candidats.
Chaque comparaison divisant le nombre de candidats par deux, $k$ comparaisons viennent à bout de $2^k$ éléments : il en faut environ $\log_2 n$. Pour les 14 millions de mots de passe du fichier rockyou, une fois triés, $24$ comparaisons suffisent, là où la recherche séquentielle peut en demander 14 millions. L’animation fait s’affronter les deux méthodes sur un même tableau trié : on peut choisir la cible en cliquant sur une case.
L’idée tient en une phrase ; le code demande pourtant une attention extrême. Voici une version qui semble correcte :
Un seul caractère manque : la boucle doit continuer tant que g <= d. Avec g < d, quand l’intervalle se réduit à une seule case, on sort de la boucle sans l’avoir examinée. Le test automatique ci-dessus, qui confronte la fonction à in sur des milliers de cas tirés au hasard, débusque l’erreur en un instant.
La recherche dichotomique apparaît dans la littérature en 1946, mais il faut attendre le début des années 1960 pour en lire une version correcte pour toutes les tailles de tableau. Dans les années 1980, Jon Bentley demande à des programmeurs professionnels de l’écrire, avec deux heures devant eux : environ 90 % des programmes rendus contiennent une erreur.
En 2006, Joshua Bloch, chez Google, révèle que la recherche dichotomique de la bibliothèque standard de Java, écrite d’après une version prouvée correcte, est fausse depuis près de dix ans. En cause, la ligne m = (g + d) / 2 : pour des tableaux de plus d’un milliard d’éléments, la somme g + d dépasse le plus grand entier représentable sur 32 bits et devient négative. Le correctif s’écrit m = g + (d - g) / 2. Python, dont les entiers n’ont pas de taille limite, est à l’abri de ce piège.
Un algorithme qui ne procède que par comparaisons peut se dessiner comme un arbre de décision : chaque comparaison est un embranchement à deux issues, et chaque feuille une réponse. Pour pouvoir désigner n’importe laquelle des $n$ cases, il faut au moins $n$ feuilles, donc un arbre de hauteur au moins $\log_2 n$. Aucun algorithme fondé sur des comparaisons ne peut battre la dichotomie dans le pire cas. Pour aller plus vite, il faudra cesser de comparer : c’est l’idée du hachage, plus bas.
La dichotomie ne cherche pas seulement dans des tableaux. Une fonction continue $f$ qui change de signe entre $a$ et $b$ s’annule entre les deux (c’est le théorème des valeurs intermédiaires). On évalue $f$ au milieu $m$ de l’intervalle, et l’on garde la moitié où le changement de signe persiste.
Chaque étape divise l’intervalle par deux : elle apporte un chiffre binaire de plus. Comme $2^{10}\approx 10^3$, il faut environ $3{,}3$ étapes par chiffre décimal, quelle que soit la fonction. C’est lent mais d’une robustesse à toute épreuve. La méthode de Newton, qui suit la tangente plutôt que de couper au milieu, double le nombre de chiffres exacts à chaque étape quand elle part assez près de la racine ; mais elle peut aussi s’égarer, là où la dichotomie ne se trompe jamais.
Pour compter les occurrences d’entiers compris entre $0$ et $n-1$, nul besoin de chercher : on réserve un tableau de $n$ cases, et l’entier $k$ est rangé dans la case $k$. Retrouver un élément ne coûte alors qu’un accès, quel que soit le nombre d’éléments. Le hachage étend cette idée à n’importe quelle clé, un mot par exemple : une fonction de hachage $h$ transforme la clé en un grand entier, et l’on range la clé dans la case $h(\text{clé})\bmod m$ d’un tableau de $m$ cases.
Deux clés peuvent tomber dans la même case : c’est une collision. On range alors les clés d’une même case dans une petite liste. Tout l’enjeu est que ces listes restent courtes, ce qui demande deux choses : une fonction de hachage qui disperse bien les clés, et un tableau qui grandit avec elles. Quand il y a plus de clés que de cases, on double la taille du tableau et l’on range chaque clé de nouveau. Ce grand ménage coûte cher, mais il est si rare qu’en moyenne chaque ajout reste rapide.
Les dictionnaires et les ensembles de Python sont des tables de hachage. Tester x in d sur un dictionnaire coûte en moyenne un temps constant, quel que soit le nombre de clés, là où x in L sur une liste en coûte un proportionnel à sa longueur. C’est ce qui permet, sur la page Complexité, de trouver un doublon en un seul passage.
Dans une classe de $23$ élèves, la probabilité que deux d’entre eux soient nés le même jour dépasse $50\,\%$ : c’est le paradoxe des anniversaires. Avec $365$ cases, les collisions apparaissent dès une vingtaine de clés, bien avant que la table soit pleine. On ne peut donc pas les éviter : on doit les gérer.
Elles peuvent même servir d’arme. En 2011, deux chercheurs montrent qu’en envoyant à un serveur web des milliers de clés soigneusement choisies pour tomber dans la même case, on transforme chaque recherche en parcours d’une longue liste, et l’on paralyse le serveur. Depuis, Python tire au hasard, à chaque lancement, un paramètre secret de sa fonction de hachage des chaînes : un attaquant ne peut plus prévoir les collisions.
Le hachage est imaginé en 1953 par Hans Peter Luhn, ingénieur chez IBM, à qui l’on doit aussi la « formule de Luhn », qui vérifie aujourd’hui encore les numéros de carte bancaire. Le mot anglais hash désigne un hachis : on hache la clé en morceaux et on les mélange, pour que des clés voisines atterrissent dans des cases éloignées.
Au jeu des vingt questions, il faut deviner un objet en posant des questions auxquelles on répond par oui ou par non. La meilleure question coupe l’ensemble des possibilités en deux parts égales : c’est la dichotomie, et $20$ questions départagent $2^{20}$, soit un million de possibilités. En 1948, Claude Shannon fait de cette idée une mesure : l’information apportée par une réponse se compte en bits, et une réponse qui divise les possibilités par deux en apporte exactement un.
Quand les réponses sont plus riches qu’un oui ou un non, une seule question peut apporter plusieurs bits. Au jeu du mot mystère, popularisé par Wordle en 2021, chaque essai renvoie une couleur pour chacune des cinq lettres : vert si elle est bien placée, jaune si elle figure ailleurs dans le mot, gris si elle est absente. Il y a $3^5=243$ réponses possibles, donc jusqu’à $\log_2 243\approx 7{,}9$ bits par essai. Le meilleur essai n’est pas forcément un mot possible : c’est celui dont les réponses se répartissent le plus uniformément, celui qui apporte en moyenne le plus d’information. Cette moyenne s’appelle l’entropie : si la réponse $r$ survient avec la probabilité $p_r$, elle vaut $\sum_r p_r\log_2(1/p_r)$.
Le mot mystère est tiré parmi les $1\,500$ mots de cinq lettres les plus courants, soit $10{,}6$ bits d’incertitude au départ, et les essais peuvent être n’importe lequel des $5\,891$ mots du dictionnaire. L’ordinateur qui joue à chaque fois le coup d’entropie maximale ouvre avec « tarie », qui apporte en moyenne $6{,}2$ bits ; il trouve le mot en $3{,}3$ essais en moyenne, et jamais en plus de $5$.
Mots acceptés : liste an-array-of-french-words (licence MIT) ; mots mystères choisis d'après les fréquences de wordfreq.
Chercher, au fond, c’est toujours réduire une incertitude. La recherche séquentielle n’élimine qu’un candidat par question ; la dichotomie en élimine la moitié, et ne peut pas faire mieux avec des réponses binaires ; le hachage pose une question dont la réponse, l’adresse de la case, contient d’un coup presque toute l’information.