Algorithmes de recherche

18-03-2023

Objectifs

  • connaître le fonctionnement de l’opérateur in ou de la méthode index définis sur certains itérables

  • comprendre l’intérêt de la notion de tri d’une collection de données

  • s’initier à la complexité des algorithmes et comprendre l’intérêt d’une telle étude.

Le problème

À de très nombreuses occasions, un programmeur est amené à soumettre l’exécution d’un calcul ou d’une instruction à la condition qu’une certaine valeur \(x\) est ou n’est pas dans une collection \(\ell\). En Python, ce programmeur écrit un code qui peut prendre la forme :

...
if x in l:
...

ou bien

...
if x not in l:
...

Parfois, ce programmeur ne peut pas se contenter d’une réponse booléenne : il lui faut en plus savoir ou trouver cet élément. Dans son code Python il écrit alors une expression de la forme :

...
l.index(x)
...

Étant donnés une structure de données \(\ell\) (la collection de données dans laquelle on cherche) et une valeur \(x\) (l’élément que l’on cherche), plusieurs types de problèmes peuvent être posés :

  • l’élément est-il ou non dans la collection ? autrement dit \(x\in\ell\) ?

  • si l’élément est dans la collection, où peut-on le trouver ? autrement dit, pour quel indice \(i\) a-t-on \(\ell[i] = x\) ?

    Cette dernière question pouvant être déclinée de plusieurs façons :

    • quel est le plus petit indice \(i\) tel que \(\ell[i] = x\) ?

    • quel est le plus grand ?

    • quels sont tous les indices ?

Dans ce qui suit, nous nous contenterons d’indiquer comment répondre au premier problème, c’est-à-dire l’appartenance ou non d’un élément à une collection. Autrement dit nous nous intéresserons plus à l’opérateur in qu’à la méthode index, mais il est très facile d’adapter les solutions du premier problème au second (en tout cas pour ses deux premières déclinaisons : plus petit indice, plus grand indice).

Nous allons traiter un problème un peu différent que celui que traite l’opérateur in : nous nous donnerons non seulement l’élément à chercher et la collection dans laquelle le chercher, mais aussi deux indices donnant les extrémités de l’intervalle de recherche.

Dit autrement, la question que nous allons résoudre est

\(x\in\ell[a:b] ?\),

où \(\ell[a:b]\) désigne la tranche des éléments de

\(\ell\) dont les indices sont compris entre \(a\) (inclus) et \(b\) (exclu), en suivant les notations usuelles de Python.

Appartenance d’un élément à une collection

Entrée : \(\ell\) une structure de données séquentielle,

\(x\) une valeur, et \(a\) et \(b\) deux indices

Sortie : Vrai si \(x\in\ell[a:b]\), et Faux dans le cas

contraire.

Nous ne répèterons plus cette spécification du problème dans les algorithmes qui suivront.

Dans la suite nous déclarerons fructueuse toute recherche d’élément qui réussit (sortie Vrai dans la spécification ci-dessus). Dans le cas contraire nous dirons qu’elle échoue ou qu’elle est non fructueuse.

Recherches dans une structure séquentielle non triée

Recherche fastidieuse

L’algorithme

Recherche fastidieuse

  1. trouve \(\leftarrow\) Faux

  2. Pour \(i\) variant de \(a\) à \(b -1\)

  3. \(\quad\) Si compare(\(\ell[i], x\)) = 0

  4. \(\quad\quad\) trouve \(\leftarrow\) Vrai

  5. \(\quad\) Fin Si

  6. Fin Pour

  7. Renvoyer : trouve

Son coût

Dans tous les cas, recherche fructueuse ou non, une recherche fastidieuse dans une tranche \(\ell[a:b]\) coûte \(b-a\) comparaisons.

Plus généralement une recherche dans une séquence de longueur \(n\) coûte \(n\).

Recherche séquentielle

L’algorithme

Recherche séquentielle dans une structure non triée

  1. trouve \(\leftarrow\) Faux

  2. \(i\leftarrow a\)

  3. TQ non trouve et \(i<b\)

  4. \(\quad\) Si compare(\(\ell[i], x\))=0

  5. \(\quad\quad\) trouve \(\leftarrow\) Vrai

  6. \(\quad\) Fin Si

  7. \(\quad i\leftarrow i + 1\)

  8. Fin TQ

  9. Renvoyer : trouve

Son coût

Recherches dans une structure séquentielle triée

Recherche séquentielle

L’algorithme

Recherche séquentielle dans une structure triée

  1. trouve \(\leftarrow\) Faux

  2. \(i\leftarrow a\)

  3. fini \(\leftarrow\) \(i \geq b\)

  4. TQ non trouve et non fini

  5. \(\quad cmp\leftarrow\) compare(\(x,\ell[i]\))

  6. \(\quad\) Si \(cmp = 0\)

  7. \(\quad\quad\) trouve \(\leftarrow\) Vrai

  8. \(\quad\) Fin Si

  9. \(\quad i\leftarrow i + 1\)

  10. \(\quad\) Si \(cmp = -1\) ou \(i=b\)

  11. \(\quad\quad\) fini \(\leftarrow\) Vrai

  12. \(\quad\) Fin Si

  13. Fin TQ

  14. Renvoyer : trouve

Son coût

Recherche dichotomique

L’algorithme

Recherche dichotomique dans une structure triée

  1. \(d\leftarrow a\)

  2. \(f\leftarrow b-1\)

  3. TQ \(d<f\)

  4. \(\quad m\leftarrow \frac{d+f}{2}\)

  5. \(\quad\) Si compare(\(\ell[m],x\)) < 0

  6. \(\quad\quad d\leftarrow m+1\)

  7. \(\quad\) Sinon

  8. \(\quad\quad f\leftarrow m\)

  9. \(\quad\) Fin Si

  10. Fin TQ

  11. Renvoyer \(d<b\) et \(x = \ell[d]\)

Son coût

L’arbre ci-dessous montre tous les déroulements possibles d’une recherche dichotomique dans une séquence de longueur huit (intervalle de recherche initial 0..8). Chaque nœud contient l’intervalle dans lequel se fait la recherche et correspond à une comparaison de l’élément recherché à un élément de la séquence. On voit donc que dans tous les cas, recherche fructueuse ou non, quatre comparaisons permettent de conclure à l’appartenance ou non de l’élément recherché.

Figure made with TikZ

L’arbre ci-dessous montre la même chose pour une séquence de longueur 10. Cette fois le nombre de comparaisons pour une recherche fructueuse ou non peut être égal à quatre ou cinq.

Figure made with TikZ

Pour une recherche dichotomique dans une séquence de longueur \(n=2^p\), la boucle TQ de l’algorithme dichotomique fait \(p\) étapes pour arriver à une tranche de longueur 1. À raison d’une comparaison par étape, cela donne \(p\) comparaisons. En ajoutant la comparaison effectuée après l’itération cela en fait en tout \(p+1\) comparaisons dans tous les cas, que la recherche soit fructueuse ou non. Et comme on a

\[n = 2^p,\]

on en déduit que

\[p = \frac{\ln{n}}{\ln{2}} = \log_2{n},\]

où \(\ln{x}\) désigne le logarithme népérien de \(x\), et \(\log_2{x}\) le logarithme de base 2.

Finalement lorsque la longueur de la séquence dans laquelle la recherche est effectuée est une puissance de 2, le nombre de comparaisons d’éléments de cette liste est toujours égal à

\[c(n) = 1 + \log_2{n}.\]

Dans le cas général, pour \(n\) non nécessairement égal à une puissance de 2, le nombre de comparaisons est dans l’intervalle :

\[1 + \lfloor\log_2{n}\rfloor \leq c(n) \leq 1 + \lceil\log_2{n}\rceil,\]

avec les notations :

  • \(\lfloor x\rfloor\) désignant la partie entière inférieure du nombre réel \(x\), autrement dit le plus grand entier inférieur ou égal à \(x\),

  • \(\lceil x\rceil\) désignant la partie entière supérieure du nombre réel \(x\), autrement dit le plus petit entier supérieur ou égal à \(x\).

(ces deux parties entières sont égales si et seulement si \(x\) est un nombre entier.)

On retiendra principalement que le nombre de comparaisons effectuées par l’algorithme de recherche dichotomique croit logarithmiquement en fonction de la taille de la séquence dans laquelle s’effectue la recherche.

Exemple :

Voici un tableau donnant quelques nombres de comparaisons dans des séquences triées de différentes longueurs :

Longueur

Dichotomie

Séquentielle

128

7

entre 1 et 128

1024

11

entre 1 et 1024

\(10^6\)

20 ou 21

entre 1 et \(10^6\)

Ces valeurs numériques montrent tout l’intérêt de l’algorithme de recherche dichotomique, et des structures triées.

Note

L’algorithme peut facilement être modifié pour obtenir des recherches fructueuses avec moins de comparaisons. Comment ? C’est un excellent exercice que de répondre à cette question.

Et dans les dictionnaires ?

La recherche d’une information dans un dictionnaire ne se traite pas du tout de la même façon que dans une séquence :

  • d’abord parce que la notion d’indice n’existe pas ; elle est remplacée par celle de clé

  • ensuite parce qu’elle n’opère absolument pas par comparaison des éléments, mais par calcul d’une adresse grâce à une fonction spéciale nommée fonction de hachage.

Ce qui suit vise à donner une première idée de la façon dont est organisée un dictionnaire et de ce qu’est une fonction de hachage.

Un dictionnaire peut être vu comme une liste de couples (clé, valeur) dont la longueur est fixée une fois pour toute et dont certains éléments ne sont pas attribués (et valent None par exemple).

L’exemple de dictionnaire vu dans un cours précédent donnant les tarifs des fruits pourrait être représenté par la liste

tarifs = [None, None, ('pomme', 1.95), None, None,
          None, None, None, None, None,
          None, None, None, ('banane', 2.59), None,
          None, ('orange', 1.95), None, None, None]

Ce dictionnaire de taille 20 contient trois associations, et par conséquent 17 emplacements vides.

Fonction de hachage

Comment placer les associations dans le dictionnaire de façon à pouvoir les retrouver facilement ? La réponse consiste à définir une fonction qui à partir d’une clé détermine l’indice où doit être placée l’association. Une telle fonction est nommée fonction de hachage.

Sur notre exemple de dictionnaire dont les clés sont des chaînes de caractères, une fonction de hachage pourrait être une fonction qui calcule la somme des numéros Unicode des caractères composant la clé. Cette somme pouvant dépasser la longueur TAILLE_MAX du dictionnaire, on la calcule modulo cette longueur.

Exemple

Supposons que l’on veuille calculer l’indice où serait rangée une association de clé fraise. La liste des numéros unicode des caractères de cette clé est [102, 114, 97, 105, 115, 101] dont la somme vaut 634, ce qui modulo TAILLE_MAX=20 donne 14.

Ainsi, si nous nommons hache la fonction qui à une chaîne associe un indice compris entre 0 et TAILLE_MAX selon ce procédé, on a :

>>> hache('fraise')
14

Cette fonction se code facilement en Python :

Construction de dictionnaires

La construction de dictionnaire se fait aisément en

  • commençant par construire un dictionnaire vide (fonction dico_vide ci-dessous)

  • et en ajoutant une à une toutes les associations (à l’aide de la fonction dico_add ci-dessous).

Recherche dans un dictionnaire

L’algorithme

Rechercher un élément dans un dictionnaire à partir de sa clé consiste à calculer l’adresse de son emplacement dans le dictionnaire à l’aide de la fonction de hachage.

Son coût

On voit bien que le coût d’une recherche réside essentiellement dans le coût de la fonction de hachage. Et le coût de cette fonction ne dépend pas du nombre d’associations stockées dans le dictionnaire 1 : il est donc constant.

C’est ce dernier point qui donne tout l’intérêt des structures de données de type dictionnaires en Python 2.

Avertissement

Dans la présentation qui vient d’être faite, un problème a été masqué par souci de simplification. Ce problème est celui des collisions. Les collisions sont des clés distinctes pour lesquelles la fonction de hachage produit le même nombre. Dans ce cas, on est amené à stocker deux associations au même endroit : c’est une collision. Avec notre fonction de hachage décrite plus haut, le couple ('fraise', 'prune') est une collision :

>>> hache('fraise')
14
>>> hache('prune')
14

Dans la pratique, il est bien évidemment important de gérer ces collisions (c’est d’ailleurs ce que font très bien les dictionnaires de Python). Mais c’est un problème que nous n’aborderons pas dans ce cours 3.

Notes

1

le coût d’une fonction de hachage dépend cependant de la taille de l’espace réservé pour le dictionnaire (TAILLE_MAX).

2

et qu’on nomme tables de hachage dans bien d’autres langages de programmation.

3

il le sera dans le cours Algorithmes et Structures de Données du semestre 4 de la licence d’informatique.