Recherche d'occurrences d'une chaîne de caractères dans une autre : Cours Algorithme recherche
- L'algorithme de Knuth-Morris-Pratt.
- L'algorithme de Boyer et Moore.
1 Recherche d'occurrences d'une chaîne de caractères dans une autre
Si l’on considère une chaîne longue le texte dans un tableau T[1..n] et une chaîne courte le cible dans un tableau C[1..m] ; vérifier qu'une occurrence de C commence à T[i] prend un temps m. Donc, un algorithme simple en temps se retrouve avec la complexité O(mn).
On lit le tableau de texte T de gauche à droite. A chaque moment, on stocke la (taille de la) partie au début de C qui correspond à la partie de T qu'on vient de lire. Cette taille peut être mise à jour sans retour en arrière.
On créé un état pour chaque lettre de C, mettons par exemple C=C1,...,Cm . Considérons un état Ci : on a déjà lu C1,...,Ci. On continue d’avancer si la prochaine lettre x est la bonne Ci+1 (sauf si on a trouvé un C complet). Sinon on recule. Problème : De combien doit-on reculer lorsqu’on est à Cj ; où C1,...,Cj est le plus long préfixe de C qui est aussi suffixe de C1,...,Ci x.
Le pré-calcul (du plus long préfixe de C qui est aussi suffixe de C1,...,Ci) peut se faire facilement en temps O(m2) mais ce n'est pas optimal :
Comment faire mieux qu'un algorithme qui considère chaque lettre une seule fois? C’est impossible (dans certains cas au moins). Mais souvent, si C est de taille moyenne, on peut exclure des sections de T sans les regarder !
Pour trouver les positions où une occurrence de C pourrait terminer, il faut :
La récupération après un échec et le redémarrage après une réussite quand on veut trouver toutes les occurrences peut se faire de la manière suivante :
-------------------------------------------------------------------------------------------------------
Précédent : Fusion et Recherche
Suivant : Allocation et Libération d'espace
- L'algorithme de Boyer et Moore.
1 Recherche d'occurrences d'une chaîne de caractères dans une autre
Si l’on considère une chaîne longue le texte dans un tableau T[1..n] et une chaîne courte le cible dans un tableau C[1..m] ; vérifier qu'une occurrence de C commence à T[i] prend un temps m. Donc, un algorithme simple en temps se retrouve avec la complexité O(mn).
Comment faire mieux ?
1.1 L'algorithme de Knuth-Morris-Pratt
On lit le tableau de texte T de gauche à droite. A chaque moment, on stocke la (taille de la) partie au début de C qui correspond à la partie de T qu'on vient de lire. Cette taille peut être mise à jour sans retour en arrière.
Il faut savoir, pour chaque préfixe de C, quel est son plus long suffixe qui est aussi un préfixe de C.
1.1.1 Un automate qui effectue la recherche du suffixe-préfixe
On créé un état pour chaque lettre de C, mettons par exemple C=C1,...,Cm . Considérons un état Ci : on a déjà lu C1,...,Ci. On continue d’avancer si la prochaine lettre x est la bonne Ci+1 (sauf si on a trouvé un C complet). Sinon on recule. Problème : De combien doit-on reculer lorsqu’on est à Cj ; où C1,...,Cj est le plus long préfixe de C qui est aussi suffixe de C1,...,Ci x.
1.1.2 Le pré-calcul
Le pré-calcul (du plus long préfixe de C qui est aussi suffixe de C1,...,Ci) peut se faire facilement en temps O(m2) mais ce n'est pas optimal :
- Une récurrence pour Si, la longueur de ce préfixe-suffixe si Ci+1 = CSi+1, Si+1 = Si+1, sinon, si Ci+1=CSSi+1, Si+1=SSi+1, etc.
- Le calcul par programmation dynamique
- Le temps du pré-calcul : O(m)
- Le temps total O(m+n)
1.2 L'algorithme de Boyer et Moore: l'idée
Comment faire mieux qu'un algorithme qui considère chaque lettre une seule fois? C’est impossible (dans certains cas au moins). Mais souvent, si C est de taille moyenne, on peut exclure des sections de T sans les regarder !
exemple trivial: si C est « aaaaaaaaaa », et T ne contient pas de a, on peut trouver la solution en ne regardant que chaque 10-ème lettre de T.
1.2.1 L'algorithme de Boyer et Moore: un peu de détail
Pour trouver les positions où une occurrence de C pourrait terminer, il faut :
- Regarder d'abord la lettre T[m]
- Si cette lettre n'a pas d'occurrences en C, avancer par m
- Si sa dernière occurrence en C est à position j (j<m), avancer par m-j
- Si sa dernière occurrence est à C[m], chercher une occurrence complète (de droite à gauche)
1.2.2 Récupération après un échec
La récupération après un échec et le redémarrage après une réussite quand on veut trouver toutes les occurrences peut se faire de la manière suivante :
- Système pareil à celui de Knuth-Morris-Pratt d'utiliser l'information obtenue pendant la partie réussie de la recherche.
- Donne temps « moyen » O(n/m) si on accepte l'idée que les deux chaînes sont aléatoires.
-------------------------------------------------------------------------------------------------------
Précédent : Fusion et Recherche
Suivant : Allocation et Libération d'espace
Article plus récent Article plus ancien
