Algorithmes sur les chaînes de caractères
Les algorithmes sur les chaînes de caractères traitent des séquences de symboles — texte, ADN ou autres données linéaires — afin de trouver des motifs, d'indexer de grands textes pour une recherche rapide et d'aligner des séquences par similarité.
Definition
Les algorithmes sur les chaînes de caractères sont des procédures et des structures de données qui opèrent sur des chaînes — des séquences finies de caractères tirées d'un alphabet — pour résoudre des problèmes tels que la localisation de motifs, l'indexation pour une recherche rapide, et la mesure ou l'alignement de la similarité entre séquences.
Scope
Ce domaine couvre les algorithmes et les structures de données spécialisés pour les chaînes de caractères : la recherche de motifs exacte et approximative, les structures d'index (tries, arbres de suffixes et tableaux de suffixes) qui prétraitent le texte pour des requêtes répétées, et les méthodes d'alignement de séquences pour comparer des chaînes. Il est lié à la programmation dynamique (alignement), aux structures de données (arbres et tableaux) et aux applications en biologie computationnelle, en recherche d'information textuelle et en traitement automatique du langage naturel.
Sub-topics
Core questions
- Comment un motif peut-il être localisé dans un texte plus rapidement qu'une comparaison naïve caractère par caractère ?
- Comment un texte volumineux est-il prétraité pour que de nombreuses requêtes ultérieures soient rapides ?
- Comment la similarité entre deux chaînes est-elle définie et calculée ?
- Comment la taille de l'alphabet et la longueur des chaînes affectent-elles l'efficacité des algorithmes sur les chaînes ?
- Comment les méthodes de correspondance exacte s'étendent-elles à la correspondance approximative ou à la recherche de motifs multiples ?
Key concepts
- alphabet et chaîne de caractères
- recherche exacte de motifs
- Knuth-Morris-Pratt et Boyer-Moore
- tries
- arbres de suffixes et tableaux de suffixes
- distance d'édition
- alignement de séquences
- correspondance approximative
Key theories
- Recherche exacte de motifs en temps linéaire
- En prétraitant le motif pour exploiter les informations des correspondances partielles, des algorithmes tels que Knuth-Morris-Pratt et Boyer-Moore trouvent toutes les occurrences d'un motif en un temps linéaire par rapport à la longueur du texte, évitant ainsi le coût quadratique de la correspondance naïve.
- Structures d'index pour le texte
- Les arbres de suffixes et les tableaux de suffixes prétraitent un texte de manière à ce que les requêtes de motifs arbitraires, les répétitions et les questions de plus longue sous-chaîne commune puissent être résolues rapidement, échangeant le coût de construction contre une recherche répétée rapide.
Clinical relevance
Les algorithmes sur les chaînes de caractères sont fondamentaux pour la recherche textuelle et la bioinformatique : la recherche de motifs alimente les utilitaires de recherche, les éditeurs de texte et la détection d'intrusion ; les structures de suffixes indexent les moteurs de recherche et les bases de données génomiques ; et l'alignement de séquences est central pour comparer les séquences d'ADN, d'ARN et de protéines en biologie moléculaire.
History
La recherche efficace de motifs dans les chaînes de caractères a émergé dans les années 1970 avec les algorithmes de Knuth-Morris-Pratt (1977) et Boyer-Moore (1977). Les arbres de suffixes (Weiner, 1973 ; McCreight, 1976 ; Ukkonen, 1995) et plus tard les tableaux de suffixes (Manber et Myers, 1990) ont permis une indexation puissante, et le domaine s'est rapidement développé grâce à la biologie computationnelle, comme l'a présenté l'ouvrage de Gusfield en 1997.
Key figures
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Dan Gusfield
Related topics
Seminal works
- knuth1977
- gusfield1997
- cormen2009
Frequently asked questions
- Pourquoi prétraiter le motif ou le texte au lieu de chercher directement ?
- La correspondance naïve peut prendre un temps proportionnel au produit des longueurs du motif et du texte. Le prétraitement du motif (comme dans Knuth-Morris-Pratt) permet une recherche en temps linéaire, et le prétraitement du texte en un index (arbre de suffixes ou tableau) permet à de nombreuses requêtes ultérieures de s'exécuter beaucoup plus rapidement, ce qui est avantageux lorsque le même texte est recherché de manière répétée.
- Comment les algorithmes sur les chaînes sont-ils utilisés en biologie ?
- L'ADN, l'ARN et les protéines sont naturellement représentés comme des chaînes de caractères ; ainsi, la recherche de motifs localise les motifs, les structures de suffixes indexent les génomes pour une consultation rapide, et les algorithmes d'alignement de séquences quantifient la similarité entre les séquences pour inférer les relations évolutives et la fonction.