Partie 5 : Recherche textuelle¶

Programme officiel (B.O.)¶

B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale

Contenus	Capacités attendues	Commentaires
Recherche textuelle.	Étudier l'algorithme de Boyer-Moore pour la recherche d'un motif dans un texte.	L'intérêt du prétraitement du motif est mis en avant. L'étude du coût de cet algorithme dans les cas favorables est réalisée.

1. Le problème de la recherche textuelle¶

1.1 Énoncé¶

Étant donnés un texte (chaîne de caractères) et un motif (sous-chaîne à chercher), déterminer si le motif apparaît dans le texte et, le cas échéant, à quelle(s) position(s).

Exemples :

Texte : "ABRACADABRA", motif : "CAD" → trouvé en position 4
Texte : "ABRACADABRA", motif : "XYZ" → non trouvé

1.2 Approche naïve¶

L'algorithme naïf compare le motif à chaque position possible du texte :

def recherche_naive(texte, motif):
    positions = []
    n, m = len(texte), len(motif)
    for i in range(n - m + 1):
        if texte[i:i + m] == motif:
            positions.append(i)
    return positions

Complexité : O(n × m) dans le pire cas (chaque position nécessite m comparaisons).

2. L'algorithme de Boyer-Moore¶

2.1 Idée principale¶

L'algorithme de Boyer-Moore améliore la recherche en comparant le motif de droite à gauche et en sautant des positions lorsqu'un caractère du texte ne correspond pas.

Deux heuristiques permettent ces sauts :

Heuristique du mauvais caractère (bad character rule) ;
Heuristique du bon suffixe (good suffix rule).

Au programme de Terminale, on étudie principalement l'heuristique du mauvais caractère.

2.2 Heuristique du mauvais caractère¶

Quand un caractère du texte ne correspond pas au motif, on regarde si ce caractère apparaît ailleurs dans le motif :

S'il n'apparaît pas : on peut décaler le motif au-delà de ce caractère ;
S'il apparaît : on décale le motif pour aligner cette occurrence avec la position courante.

2.3 Prétraitement du motif¶

On construit un dictionnaire indiquant, pour chaque caractère du motif, la position de sa dernière occurrence :

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

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

2.4 Algorithme complet¶

def boyer_moore(texte, motif):
    n, m = len(texte), len(motif)
    if m == 0:
        return []

    table = table_mauvais_caractere(motif)
    positions = []
    i = 0

    while i <= n - m:
        j = m - 1
        while j >= 0 and motif[j] == texte[i + j]:
            j -= 1

        if j < 0:
            positions.append(i)
            i += 1
        else:
            caractere = texte[i + j]
            if caractere in table:
                decalage = j - table[caractere]
                i += max(1, decalage)
            else:
                i += j + 1

    return positions

2.5 Exemple déroulé¶

Texte : ABRACADABRA, motif : ABRA

Table du mauvais caractère : {'A': 3, 'B': 1, 'R': 2}

Position 0 : ABRACADABRA
             ABRA          → comparaison de droite à gauche
             A=A ✓, R=R ✓, B=B ✓, A=A ✓ → trouvé en position 0

Position 1 : ABRACADABRA
              ABRA         → A vs B : mismatch
              B est en position 1 dans le motif, décalage = 2-1 = 1
              → on avance de max(1, 1) = 1

Position 2 : ABRACADABRA
               ABRA        → A vs A ✓, R vs C : mismatch
               C absent du motif → on avance de j+1 = 2

Position 4 : ABRACADABRA
                 ABRA       → A vs D : mismatch
                 D absent du motif → on avance de j+1 = 4

... (trouvé en position 7)

3. Complexité¶

3.1 Cas favorable¶

Dans le meilleur cas, Boyer-Moore est en O(n/m) : chaque comparaison élimine m positions (le dernier caractère du motif ne correspond jamais au texte). C'est sous-linéaire - on ne lit même pas tous les caractères du texte.

Exemple favorable : texte composé de A répétés, motif terminant par B. À chaque tentative, le premier caractère comparé (le dernier du motif, B) ne correspond pas au A du texte, et A n'apparaît pas dans le motif → on saute de m positions.

3.2 Cas défavorable¶

Dans le pire cas, Boyer-Moore (avec seulement l'heuristique du mauvais caractère) est en O(n × m), comme l'algorithme naïf. Cela arrive quand le texte et le motif sont composés du même caractère répété.

3.3 En pratique¶

Boyer-Moore est l'un des algorithmes de recherche textuelle les plus rapides en pratique pour les textes en langage naturel, car les sauts sont fréquents grâce à la diversité des caractères.

3.4 Comparaison¶

Algorithme	Prétraitement	Meilleur cas	Pire cas
Naïf	Aucun	O(n)	O(n × m)
Boyer-Moore	O(m + taille alphabet)	O(n/m)	O(n × m)

4. Intérêt du prétraitement¶

Le prétraitement du motif (construction de la table) se fait une seule fois en O(m) et permet ensuite de sauter efficacement des positions lors de la recherche. C'est un investissement initial qui se rentabilise sur de longs textes.

Ce principe se retrouve dans d'autres contextes : compilation d'expressions régulières, index de bases de données, etc.

À retenir¶

Concept	Description
Recherche naïve	Compare le motif à chaque position : O(n × m)
Boyer-Moore	Compare de droite à gauche, saute des positions
Mauvais caractère	Table indiquant la dernière occurrence de chaque caractère dans le motif
Prétraitement	Construction de la table en O(m), une seule fois
Cas favorable	O(n/m) - sous-linéaire
Utilisation	Éditeurs de texte, grep, moteurs de recherche