Algorithme de recherche de sous-chaîne

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un algorithme de recherche de sous-chaine est un type d'algorithme de recherche qui a pour objectif de trouver une chaîne de caractères (le pattern P) à l'intérieur d'une autre chaîne (le texte T).

Texte[modifier | modifier le code]

Il existe beaucoup de formats de textes dans lesquels chercher, et en conséquence tous les algorithmes sont susceptibles de connaître de fortes variations suivant le texte T fourni.

Par exemple, la taille du texte peut varier de la simple ligne à la concaténation de milliers de livres. L'encodage du texte peut également avoir une influence dramatique sur la performance d'un algorithme. Notamment, des alphabets de type ADN, ASCII ou Unicode peuvent exclure d'office l'utilisation d'un algorithme particulier.

Algorithme naïf/Bruteforce[modifier | modifier le code]

L'idée est de réaliser une comparaison caractère après caractère de la chaîne initiale et de la chaîne recherchée. On parcourt les caractères de la chaîne initiale tant qu'ils sont différents du premier caractère de la chaîne à trouver. Dès qu'on trouve un caractère identique, on parcourt les caractères suivants tant qu'ils correspondent. Si un caractère diffère alors qu'on n'a pas atteint la fin de la chaîne recherchée, alors on reprend la recherche du premier caractère identique, à partir du caractère suivant dans la chaîne initiale. Si tous les caractères correspondent, on retourne la position du premier caractère de la chaîne trouvée dans la chaîne initiale. Enfin, si aucune occurrence de la chaîne recherchée n'apparaît dans la chaîne initiale, l'algorithme se doit de le signaler, en retournant une valeur négative par exemple.

Sur de petits textes T cet algorithme est efficace. Cependant, la complexite algorithmique étant Θ(|T|*|P|) il est rapidement dépassé par des algorithmes qui vont utiliser des particularités de P ou T avant de faire la recherche, ce que l'on appelle le pré-traitement.

Recherche unique[modifier | modifier le code]

Knuth-Morris-Pratt[modifier | modifier le code]

Article détaillé - Algorithme de Knuth-Morris-Pratt

Boyer-Moore et variantes[modifier | modifier le code]

Article détaillé - Algorithme de Boyer-Moore

Article détaillé - Algorithme de Boyer-Moore-Horspool

Article détaillé - Algorithme de Raita

Shitf-Or/Bitap/Baeza-Yates-Gonnet[modifier | modifier le code]

Article détaillé - Algorithme de Baeza-Yates-Gonnet

Z-Algorithm[modifier | modifier le code]

Article détaillé - Algorithme Z

Recherches multiples[modifier | modifier le code]

Les algorithmes de cette section font un lourd pré-traitement sur le texte T ou les multiples patterns P_i d'entrée afin de comparer les multiples P_i à une portion de texte une seule fois. Quelques exemples classiques sont la détection de plagiat ou la comparaison d'un fichier suspect à des fragments de virus.

Rabin-Karp[modifier | modifier le code]

Article détaillé - Algorithme de Rabin-Karp.

Aho-Corasick[modifier | modifier le code]

Article détaillé - Algorithme d'Aho-Corasick.

Combinaisons et adaptations[modifier | modifier le code]

Les algorithmes sus-cités sont académiques. En pratique ils sont fortement adaptés pour répondre aux besoins sur le terrain.

Certaines bibliothèques combinent de multiples algorithmes pour rester dans le meilleur cas de résolution possible. Par exemple stringlib/fastsearch[1] en Python utilise bruteforce pour P de longueur 1 et une combinaison de Boyer-Moore-Horspool et Sunday et des filtres de Bloom pour remplacer la table de saut.

Certains programmes tel grep offrent une myriade d'optimisations[2] et sacrifient leur worst-case au best-case[3], en pariant sur le fait que P et T ont une faible probabilité d'engendrer un cas pathologique.

Enfin, les processeurs modernes offrent des jeux d'instructions SIMD particulièrement efficaces tel SSE. Certaines implémentations de libc strstr utilisent ces instructions pour accélérer la recherche.

Notes et références[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]