Terminale NSI — Recherche textuelle

Séance 1 — Le problème et l'algorithme naïf

Vocabulaire, algorithme naïf, mesures · 2h

1. Le problème de la recherche textuelle

On cherche à savoir si une chaîne de caractères, le motif, est présente dans une chaîne plus longue, le texte, et à quel(s) indice(s) (position, en partant de 0).

Exemple
Texte : « L'informatique est la science du traitement automatique. » — Motif : « mati » — Résultat : présent à l'indice 8.

Une occurrence est une position où le motif apparaît intégralement dans le texte.

2. Exercice 1 — L'algorithme naïf

L'idée la plus simple : faire glisser le motif le long du texte, position par position.

def occurrence(m, t, i):
    """indique s'il y a une occurrence de m dans t à la position i"""
    if i < 0 or i > len(t) - len(m):
        return False
    for j in range(len(m)):
        if t[i + j] != m[j]:
            return False
    return True

def recherche(m, t):
    """affiche toutes les occurrences de m dans t"""
    ...

a) Complète recherche(m, t). Jusqu'à quelle position i faut-il tester ? b) Teste avec texte = "une magnifique maison bleue", motif = "maison". c) Teste avec un motif absent, puis un motif présent plusieurs fois.

Voir la réponse
def recherche(m, t):
    for i in range(0, len(t) - len(m) + 1):
        if occurrence(m, t, i):
            print("occurrence à la position", i)
Il faut tester i de 0 à len(t) - len(m) inclus : c'est la dernière position où le motif peut encore tenir entièrement. 
recherche("maison", "une magnifique maison bleue")  # position 15
recherche("ma", "une magnifique maison bleue")       # positions 4 et 15

3. Exercice 2 — Compter les comparaisons

Motif : "chercher" — Texte : "chercher, rechercher et chercher encore"

a) Compte les comparaisons à la position 0. b) À la position 1 (l'espace). c) Total sur tout le texte.

Voir la réponse
Position 0 : les 8 caractères correspondent → 8 comparaisons.
Position 1 : 1 seule comparaison (échec immédiat sur l'espace).
Total sur l'ensemble du texte : 54 comparaisons.

4. Exercice 3 — premiere_occurrence()

Écris une fonction qui renvoie l'indice de la première occurrence, ou None si absente.

Voir la réponse
def premiere_occurrence(m, t):
    for i in range(0, len(t) - len(m) + 1):
        if occurrence(m, t, i):
            return i
    return None
Plus efficace que recherche() : elle s'arrête (return) dès qu'une occurrence est trouvée.

5. Exercice 4 — Version booléenne early-stop

Écris contient(m, t) qui répond seulement True/False, en s'arrêtant le plus tôt possible.

Voir la réponse
def contient(m, t):
    for i in range(0, len(t) - len(m) + 1):
        if occurrence(m, t, i):
            return True
    return False
occurrence() s'arrête déjà dès le premier caractère différent grâce au return immédiat.

6. Exercice 5 — Mesure de temps sur un texte réel

import time
debut = time.perf_counter()
resultat = premiere_occurrence(motif, text_long)
duree = time.perf_counter() - debut
print(f"Trouvé à l'indice {resultat} en {duree:.6f} s")

a) Mot court et fréquent. b) Expression longue présente. c) Mot absent. d) Quelle recherche est la plus longue, et pourquoi ?

Voir la réponse
En général, la recherche d'un mot absent est la plus longue : l'algorithme doit parcourir tout le texte sans jamais pouvoir s'arrêter avant la fin.

Exercices défis (bonus)

Défi 1 défi

Exprime le nombre maximal de comparaisons en fonction de n (texte) et m (motif).

Voir la réponse
De l'ordre de (n - m + 1) × m, soit environ n × m quand m est petit devant n.
Défi 2 défi

Construis un exemple provoquant le pire des cas (texte très répétitif).

Voir la réponse
texte = "a" * 1000
motif = "a" * 50 + "b"   # échoue toujours sur le dernier caractère, après 50 comparaisons
Défi 3 défi

Modifie recherche() pour renvoyer la liste de tous les indices (occurrences chevauchantes incluses).

Voir la réponse
def recherche_indices(m, t):
    indices = []
    for i in range(0, len(t) - len(m) + 1):
        if occurrence(m, t, i):
            indices.append(i)
    return indices

print(recherche_indices("aa", "aaaa"))   # [0, 1, 2]