Chapitre 4 : Algorithmes de recherche

La recherche est une opération fondamentale en informatique qui consiste à trouver un élément ou un ensemble d'éléments particuliers dans une collection de données. Des algorithmes et des structures de données de recherche efficaces sont essentiels pour de nombreuses applications, des bases de données et des systèmes de fichiers à la recherche d'informations et à la géométrie computationnelle. Dans ce chapitre, nous explorons plusieurs algorithmes et structures de données de recherche importants, notamment les arbres de recherche binaires, les arbres de recherche équilibrés et les tables de hachage. Nous discutons également de diverses applications de la recherche dans des scénarios du monde réel.

Tables de symboles et structures de données

Une table de symboles est un type de données abstrait qui associe des clés à des valeurs, en fournissant des opérations pour insérer des paires clé-valeur, rechercher une valeur à partir de sa clé et supprimer des paires clé-valeur. Les tables de symboles sont également connues sous le nom de dictionnaires ou de tableaux associatifs dans différents langages de programmation. Ce sont des structures de données fondamentales utilisées dans un large éventail d'applications, telles que :

• Les compilateurs, où les tables de symboles sont utilisées pour stocker des informations sur les variables, les fonctions et d'autres identificateurs.
• Les bases de données, où les index sont construits à l'aide de tables de symboles pour permettre une recherche et une récupération rapides des enregistrements.
• Les routeurs réseau, qui utilisent des tables de symboles pour stocker des informations de routage afin d'assurer un acheminement efficace des paquets.

Il existe plusieurs structures de données qui peuvent être utilisées pour mettre en œuvre des tables de symboles, chacune avec ses propres compromis en termes de performances de recherche, d'insertion et de suppression. Dans cette section, nous nous concentrons sur deux structures de données importantes : les arbres de recherche binaires et les tables de hachage.

Arbres de recherche binaires (ARB)

Un arbre de recherche binaire (ARB) est une structure de données hiérarchique qui stocke des paires clé-valeur d'une manière qui permet des opérations de recherche, d'insertion et de suppression efficaces. Chaque nœud d'un ARB contient une clé, une valeur associée et des références à ses nœuds enfants gauche et droit. La clé de chaque nœud est supérieure à toutes les clés de son sous-arbre gauche et inférieure à toutes les clés de son sous-arbre droit.Voici la traduction française du fichier Markdown, avec les commentaires traduits mais le code non traduit :

e. Cette propriété, connue sous le nom d'invariant BST, permet une recherche efficace en prenant des décisions binaires à chaque nœud.

Voici un exemple d'un BST simple :

      4
    /   \
   2     6
  / \   / \
 1   3 5   7

La recherche dans un BST implique de comparer la clé cible avec la clé du nœud actuel et de rechercher de manière récursive dans le sous-arbre gauche ou droit en fonction de la comparaison. Si la clé cible est trouvée, la valeur associée est renvoyée. Si la clé cible n'est pas trouvée après avoir atteint une référence nulle, la recherche se termine sans succès.

L'insertion dans un BST suit un processus similaire à la recherche. Nous comparons la clé du nouveau nœud avec les clés du BST et traversons l'arbre jusqu'à ce que nous trouvions une référence nulle, où nous attachons le nouveau nœud en tant que feuille. La suppression dans un BST est un peu plus complexe, car elle nécessite de gérer trois cas : la suppression d'un nœud feuille, la suppression d'un nœud avec un seul enfant et la suppression d'un nœud avec deux enfants.

La complexité temporelle moyenne des cas de recherche, d'insertion et de suppression dans un BST est de O(log n), où n est le nombre de nœuds de l'arbre. Cependant, dans le pire des cas (par exemple, lorsque le BST se dégrade en une liste chaînée), la complexité temporelle devient O(n). Pour atténuer ce problème, nous pouvons utiliser des BST auto-équilibrés, comme les arbres AVL ou les arbres rouges et noirs, qui maintiennent une structure d'arbre presque équilibrée et garantissent une performance pire des cas de O(log n) pour toutes les opérations.

Tables de hachage

Une table de hachage est une structure de données qui fournit une recherche, une insertion et une suppression moyennes rapides en utilisant une fonction de hachage pour mapper les clés vers des indices dans un tableau, appelés compartiments. La fonction de hachage prend une clé en entrée et renvoie un indice entier, qui est utilisé pour localiser le compartiment correspondant dans le tableau. Idéalement, la fonction de hachage devrait répartir uniformément les clés dans les compartiments pour minimiser les collisions (c'est-à-dire plusieurs clés mappées sur le même compartiment).

Lorsqu'une collision se produit, il existe deux principales approches pour la résoudre :

1. Chaînage séparé : Chaque compartiment est implémenté comme uneVoici la traduction française du fichier Markdown :

Listes chaînées : et toutes les paires clé-valeur qui se hachent dans le même compartiment sont stockées dans la liste chaînée de ce compartiment.

2. Adressage ouvert : Lorsqu'une collision se produit, la table de hachage sonde d'autres compartiments dans une séquence prédéfinie jusqu'à ce qu'un compartiment vide soit trouvé. Les techniques de sondage courantes incluent le sondage linéaire, le sondage quadratique et le double hachage.

Voici un exemple d'une table de hachage avec chaînage séparé :

+---+    +-------+
| 0 |--->| (1,A) |
+---+    +-------+
| 1 |--->| (5,B) |---->| (9,C) |
+---+    +-------+     +-------+
| 2 |
+---+
| 3 |--->| (7,D) |
+---+    +-------+
| 4 |
+---+

Dans cet exemple, les clés 1, 5 et 9 se hachent toutes dans le compartiment 1, donc elles sont stockées dans une liste chaînée attachée à ce compartiment. La clé 7 se hache dans le compartiment 3 et est la seule paire clé-valeur dans ce compartiment.

La complexité temporelle moyenne des opérations de recherche, d'insertion et de suppression dans une table de hachage bien conçue est de O(1), ce qui en fait l'une des structures de données les plus rapides pour ces opérations. Cependant, la complexité temporelle dans le pire des cas peut se dégrader jusqu'à O(n) si la fonction de hachage est mal choisie ou s'il y a de nombreuses collisions. Pour maintenir de bonnes performances, il est essentiel d'utiliser une fonction de hachage de haute qualité et de redimensionner la table de hachage lorsque le facteur de charge (c'est-à-dire le rapport entre le nombre de paires clé-valeur et le nombre de compartiments) dépasse un certain seuil, généralement autour de 0,75.

Arbres de recherche équilibrés

Bien que les arbres de recherche binaires offrent des opérations de recherche, d'insertion et de suppression efficaces en moyenne, leurs performances peuvent se dégrader de manière significative dans le pire des cas. Les arbres de recherche équilibrés sont une famille de structures de données qui maintiennent une structure d'arbre presque équilibrée, assurant de bonnes performances dans le pire des cas. Dans cette section, nous discutons de deux arbres de recherche équilibrés populaires : les arbres AVL et les arbres rouges et noirs.

Arbres AVL

Un arbre AVL, nommé d'après ses inventeurs Adelson-Velsky et Landis, est un arbre de recherche binaire auto-équilibré dans lequel les hauteurs des sous-arbres gauche et droit de tout nœud diffèrent d'au plus un. Cette différence de hauteurVoici la traduction française du fichier Markdown, avec les commentaires traduits mais le code non traduit :

La différence de hauteur entre les sous-arbres gauche et droit d'un nœud est appelée le facteur d'équilibre. Lorsqu'une opération d'insertion ou de suppression viole la propriété AVL (c'est-à-dire que le facteur d'équilibre devient supérieur à 1 ou inférieur à -1), l'arbre est rééquilibré par une ou plusieurs rotations.

Il existe quatre types de rotations utilisées pour rééquilibrer les arbres AVL :

1. Rotation à gauche : effectuée lorsque le facteur d'équilibre d'un nœud est supérieur à 1 et que le facteur d'équilibre de son enfant droit est non négatif.

2. Rotation à droite : effectuée lorsque le facteur d'équilibre d'un nœud est inférieur à -1 et que le facteur d'équilibre de son enfant gauche est non positif.

3. Rotation gauche-droite : effectuée lorsque le facteur d'équilibre d'un nœud est supérieur à 1 et que le facteur d'équilibre de son enfant droit est négatif.

4. Rotation droite-gauche : effectuée lorsque le facteur d'équilibre d'un nœud est inférieur à -1 et que le facteur d'équilibre de son enfant gauche est positif.

En maintenant la propriété AVL, les arbres AVL garantissent une complexité temporelle dans le pire des cas de O(log n) pour les opérations de recherche, d'insertion et de suppression. Cependant, les facteurs constants impliqués dans les opérations sur les arbres AVL sont légèrement plus élevés par rapport aux arbres de recherche binaires ordinaires en raison de la surcharge du maintien des facteurs d'équilibre et de l'exécution des rotations.

Arbres Rouges-Noirs

Un arbre rouge-noir est un autre arbre de recherche binaire auto-équilibré qui maintient une structure presque équilibrée. Chaque nœud d'un arbre rouge-noir est coloré en rouge ou en noir, et l'arbre satisfait les propriétés suivantes :

1. La racine est toujours noire.
2. Tous les nœuds feuilles (NIL) sont noirs.
3. Si un nœud est rouge, ses deux enfants sont noirs.
4. Chaque chemin d'un nœud à l'un de ses nœuds feuilles descendants contient le même nombre de nœuds noirs.

Ces propriétés garantissent que le chemin le plus long de la racine à une feuille n'est pas plus de deux fois plus long que le chemin le plus court, assurant une complexité temporelle dans le pire des cas de O(log n) pour les opérations de recherche, d'insertion et de suppression.

Lorsqu'une opération d'insertion ou de suppression viole l'une des propriétés de l'arbre rouge-noir, l'arbre est rééquilibré par une série de changements de couleur et de rotations.Voici la traduction française du fichier Markdown, avec les commentaires traduits mais le code non traduit :

Le rééquilibrage dans les arbres rouges et noirs est généralement plus efficace que dans les arbres AVL, car il nécessite en moyenne moins de rotations. Cela fait des arbres rouges et noirs un choix populaire pour la mise en œuvre d'arbres de recherche équilibrés dans la pratique, comme dans la bibliothèque de modèles standard C++ (STL) et le cadre de collections Java.

Applications de la recherche

Les algorithmes et les structures de données de recherche ont de nombreuses applications dans divers domaines. Dans cette section, nous discutons de quelques exemples pour illustrer l'importance et la polyvalence de la recherche dans des scénarios du monde réel.

Bases de données et récupération d'informations

Les bases de données et les systèmes de récupération d'informations s'appuient fortement sur des techniques de recherche efficaces pour fournir un accès rapide aux données. Dans les bases de données relationnelles, des index sont construits à l'aide de structures de données comme les arbres B ou les tables de hachage pour permettre des recherches rapides d'enregistrements en fonction d'attributs spécifiques. Ces index permettent aux bases de données d'exécuter efficacement des requêtes avec des conditions sur les attributs indexés, réduisant considérablement l'espace de recherche et améliorant les performances des requêtes.

Dans les systèmes de récupération d'informations, comme les moteurs de recherche Web, des index inversés sont utilisés pour mapper les termes aux documents qui les contiennent. Un index inversé est essentiellement une table de symboles où les clés sont des termes et les valeurs sont des listes d'identifiants de documents. Lorsqu'un utilisateur soumet une requête, le moteur de recherche recherche les termes de la requête dans l'index inversé et récupère les listes de documents correspondantes, qui sont ensuite combinées et classées pour produire les résultats de recherche finaux.

Conception de compilateurs

Les compilateurs utilisent extensivement des tables de symboles pour suivre les identificateurs (par exemple, les noms de variables, les noms de fonctions) et leurs attributs (par exemple, le type de données, la portée) pendant le processus de compilation. Lorsque le compilateur rencontre un identificateur dans le code source, il recherche dans la table de symboles pour déterminer sa signification et ses propriétés. Une recherche efficace est cruciale pour les performances du compilateur, car un compilateur typique peut avoir à traiter des millions d'identificateurs dans un### Bioinformatique et biologie computationnelle

En bioinformatique et en biologie computationnelle, les algorithmes de recherche jouent un rôle essentiel dans l'analyse et la compréhension des données biologiques. Voici quelques exemples :

• Alignement de séquences : Des algorithmes comme BLAST (Basic Local Alignment Search Tool) et Smith-Waterman sont utilisés pour rechercher des similitudes entre les séquences d'ADN, d'ARN ou de protéines. Ces algorithmes emploient diverses techniques de recherche pour trouver efficacement les meilleures correspondances entre les séquences, aidant les chercheurs à identifier les relations évolutives, les similitudes fonctionnelles et les mutations potentielles.

• Assemblage de génomes : Les algorithmes de recherche sont utilisés pour localiser les chevauchements entre les courts fragments d'ADN (lectures) générés par les machines de séquençage, permettant la reconstruction de la séquence génomique d'origine. Une recherche efficace est essentielle pour gérer les énormes quantités de données générées dans les projets de séquençage modernes.

• Recherche de gènes et de motifs : Les chercheurs utilisent des algorithmes de recherche pour localiser des motifs spécifiques dans les séquences d'ADN ou de protéines, comme les sites de liaison des facteurs de transcription, les sites d'épissage ou les domaines conservés. Ces motifs peuvent fournir des informations sur la régulation des gènes, la fonction des protéines et la conservation évolutive.

Cybersécurité et cryptographie

Les algorithmes de recherche sont utilisés dans divers aspects de la cybersécurité et de la cryptographie, notamment :

• Détection d'intrusion : Les systèmes de détection d'intrusion sur les réseaux utilisent souvent des algorithmes de recherche comme Aho-Corasick ou Boyer-Moore pour faire correspondre efficacement les modèles de trafic réseau avec une base de données de signatures d'attaques connues. Cela permet la détection et la prévention en temps réel des menaces de sécurité.

• Cassage de mots de passe : Les attaquants peuvent utiliser des algorithmes de recherche pour explorer efficacement de grands dictionnaires de mots de passe ou générer des combinaisons de mots de passe potentiels lors de tentatives de cassage de hachages de mots de passe. Des techniques comme les tables arc-en-ciel et les compromis temps-mémoire s'appuient sur une recherche efficace pour accélérer la récupération des mots de passe.Voici la traduction française du fichier Markdown avec les commentaires traduits, mais le code non traduit :

• Cryptanalyse : En cryptographie, les algorithmes de recherche sont utilisés pour analyser et potentiellement exploiter les faiblesses des systèmes cryptographiques. Par exemple, des algorithmes comme baby-step giant-step ou Pollard's rho sont utilisés pour résoudre le problème du logarithme discret, qui sous-tend la sécurité de certains schémas cryptographiques.

Conclusion

Les algorithmes de recherche et les structures de données sont des outils fondamentaux en informatique, avec des applications couvrant un large éventail de domaines. Des bases de données et de la recherche d'informations au calcul scientifique, à la bioinformatique et à la cybersécurité, la capacité de rechercher et de localiser efficacement les données est cruciale pour résoudre des problèmes complexes et extraire des informations précieuses.

En comprenant les principes et les techniques derrière les algorithmes de recherche, tels que les arbres de recherche binaires, les arbres de recherche équilibrés et les tables de hachage, les développeurs peuvent prendre des décisions éclairées lors de la conception et de la mise en œuvre de systèmes qui s'appuient sur des capacités de recherche efficaces. Le choix de l'algorithme de recherche et de la structure de données appropriés dépend de facteurs tels que la taille et la nature des données, la fréquence des opérations de recherche et les exigences spécifiques de l'application.

Alors que la quantité de données générées et traitées continue de croître de manière exponentielle, l'importance des algorithmes de recherche efficaces ne fera qu'augmenter. Les chercheurs et les praticiens dans divers domaines continueront à s'appuyer sur ces outils fondamentaux pour relever les défis posés par le big data et pour déverrouiller de nouvelles opportunités de découverte et d'innovation.