Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Page 74 C++, structures de données et la STL 3.6 Algorithmes de recherche dans

Page 74 C++, structures de données et la STL 3.6 Algorithmes de recherche dans les chaînes de caractères Quand on utilise des chaînes de caractères, on a souvent besoin d'examiner une chaîne pour y rechercher une sous-chaîne donnée. Une telle opération de recherche existe dans tous les logiciels de traitement de textes, ainsi d’ailleurs que dans toutes les réalisations du type de données abstrait chaîne de caractères. Lorsqu'on manipule de longs textes, on doit réaliser cette opération aussi efficacement que possible. Nous nous concentrerons ici sur quatre algorithmes classiques de recherche de patron1 (en anglais pattern-matching), qui examinent une chaîne pour y trouver une sous-chaîne donnée. Recherche simple La réalisation de l'opération find, pour prendre une des opérations de recherche associées au type string, permet d’illustrer l'algorithme de recherche de patron le plus simple. La figure 3.6 illustre cet algorithme pour la recherche de la sous-chaîne “abc” dans la chaîne “ababc”; le caractère “|” marque les positions dans le patron et dans la chaîne où la comparaison est effectuée. On commence au début de la chaîne et de la sous-chaîne (ou patron) et on compare les premiers caractères. Ils correspondent; on compare alors les deuxièmes caractères, ils correspondent aussi. On compare donc les troisièmes caractères; comme ils ne correspondent pas (indiqué par un astérisque), on revient au deuxième caractère de la chaîne et au premier caractère du patron et on répète le processus. | | | | | | | ababc ababc ababc ababc ababc ababc ababc Chaîne de caractères abc abc abc abc abc abc abc Patron |1 |2 |3* |4* |5 |6 |7 Comparaisons Figure 3.6 Recherche de patron Cet algorithme est simple et facile à programmer. La fonction RechercheSimple ci-dessous illustre cet algorithme de façon plus détaillée : int RechercheSimple(const string& Patron, const string& Texte) { int carac, pat, longueurPatron, longueurTexte; longueurPatron = Patron.size(); longueurTexte = Texte.size(); pat = 0; if(longueurPatron <= longueurTexte){ carac = 0; do{ if(Patron[pat] == Texte[carac]){ pat++; carac++; } else{ carac = carac - pat + 1; // avance dans Texte pat = 0; } //if } while(pat < longueurPatron && carac < longueurTexte); } //if; if((pat >= longueurPatron)) // trouvé return carac - longueurPatron; else return -1; } //RechercheSimple; 1 Sous-produit d’une recherche d’emploi? ©2004 Ph. Gabrini Chapitre 3 Page 75 Dans la boucle do-while, les caractères de la chaîne et du patron sont comparés un à un; chaque fois qu'on note une différence des caractères, on repart au début du patron après avoir reculé dans la chaîne. Dans le pire des cas, c’est-à-dire celui où le patron ne se trouve pas dans la chaîne, chacun des p caractères du patron sera comparé aux t caractères de la chaîne texte (par exemple si nous cherchons “hipi” dans “hipahipbhipchipdhipehipfhipg”). La complexité temporelle de l'algorithme est donc O(pt). Dans la boucle do-while, les caractères de la chaîne et du patron sont comparés un à un; chaque fois qu'on note une différence des caractères, on repart au début du patron après avoir reculé dans la chaîne. Dans le pire des cas, c’est-à-dire celui où le patron ne se trouve pas dans la chaîne, chacun des p caractères du patron sera comparé aux t caractères de la chaîne texte (par exemple si nous cherchons “hipi” dans “hipahipbhipchipdhipehipfhipg”). La complexité temporelle de l'algorithme est donc O(pt). Algorithme de Knuth-Morris-Pratt Algorithme de Knuth-Morris-Pratt En examinant la recherche de patron de la figure 3.6, on se rend facilement compte que certaines comparaisons sont inutiles. Par exemple, la comparaison de l'étape 4 est inutile, car le second caractère de la chaîne a déjà été examiné et peut être sauté. L'idée de base de l'algorithme de Knuth-Morris-Pratt2 est de tirer avantage de l'information obtenue avant qu'une différence ne soit trouvée. Si une différence apparaît au nème caractère du patron, les (n-1) premiers caractères correspondaient. Sauter tous ces caractères ne fonctionnera pas, car le patron pourrait correspondre à des parties de lui-même au point où la différence se produit. Par exemple, si nous cherchons “grigou” dans “grisettegrignotanteetgrigou”, la première différence se produit au quatrième caractère, nous avançons dans la chaîne et reprenons le patron au début. La seconde différence après quelques correspondances se produit au treizième caractère de la chaîne. On reste au même endroit de la chaîne et on repart au second caractère du patron, un peu comme si on avait reculé dans la chaîne et repris au début du patron. Le meilleur « recul » ne dépend que du patron et du fait qu'il peut se correspondre, constatation qui peut être faite au préalable et conservée dans une table des reculs; la figure 3.7 montre ce qu’il faut faire si un caractère du patron ne correspond pas au caractère du texte et aide à comprendre le recul dans le patron. En examinant la recherche de patron de la figure 3.6, on se rend facilement compte que certaines comparaisons sont inutiles. Par exemple, la comparaison de l'étape 4 est inutile, car le second caractère de la chaîne a déjà été examiné et peut être sauté. L'idée de base de l'algorithme de Knuth-Morris-Pratt2 est de tirer avantage de l'information obtenue avant qu'une différence ne soit trouvée. Si une différence apparaît au nème caractère du patron, les (n-1) premiers caractères correspondaient. Sauter tous ces caractères ne fonctionnera pas, car le patron pourrait correspondre à des parties de lui-même au point où la différence se produit. Par exemple, si nous cherchons “grigou” dans “grisettegrignotanteetgrigou”, la première différence se produit au quatrième caractère, nous avançons dans la chaîne et reprenons le patron au début. La seconde différence après quelques correspondances se produit au treizième caractère de la chaîne. On reste au même endroit de la chaîne et on repart au second caractère du patron, un peu comme si on avait reculé dans la chaîne et repris au début du patron. Le meilleur « recul » ne dépend que du patron et du fait qu'il peut se correspondre, constatation qui peut être faite au préalable et conservée dans une table des reculs; la figure 3.7 montre ce qu’il faut faire si un caractère du patron ne correspond pas au caractère du texte et aide à comprendre le recul dans le patron. Position Correspondance Recul[j] Commentaires différence 0 aucune -1 pas g, avancer dans chaîne et patron au début 1 g 0 pas r, peut être g, patron: aller au début, chaîne: rester 2 gr 0 pas i, peut être g, patron: aller au début, chaîne: rester 3 gri -1 pas g, avancer dans chaîne et patron au début 4 grig 1 pas o, peut être r, patron: aller à 1, chaîne: rester 5 grigo 0 pas u, peut être g, patron: aller au début, chaîne: rester Figure 3.7 Table des reculs De façon un peu plus générale, lorsqu’on calcule le recul (ou décalage) à effectuer on peut raisonnablement penser qu’un préfixe pré du patron correspond à un suffixe de la portion du patron ayant correspondu au texte cor (figure 3.8). Afin d’éviter une non correspondance immédiate, il faut que le caractère qui suit immédiatement pré soit différent du caractère du texte ayant provoqué la non correspondance après cor. On appelle le plus long de ces préfixes la bordure de cor. On donne à TableRecul[i] la valeur de la longueur de la bordure de Patron[0..i-1] suivie d’un caractère différent de Patron[i] ou –1 si une telle bordure n’existe pas. On reprend alors la comparaison entre Patron[TableRecul[i]] et Texte[i+j] sans manquer de correspondance de Patron dans Texte et en évitant de reculer dans le texte. Texte z y cor x j i+j cor Patron z pré Figure 3.8 Décalage de l’algorithme de Knuth-Morris-Pratt ©2004 Ph. Gabrini³ 2 Knuth, D. E., Morris, J. H., Pratt, V. R., Fast pattern matching in strings, SIAM J. Comp., vol. 6 no 2, juin 1977. Page 76 C++, structures de données et la STL La fonction ci-dessous effectue la recherche de patron en avançant de la façon normale tant que les caractères correspondent; autrement elle recule dans le patron de la valeur trouvée dans une table des reculs. La figure 3.9 illustre le processus de décalage aux endroits où il y a certaines correspondances. Un astérisque indique la fin d'une correspondance. Après la première différence au quatrième caractère, on avance de caractère en caractère à cause des différences jusqu'à une correspondance partielle qui s'arrête à une différence sur le cinquième caractère du patron; on recule au deuxième caractère du patron et on reprend dans la chaîne sur le caractère déjà examiné. La différence qui se produit nous fait à nouveau progresser de caractère en caractère jusqu'à la correspondance totale de la fin du patron. grisettegrignotanteetgrigou grigou..................... ...*grigou................. ....*grigou................ .... *grigou............... ......*grigou.............. .......*grig*u............. ...........g*igou.......... ............*grigou........ .............*grigou....... ..............*grigou...... ...............*grigou..... ................*grigou.... .................*grigou... ..................*grigou.. ...................*grigou. ....................*grigou Figure 3.9 Recherche de “grigou” void CalculerRecul(const string& Patron, int TableRecul[]) { // Calculer la table des sauts pour les caractères du patron. int longueurPatron, pat1 = 0, pat2 = -1; longueurPatron = Patron.size(); TableRecul[0] = -1; while(pat1 < longueurPatron){ while(pat2 > -1 && Patron[pat1] != Patron[pat2]) pat2 = TableRecul[pat2]; pat1++; uploads/Science et Technologie/ algorithmes-de-recherche-dans-les-chaines-de-caracteres.pdf