Recherche de chaînes de caractères
La recherche de chaînes de caractères identifie toutes les occurrences d'un motif au sein d'un texte ; les algorithmes classiques prétraitent le motif pour éviter les comparaisons redondantes et atteindre un temps de recherche linéaire ou sous-linéaire.
Definition
La recherche de chaînes de caractères est le problème qui consiste à trouver toutes les positions dans un texte où une chaîne de caractères (motif) donnée apparaît ; un algorithme de recherche exacte de chaînes de caractères signale chaque décalage auquel le motif s'aligne identiquement avec une sous-chaîne du texte.
Scope
Ce sujet aborde les algorithmes de recherche exacte de motif unique — la méthode naïve, Knuth-Morris-Pratt, Boyer-Moore et Rabin-Karp basé sur le hachage — ainsi que le prétraitement (fonctions d'échec, tables de décalage, hachages glissants) qui les rend efficaces, et l'extension à la recherche de motifs multiples via l'automate d'Aho-Corasick. La recherche approximative et la recherche basée sur des index sont traitées dans des sujets connexes.
Core questions
- Pourquoi la recherche naïve prend-elle un temps proportionnel au produit des longueurs du motif et du texte ?
- Comment le prétraitement du motif permet-il d'éviter de réexaminer les caractères du texte ?
- Comment fonctionnent la fonction d'échec de Knuth-Morris-Pratt et les règles de décalage de Boyer-Moore ?
- Comment Rabin-Karp utilise-t-il le hachage pour tester rapidement les alignements ?
- Comment la recherche est-elle étendue à de nombreux motifs simultanément ?
Key concepts
- recherche naïve
- algorithme de Knuth-Morris-Pratt
- fonction d'échec
- algorithme de Boyer-Moore
- règles du mauvais caractère et du bon suffixe
- algorithme de Rabin-Karp
- hachage glissant
- automate d'Aho-Corasick
Key theories
- Fonction d'échec de Knuth-Morris-Pratt
- En prétraitant, pour chaque préfixe de motif, le plus long préfixe propre qui est aussi un suffixe, l'algorithme de Knuth-Morris-Pratt décale intelligemment le motif après une non-correspondance et ne réexamine jamais les caractères du texte, permettant une recherche en temps linéaire.
- Balayage de droite à gauche de Boyer-Moore
- Boyer-Moore compare le motif en partant de son dernier caractère vers l'arrière et utilise les règles du mauvais caractère et du bon suffixe pour sauter de grandes portions du texte, atteignant une performance sous-linéaire en moyenne sur des entrées typiques.
Clinical relevance
La recherche de chaînes de caractères est à la base d'outils et d'infrastructures quotidiens : la recherche dans les éditeurs de texte et les utilitaires en ligne de commande, le filtrage de contenu et l'analyse de signatures de détection d'intrusion, la détection de plagiat et la localisation de motifs dans les séquences biologiques. La recherche de motifs multiples permet d'étendre ces capacités à des dictionnaires de nombreux motifs simultanément.
History
L'algorithme de Knuth-Morris-Pratt (publié en 1977, développé antérieurement) a fourni le premier algorithme de recherche exacte en temps linéaire largement connu, et Boyer et Moore (1977) ont introduit la recherche sous-linéaire en moyenne la même année. L'approche de hachage de Rabin et Karp et l'automate multi-motifs d'Aho-Corasick (1975) ont encore élargi le domaine.
Key figures
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Michael Rabin
- Richard Karp
Related topics
Seminal works
- knuth1977
- boyer1977
- cormen2009
Frequently asked questions
- Quel algorithme de recherche exacte de chaînes de caractères est le plus rapide ?
- Cela dépend de l'entrée. Knuth-Morris-Pratt garantit un temps linéaire dans le pire des cas ; Boyer-Moore est souvent le plus rapide en pratique sur du texte naturel car il saute des caractères et s'exécute en temps sous-linéaire en moyenne ; Rabin-Karp excelle lors de la recherche de nombreux motifs ou de comparaisons d'empreintes (fingerprints). Il n'y a pas de gagnant universel unique.
- Comment Rabin-Karp évite-t-il de comparer chaque caractère à chaque position ?
- Il hache le motif et chaque fenêtre de texte de même longueur en utilisant un hachage glissant qui se met à jour en temps constant à mesure que la fenêtre glisse. Ce n'est que lorsque les hachages correspondent qu'il vérifie les caractères réels ; ainsi, la plupart des positions non-correspondantes sont rejetées par une seule comparaison peu coûteuse.