# Algorithme de recherche de sous-chaîne

En informatique, plus précisément en algorithmique du texte, le problème de recherche de sous-chaîne (en anglais string-matching problem) consiste à trouver une chaîne de caractères dans un texte. Le problème de recherche d'une sous-chaîne intervient dans beaucoup d'applications. Par exemple, dans un logiciel de traitement de texte, ou dans un navigateur Web, l'utilisateur peut rechercher une chaîne de caractères dans un document, ou une page Internet, en vue de remplacer un mot par un autre (par exemple, remplacer toues les occurrences du mot "rêve" par le mot "songe").
Il existe plusieurs algorithmes pour rechercher une chaîne dans un texte, comme l'algorithme naïf ou force brute (cf. p. 35 dans), l'algorithme de Boyer-Moore ou encore l'algorithme de Knuth-Morris-Pratt. Ce sont des algorithmes de recherche.
La plupart des langages de programmation proposent des fonctions pour effectuer une telle recherche ; par exemple en Python, on écrit chaine in texte pour tester si la chaîne apparaît dans le texte. Par extension, on peut considérer aussi le problème de trouver toutes les occurrences d'un mot, ou alors de compter le nombre d'occurrences d'une chaîne dans un texte.

## Algorithme naïf pour la recherche d'un motif

L'algorithme naïf est présenté dans plusieurs livres d'algorithmique$^,$ ainsi que dans des livres spécialisés en algorithmique du texte.

### Principe

L'algorithme naïf fait glisser le motif le long du texte en le déplaçant d'une lettre à chaque fois jusqu'à avoir trouvé le motif. Au début, le motif est aligné avec le début du texte. Par exemple si l'on cherche le motif longs des dans le texte les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone on démarre avec l'alignement suivant :
On compare les caractères du motif avec le début du texte. Le premier caractère est l. Mais les deuxièmes caractères différent. On déplace alors le motif d'une lettre vers la droite :
On compare les caractères du motif et le texte à partir du second caractère. Les premiers caractères e et l sont différents. On continue donc à glisser le motif.
Au 14e alignement, les caractères coïncident :
Comme tous les caractères correspondent, on renvoie la position du premier caractère de la chaîne trouvée dans la chaîne initiale. Si jamais nous avons glissé le motif jusqu'à la fin du texte, mais que l'alignement ne coïncidait jamais, alors l'algorithme échoue. Dans certaines implémentations, l'algorithme retourne -1.

### Pseudo-code

On note |m| le nombre de caractères dans m. On suppose que les indices dans les chaînes de caractères commencent à 0. Voici le pseudo-code de l'algorithme naïf :

### Analyse

La complexité temporelle est Θ(|texte|*|m|). Plus précisément, l'algorithme effectue |m|(|texte| - |m| - 1) comparaisons dans le pire cas. Ce pire cas arrive par exemple si l'on cherche le motif aa..ab dans un texte aa..aa, comme :
En effet, à chaque position de la fenêtre glissante du motif, on réalise |m| comparaisons de caractères et il y a (|texte| - |m| - 1) positions différentes. Dans le meilleur des cas, on ne fait qu'une seule comparaison pour chaque position de fenêtre et dans ce cas on fait |texte| - |m| - 1 comparaisons.
Toutefois, pour un algorithme de plus de deux lettres, et si la distribution sur les lettres est indépendante et uniforme, alors le nombre moyen de comparaisons de caractères pour rechercher un motif avec l'algorithme naïf dans un texte est au plus 2|texte| (voir Proposition 1.1 dans).

## Algorithmes pour rechercher un motif

Il existe plusieurs algorithmes, souvent meilleurs que l'algorithme naïf. Souvent, ces algorithmes vont utiliser des particularités du motif ou du texte avant de faire la recherche, ce que l'on appelle le pré-traitement. Beaucoup d'algorithmes utilisent la même idée de fenêtre glissante du motif dans le texte que l'algorithme naïf. Le schéma général de ces algorithmes sont :
Dans l'algorithme naïf, on décale le motif de une case vers la droite à chaque (i augmente de 1). Dans les algorithmes qui suivent on augmente i plus rapidement. Ce décalage de la fenêtre glissante dépend du motif et du texte. Souvent on peut faire un prétraitement sur le motif pour savoir de combien décaler le motif.

### Tableau récapitulatif

| Algorithme | Complexité temporelle du prétraitement | Complexité temporelle de la recherche | Espace utilisé |
| Algorithme naïf | Pas de prétraitement | Θ(|texte|+|motif|) en moyenne, O(|motif|×|texte|) | |
| Algorithme de Rabin–Karp | Θ(|motif|) | Θ(|motif|) en moyenne, O(|motif|×|texte|) au pire | O(1) |
| Algorithme de Knuth–Morris–Pratt | Θ(|motif|) | Θ(|texte|) | Θ(|motif|) |
| Algorithme de Boyer–Moore | Θ(|motif| + |alphabet|) | Ω(|texte|/|motif|) au mieux, O(|motif|×|texte|) au pire | Θ(|alphabet|) |
| Two-way algorithm (en) | Θ(|motif|) | O(|texte|) | O(log(|motif|)) |
| Backward Non-Deterministic DAWG (en) Matching (BNDM) | O(|motif|) | Ω(|texte|/|motif|) au mieux, O(|motif|×|texte|) au pire | |
| Backward Oracle Matching (BOM) | O(|motif|) | O(|motif|×|texte|) | |

### Rabin-Karp

Article détaillé - Algorithme de Rabin-Karp.
L'algorithme de Rabin-Karp améliore l'algorithme naïf. Plus précisément, il améliore le test de comparaison du motif avec la portion du texte en utilisant une fonction de hachage.

### Boyer-Moore et variantes

Article détaillé - Algorithme de Boyer-Moore
Article détaillé - Algorithme de Boyer-Moore-Horspool
Article détaillé - Algorithme de Raita
Dans l'algorithme de Boyer-Moore la comparaison m = texte[i, i+|m|-1] s'effectue en faisant des comparaisons de caractères de droite vers la gauche (alors qu'a priori, dans l'algorithme naïf, on effectue des comparaisons de gauche à droite). Puis on augmente la valeur de i de la manière suivante. Soit j l'indice où il y a la première différence, c'est-à-dire tel que j le plus grand avec m[j] différent de t[i+j]. On augmente alors i de j - k, où k est le grand entier tel qu'avec k dans [0, ... j-1] et m[k] = t[i+j] si un tel k existe. S'il n'y a pas de tel k, alors on augmente k de j+1.
Considérons l'exemple où l'on cherche le motif m qui estabracadabra. Supposons que l'on teste l'égalité entre le motif m et texte[i, i+|m|-1]. Pour l'instant, nous avons constaté égalité des 5 dernières lettres de m et texte[i, i+10], à savoir dabra. Par contre, on constate une différence dans la 6e lettre en partant de la fin : il y a un b dans le texte alors qu'il y a un a dans le motif.
L'algorithme naïf aurait décaler le motif juste d'une case (incrémenter i de un). En image :
Regardons dans les incrémentations suivantes, la prochaine qui vient placer un b sous le b du texte :
L'algorithme de Boyer-Moore effectue ce décalage de 4 immédiatement, en ayant effectué un prétraitement sur le motif.

### Knuth-Morris-Pratt

Article détaillé - Algorithme de Knuth-Morris-Pratt
Dans l'algorithme de Knuth-Morris-Pratt, le motif et le texte sont comparés lettre à lettre de gauche à droite. En cas de différence de lettres, on considère le début du motif qui coïncide avec la portion de texte. On décale le motif selon le plus long bord de ce début (préfixe propre du début aussi suffixe de ce début). L'algorithme reprend de là et on ne revient jamais en arrière dans le texte.

### Shitf-Or/Bitap/Baeza-Yates-Gonnet

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

### Z-Algorithm

Article détaillé - Algorithme Z

## Recherche de plusieurs motifs

Les algorithmes de cette section font un 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.

### Rabin-Karp

Article détaillé - Algorithme de Rabin-Karp.
L'algorithme de Rabin-Karp se généralise à la recherche de plusieurs motifs en utilisant un filtre de Bloom.

### Aho-Corasick

Article détaillé - Algorithme d'Aho-Corasick.
L'algorithme d'Aho-Corasick généralise l'algorithme de Knuth-Morris-Pratt à la recherche simultanée de plusieurs motifs (voir p. 367, Section 10.3 dans$^,$). Pour l'algorithme d'Aho-Corasick la fonction préfixe devient arborescente et est défini sur un trie.

## Implémentations

La Glibc implémente l'algorithme Two-way. Le compilateur gcc propose l'algorithme naïf pour les systèmes qui ne proposent pas d'implémentation pour strstr.
L'outil grep implémente l'algorithme de Boyer-Moore.

## Discussions
### Texte

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

### Combinaisons et adaptations

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 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 et sacrifient leur worst-case au best-case, 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.