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). 
  
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 C: 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

Leave a Reply