Terminale · Numérique et sciences informatiques

Comprendre la notion de motif dans la recherche textuelle

Définir un motif, distinguer ses occurrences dans un texte, énoncer ce que doit renvoyer un algorithme de recherche et dérouler la méthode naïve avec ses comparaisons.

Aperçu gratuit
Illustration de la fiche « Comprendre la notion de motif dans la recherche textuelle »

Les points essentiels

  • Un motif est une chaîne de caractères courte que l'on cherche dans un texte plus long ; le texte et le motif sont écrits sur un même alphabet fini (lettres, chiffres, symboles).
  • Une occurrence du motif dans le texte est une position i telle que les m caractères du texte à partir de i sont exactement ceux du motif. Les occurrences se repèrent par leur indice de début, en comptant à partir de 0 en Python.

Les mots à connaître

Motif
Chaîne de caractères, de longueur m, dont on cherche les apparitions dans un texte de longueur n (avec en général m ≤ n).
Occurrence
Indice i (0 ≤ i ≤ n-m) tel que texte[i:i+m] est égal au motif ; une même chaîne peut avoir plusieurs occurrences, éventuellement chevauchantes.

Un exemple pour comprendre

On cherche le motif "ANA" dans le texte "BANANE" (indices à partir de 0). Donner toutes les occurrences et le nombre de comparaisons de caractères effectuées par l'algorithme naïf qui parcourt toutes les positions.

Le texte a n = 6 caractères, le motif m = 3 : les positions candidates sont i = 0, 1, 2, 3. Position 0 : B ≠ A, 1 comparaison, échec. Position 1 : A = A, N = N, A = A, 3 comparaisons, succès. Position 2 : N ≠ A, 1 comparaison, échec. Position 3 : A = A, N = N, E ≠ A, 3 comparaisons, échec. Les occurrences sont donc [1] seulement : "BANANE" contient "ANA" en position 1 ("ANA" aux indices 1 à 3). En position 3 le facteur est "ANE", différent de "ANA". Total : 1 + 3 + 1 + 3 = 8 comparaisons.

Première page de l’Essentiel : Comprendre la notion de motif dans la recherche textuelle
Ketty