Corrigé des exercices — Recherche textuelle

1. QCM

Question	Réponse	Explication
1	b.	On parcourt au maximum tous les caractères du texte une fois : O(n).
2	c.	On teste les positions 0, 1, ..., n-m, soit n - m + 1 positions.
3	b.	Boyer-Moore compare de droite à gauche (fin du motif vers le début).
4	b.	Le pré-traitement permet de savoir de combien décaler après un échec.
5	c.	Dans le pire cas, on compare m caractères pour chacune des n-m+1 positions.

2. Questions de cours

Question 1

Texte : "abracadabra" (longueur 11), Motif : "abra" (longueur 4)

a. Nombre de positions testées : n - m + 1 = 11 - 4 + 1 = 8 positions (indices 0 à 7)

b. Le motif "abra" est trouvé aux positions : - Position 0 : abracadabra - Position 7 : abracadabra

Question 2

L'algorithme de Boyer-Moore est plus efficace car :

Comparaison de droite à gauche : En cas d'échec sur un caractère qui n'existe pas dans le motif, on peut sauter tout le motif d'un coup.
Sauts importants : Plus le motif est long, plus les sauts potentiels sont grands. Par exemple, avec un motif de 10 caractères et un caractère non présent dans le motif, on peut avancer de 10 positions.
Cas favorable : Si l'alphabet est grand et le motif long, Boyer-Moore peut avoir une complexité sous-linéaire O(n/m) dans le meilleur cas.

Exemple : Rechercher "ALGORITHME" dans un texte. Si on tombe sur un "Z" (absent du motif), on saute directement de 10 caractères.

Question 3

a. recherche("bonjour", "jour") renvoie 3

Vérification : bonjour → à l'indice 3, on trouve jour.

b. recherche("bonjour", "soir") renvoie -1

Le motif "soir" n'est pas présent dans "bonjour".

c. Modification pour renvoyer toutes les positions :

def recherche_toutes(texte, motif):
  n = len(texte)
  m = len(motif)
  positions = []
  for j in range(n - m + 1):
    i = 0
    while i < m and texte[j + i] == motif[i]:
      i = i + 1
    if i == m:
      positions.append(j)
  return positions

>>> recherche_toutes("abracadabra", "abra")
[0, 7]

3. Exercices de programmation

Exercice 1 : Compter les occurrences

def compter_occurrences(texte, motif):
  """Compte le nombre d'occurrences du motif dans le texte."""
  n = len(texte)
  m = len(motif)
  compteur = 0
  for j in range(n - m + 1):
    i = 0
    while i < m and texte[j + i] == motif[i]:
      i = i + 1
    if i == m:
      compteur += 1
  return compteur

Tests :

>>> compter_occurrences("abracadabra", "a")
5
>>> compter_occurrences("abracadabra", "abra")
2
>>> compter_occurrences("aaaa", "aa")
3  # Occurrences aux positions 0, 1 et 2

Exercice 2 : Recherche insensible à la casse

def recherche_insensible(texte, motif):
  """Recherche un motif sans tenir compte des majuscules/minuscules."""
  texte_min = texte.lower()
  motif_min = motif.lower()
  n = len(texte_min)
  m = len(motif_min)
  for j in range(n - m + 1):
    i = 0
    while i < m and texte_min[j + i] == motif_min[i]:
      i = i + 1
    if i == m:
      return j
  return -1

Tests :

>>> recherche_insensible("Bonjour tout le Monde", "monde")
16
>>> recherche_insensible("PYTHON", "python")
0
>>> recherche_insensible("Hello World", "WORLD")
6

Exercice 3 : Analyse de complexité

Texte : "aaaaaaaaaa" (10 'a'), Motif : "aaab" (3 'a' puis 'b')

a. Calcul du nombre de comparaisons :

Positions testées : 10 - 4 + 1 = 7 positions (indices 0 à 6)
À chaque position, on compare les 3 premiers 'a' avec succès, puis échec sur 'b'
Soit 4 comparaisons par position

Total : 7 × 4 = 28 comparaisons

b. Ce cas est défavorable car :

Le motif partage un long préfixe avec le texte ("aaa")
À chaque tentative, on effectue presque toutes les comparaisons avant l'échec
On ne décale que d'une position à chaque fois
C'est le pire cas : beaucoup de comparaisons pour peu d'avancement

Ce type de motif (caractères répétés suivis d'un caractère différent) maximise le nombre de comparaisons.

Exercice 4 : Table des dernières occurrences

Pour le motif "EXEMPLE" (indices 0 à 6) :

Caractère	Dernière position
E	6
X	1
M	3
P	4
L	5

Note : Le caractère 'E' apparaît aux positions 0 et 6. On garde la dernière occurrence (6).

Construction en Python :

def table_occurrences(motif):
  table = {}
  for i in range(len(motif)):
    table[motif[i]] = i
  return table

>>> table_occurrences("EXEMPLE")
{'E': 6, 'X': 1, 'M': 3, 'P': 4, 'L': 5}

Utilisation : Si on rencontre un caractère 'X' lors d'un échec, on sait que la dernière occurrence de 'X' dans le motif est à la position 1. On peut donc calculer le décalage optimal.

Auteur : Florian Mathieu

Licence CC BY NC

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.