burger menuschoolmouv-logo

01 86 76 13 95

(Appel gratuit)

Nos offres
Tle
breadcrumb homearrow Tlearrow Numérique et sciences informatiquesarrow Recherche de sous-chaînearrow

Fiche de révision : Recherche de sous-chaîne

Recherche de sous-chaîne

information-icon

Les premières épreuves du bac 2025 sont pour bientôt ! Consulte notre dossier sur le contrôle continu et le calcul des notes de ton bac pour maximiser ta préparation pour les révisions à ton examen 💪

Recherche naïve

  • Un algorithme pour vérifier la présence d’une sous-chaîne (motif) au sein d’une chaîne de caractères (fenêtre) est assez facile à mettre au point.
  • Le motif peut être :
  • absent ;
  • ou présent (une ou plusieurs fois).
  • On compare les caractères de la chaîne à ceux formant le motif.
  • On procède par décalages successifs jusqu’à atteindre la fin du texte.
  • Si les caractères correspondent en regard du texte, on a trouvé une occurrence du motif dans le texte.
  • Dans une recherche naïve le texte est parcouru par déplacements de la fenêtre glissante, de gauche à droite et le contrôle du motif est effectué lettre à lettre, de gauche à droite.
  • L’implémentation de cet algorithme de recherche consiste à imbriquer deux boucles, et à relever les positions d’éventuelles occurrences, qu’on retourne sous forme d’une liste d’indices (vide si le motif recherché est absent).

def recherche(motif, texte):

positions = []
for i in range(len(texte) - len(motif)):

for j in range(len(motif)):

if not texte[i + j] == motif[j]:

break

if j == len(motif) - 1:

positions.append(i)

return positions

  • On peut également utiliser la construction for assortie de la clause optionnelle else, cette dernière n’étant exécutée que si la boucle s’est terminée normalement, sans avoir été interrompue par un break.
  • La complexité du code est dans le pire des cas $O(n\times{m})$, où $m$ est la longueur du motif et $n$ celle du texte.
  • Nous allons réaliser avec l’étude de l’algorithme de Boyer-Moore que différentes optimisations sont possibles pour ce type de recherche.

Algorithme de Boyer Moore

  • L’algorithme de Boyer-Moore est la figure de référence des algorithmes de recherche.
  • Cet algorithme est capable d’éviter de nombreuses comparaisons inutiles : il s’avère bien plus performant que la recherche naïve.
  • Il prend en compte les occurrences des lettres composant le motif et en déduit des comparaisons inutiles, qu’il ne sera pas nécessaire d’effectuer.
  • Les déplacements du motif s’effectuent de gauche à droite comme dans l’algorithme naïf, mais celui de Boyer-Moore présente la particularité d’évaluer le motif de la droite vers la gauche.
  • L’algorithme de Boyer-Moore commence par contrôler la fin du motif (matérialisé par un curseur au-dessus du texte).

⇩

CORRELATION N'EST PAS CAUSALITE

VERITE

  • La comparaison entre le E du motif et le L du texte permet de constater une non-correspondance.
  • Cette absence de la lettre « L » dans le motif garantit qu’on ne pourra trouver aucune correspondance, quelle que soit la manière dont on décalera le motif en regard de la position courante d’évaluation.
  • En conséquence, il est totalement inutile de vérifier les positions suivantes sur toute la longueur du motif.
  • On décale donc le motif vers la droite jusqu’à le positionner au-delà du caractère comparé dans le texte.
  • L’algorithme de Boyer-Moore a permis d’éliminer cinq positions inutiles de la fenêtre glissante du motif.
  • Nous allons maintenant décrire de manière plus formelle les deux règles complémentaires de l’algorithme de Boyer-Moore :
  • la règle du mauvais caractère ;
  • et la règle du bon suffixe.
  • Règle du mauvais caractère
  • La règle du mauvais caractère consiste à éliminer des positions considérées comme impossibles pour le motif.
  • Lors de l’évaluation d’un mauvais caractère, deux cas de figure sont possibles :
  • soit le caractère du texte est totalement absent du motif recherché (aucune position ne pourra aboutir à une correspondance) ;
  • soit le caractère du texte est présent, une ou plusieurs fois, ailleurs dans le motif, auquel cas on décale le motif jusqu’à alignement de la première occurrence du motif avec le caractère du texte (de la droite vers la gauche).

⇩

LA REALISATION INFORMATIQUE PAR PROGRAMMATION CONSTITUE UNE IMPLEMENTATION LOGICIELLE.

IMPLEMENTATION

  • Le caractère « M » est présent dans le motif : ce dernier est donc décalé pour mettre le M en correspondance.

⇩

LA REALISATION INFORMATIQUE PAR PROGRAMMATION CONSTITUE UNE IMPLEMENTATION LOGICIELLE.

IMPLEMENTATION

  • Règle du bon suffixe
  • La comparaison entre le motif et le texte s’effectuant de la droite vers la gauche, s’il existe une correspondance elle se matérialise au niveau du suffixe.
  • De la droite vers la gauche, on recherche une autre occurrence du suffixe qui soit précédée par un autre caractère que celui qui ne correspond pas : on s’arrête dès qu’une occurrence est trouvée et on décale le motif pour mettre cette occurrence en correspondance avec le suffixe du texte.

⇩

L OBJECTIF EST D EVITER DES COMPARAISONS INUTILES

RESERVER

L OBJECTIF EST D EVITER DES COMPARAISONS INUTILES

RESERVER

  • S’il n’existe pas d’autre occurrence du suffixe dans le motif, on le décale jusqu’à la mise en correspondance du plus long suffixe possible qui corresponde à un préfixe du motif.

⇩

RATIONALISATION DES RESSOURCES

IONISATION

RATIONALISATION DES RESSOURCES

IONISATION

  • S’il n’existe pas de préfixe du motif qui puisse correspondre à un suffixe du texte, on décale le motif au-delà du suffixe.
  • La découverte d’une occurrence est un cas particulier de la règle du bon suffixe où le bon suffixe est aussi long que le motif recherché.
  • Chacune des deux règles permet d’effectuer des décalages importants du motif sans risquer de manquer une occurrence de celui-ci.
  • L’algorithme de Boyer-Moore combine ces deux règles (et choisit au cas par cas la meilleure) pour maximiser les décalages.

Optimisation algorithmique

  • Les prétraitements permettent d’améliorer la performance des algorithmes de recherche textuelle. On distingue deux approches :
  • le prétraitement du motif (comme Boyer-Moore) ;
  • le prétraitement du texte.
  • Le prétraitement du motif vise à éviter d’effectuer de manière répétitive les mêmes calculs, en stockant leurs résultats dans des tables de saut, pour les réutiliser.
  • Les tables de saut indiquent l’ampleur du décalage à effectuer en fonction des lettres rencontrées dans le texte, en appliquant des règles de l’algorithme.
  • La table de sauts du mauvais caractère transpose l’application de la règle du mauvais caractère à l’alphabet des caractères possiblement présents dans le texte.
  • Il existe plusieurs méthodes équivalentes pour la génération de cette table de saut. On peut procéder :
  • en traitant le motif à partir de la fin ;
  • en listant successivement les lettres composant le motif ;
  • et en notant le nombre de décalages par rapport à la fin du motif.
  • Les lettres absentes du motif, représentées collectivement par un caractère « * », entraineront un décalage de la longueur du motif complet.