Algorithme de recherche de sous-chaîne

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.

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 complexité 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.

Les algorithmes de cette section font un lourd pré-traitement sur le texte T ou les motifs multiples 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.

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 la force brute 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.

• Structure de données compressée
• Arbre d'ondelettes

• Simone Faro et Thierry Lecroq, « The exact online string matching problem: A review of the most recent results », ACM Computing Surveys, vol. 45, n^o 2,‎ février 2013, article n^o 13 (42 p.) (DOI 10.1145/2431211.2431212).
• Simone Faro et Thierry Lecroq, « The Exact String Matching Problem: a Comprehensive Experimental Evaluation », Arxiv,‎ décembre 2010 (arXiv 1012.2547). — Version antérieure, et libre, de l'article précédent.

• (en) Algorithmes de recherche de chaine
• (en) StringSearch – high-performance pattern matching algorithms in Java – implémentations des algorithmes BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita et Shift-Or en Java

• Portail de l'informatique théorique