Algorithme de recherche de chaîne

En informatique , les algorithmes de recherche de chaînes , parfois appelés algorithmes de correspondance de chaînes , sont une classe importante d' algorithmes de chaînes qui tentent de trouver un endroit où une ou plusieurs chaînes (également appelées motifs) se trouvent dans une chaîne ou un texte plus grand.

Un exemple basique de recherche de chaîne est lorsque le motif et le texte recherché sont des tableaux d'éléments d'un alphabet ( ensemble fini ) Σ. Σ peut être un alphabet de langage humain, par exemple, les lettres A à Z et d'autres applications peuvent utiliser un alphabet binaire (Σ = {0,1}) ou un alphabet ADN (Σ = {A,C,G,T}) en bioinformatique .

En pratique, la méthode de recherche de chaîne réalisable peut être affectée par le codage de la chaîne. En particulier, si un codage à largeur variable est utilisé, il peut être plus lent de trouver le N ème caractère, ce qui peut nécessiter un temps proportionnel à N . Cela peut ralentir considérablement certains algorithmes de recherche. L'une des nombreuses solutions possibles consiste à rechercher la séquence d'unités de code à la place, mais cela peut produire de fausses correspondances à moins que le codage ne soit spécifiquement conçu pour l'éviter.

Le cas le plus basique de recherche de chaîne implique une chaîne (souvent très longue), parfois appelée haystack , et une chaîne (souvent très courte), parfois appelée needle . L'objectif est de trouver une ou plusieurs occurrences de l'aiguille dans la botte de foin. Par exemple, on peut rechercher to dans :

Certains livres sont à goûter, d’autres à avaler, et quelques uns à mâcher et à digérer. 

On pourrait demander la première occurrence de « to », qui est le quatrième mot ; ou toutes les occurrences, qui sont au nombre de 3 ; ou la dernière, qui est le cinquième mot à partir de la fin.

Cependant, très souvent, diverses contraintes sont ajoutées. Par exemple, on peut vouloir faire correspondre le mot « aiguille » uniquement lorsqu'il est composé d'un (ou plusieurs) mot(s) complet(s), peut-être défini comme n'ayant pas d'autres lettres immédiatement adjacentes de chaque côté. Dans ce cas, une recherche de « hew » ou « low » devrait échouer pour la phrase d'exemple ci-dessus, même si ces chaînes littérales apparaissent.

Un autre exemple courant concerne la « normalisation ». Pour de nombreuses raisons, une recherche d'une expression telle que « être » devrait réussir même dans les endroits où il y a quelque chose d'autre entre le « être » et le « être » :

• Plus d'un espace
• Autres caractères « d'espacement » tels que les tabulations, les espaces insécables, les sauts de ligne, etc.
• Moins fréquemment, un trait d'union ou un trait d'union conditionnel
• Dans les textes structurés, les balises ou même des éléments arbitrairement grands mais « entre parenthèses » tels que les notes de bas de page, les numéros de liste ou autres marqueurs, les images intégrées, etc.

De nombreux systèmes de symboles incluent des caractères qui sont synonymes (au moins pour certaines raisons) :

• Les alphabets latins distinguent les minuscules des majuscules, mais pour de nombreuses utilisations, la recherche de chaîne est censée ignorer cette distinction.
• De nombreuses langues incluent des ligatures , où un caractère composé est équivalent à deux ou plusieurs autres caractères.
• De nombreux systèmes d'écriture utilisent des signes diacritiques tels que des accents ou des points-voyelles , qui peuvent varier dans leur utilisation ou avoir une importance variable dans la correspondance.
• Les séquences d'ADN peuvent impliquer des segments non codants qui peuvent être ignorés à certaines fins, ou des polymorphismes qui n'entraînent aucun changement dans les protéines codées, ce qui peut ne pas être considéré comme une véritable différence à d'autres fins.
• Certaines langues ont des règles selon lesquelles un caractère ou une forme de caractère différent doit être utilisé au début, au milieu ou à la fin des mots.

Enfin, pour les chaînes qui représentent le langage naturel, des aspects du langage lui-même entrent en jeu. Par exemple, on peut souhaiter trouver toutes les occurrences d'un « mot » malgré ses orthographes, préfixes ou suffixes alternatifs, etc.

Un autre type de recherche plus complexe est la recherche par expression régulière , où l'utilisateur construit un modèle de caractères ou d'autres symboles, et toute correspondance avec le modèle doit satisfaire la recherche. Par exemple, pour attraper à la fois le mot anglais américain "color" et son équivalent britannique "colour", au lieu de rechercher deux chaînes littérales différentes, on peut utiliser une expression régulière telle que :

couleur 

où le « ? » rend conventionnellement le caractère précédent (« u ») facultatif.

Cet article traite principalement des algorithmes pour les types de recherche de chaînes les plus simples.

Un problème similaire introduit dans le domaine de la bioinformatique et de la génomique est la correspondance exacte maximale (MEM). Étant donné deux chaînes, les MEM sont des sous-chaînes communes qui ne peuvent pas être étendues à gauche ou à droite sans provoquer une non-concordance.

Une façon simple et inefficace de voir où une chaîne apparaît dans une autre est de vérifier à chaque index, un par un. Tout d'abord, nous regardons s'il existe une copie de l'aiguille commençant au premier caractère de la botte de foin ; si ce n'est pas le cas, nous regardons s'il existe une copie de l'aiguille commençant au deuxième caractère de la botte de foin, et ainsi de suite. Dans le cas normal, nous n'avons qu'à regarder un ou deux caractères pour chaque mauvaise position pour voir qu'il s'agit d'une mauvaise position, donc dans le cas moyen, cela prend O ( n + m ) étapes, où n est la longueur de la botte de foin et m est la longueur de l'aiguille ; mais dans le pire des cas, la recherche d'une chaîne comme "aaaab" dans une chaîne comme "aaaaaaaaab", cela prend O ( nm )

Dans cette approche, le retour en arrière est évité en construisant un automate fini déterministe (DFA) qui reconnaît une chaîne de recherche stockée. Ceux-ci sont coûteux à construire (ils sont généralement créés à l'aide de la construction Powerset ) mais sont très rapides à utiliser. Par exemple, l' DFA illustré à droite reconnaît le mot « MOMMY ». Cette approche est fréquemment généralisée dans la pratique pour rechercher des expressions régulières arbitraires .

Knuth–Morris–Pratt calcule un DFA qui reconnaît les entrées avec la chaîne à rechercher comme suffixe, Boyer–Moore commence la recherche à partir de la fin de l'aiguille, de sorte qu'il peut généralement avancer d'une longueur d'aiguille entière à chaque étape. Baeza–Yates garde une trace de la présence ou non des j caractères précédents comme préfixe de la chaîne de recherche, et est donc adaptable à la recherche de chaînes floues . L' algorithme bitap est une application de l'approche de Baeza–Yates.

Les algorithmes de recherche plus rapides prétraitent le texte. Après avoir créé un index de sous-chaîne , par exemple un arbre de suffixes ou un tableau de suffixes , les occurrences d'un motif peuvent être trouvées rapidement. Par exemple, un arbre de suffixes peut être construit dans le temps, et toutes les occurrences d'un motif peuvent être trouvées dans le temps en supposant que l'alphabet a une taille constante et que tous les nœuds internes de l'arbre de suffixes savent quelles feuilles se trouvent en dessous d'eux. Ce dernier peut être accompli en exécutant un algorithme DFS à partir de la racine de l'arbre de suffixes.

Certaines méthodes de recherche, comme la recherche de trigrammes , visent à trouver un score de « proximité » entre la chaîne de recherche et le texte plutôt qu'un score de « correspondance/non-correspondance ». On les appelle parfois recherches « floues » .

Les différents algorithmes peuvent être classés en fonction du nombre de modèles que chacun utilise.

Dans la compilation suivante, m est la longueur du motif, n la longueur du texte consultable et k = |Σ| est la taille de l'alphabet.

1. ^ Les temps asymptotiques sont exprimés en utilisant les notations O, Ω et Θ .

2. ^ Utilisé pour implémenter les fonctions de recherche memmem et strstr dans les bibliothèques standard C glibc et musl .

3. ^ Peut être étendu pour gérer la correspondance approximative de chaînes et des ensembles (potentiellement infinis) de motifs représentés comme des langages réguliers .

L' algorithme de recherche de chaînes de Boyer-Moore a été la référence standard pour la littérature pratique sur la recherche de chaînes.

Dans la compilation suivante, M est la longueur du motif le plus long, m sa longueur totale, n la longueur du texte consultable, o le nombre d'occurrences.

Naturellement, les modèles ne peuvent pas être énumérés de manière finie dans ce cas. Ils sont généralement représentés par une grammaire régulière ou une expression régulière .

D'autres approches de classification sont possibles. L'une des plus courantes utilise le prétraitement comme critère principal.

Un autre classe les algorithmes en fonction de leur stratégie de correspondance :

• Faites correspondre le préfixe en premier (Knuth–Morris–Pratt, Shift-And, Aho–Corasick)
• Faites correspondre le suffixe en premier (Boyer–Moore et variantes, Commentz-Walter)
• Faites correspondre d’abord le meilleur facteur (BNDM, BOM, Set-BOM)
• Autre stratégie (Naïve, Rabin-Karp, Vectorisée)