La recherche textuelle

⚙️ Chapitre : Recherche textuelle

1️⃣ Introduction : le problème de la recherche textuelle

La recherche textuelle consiste à déterminer si un motif (une chaîne de caractères) apparaît dans un texte, et éventuellement à quelles positions.

Exemple :

• texte = "abracadabra"
• motif = "abra"

Le motif apparaît aux positions 0 et 7.

On note généralement :

• n : longueur du texte
• m : longueur du motif

2️⃣ La recherche naïve

La méthode la plus simple consiste à tester toutes les positions possibles du texte. On compare le motif caractère par caractère.

Principe :

• On place le motif au début du texte
• On compare les caractères un à un
• En cas d’échec, on décale le motif d’un caractère vers la droite
• On recommence jusqu’à la fin du texte

Exemple explicatif

texte = "banane"
motif = "ane"

On compare :

• "ban" ≠ "ane"
• "ana" ≠ "ane"
• "nan" ≠ "ane"
• "ane" = "ane" ✅

Le motif est trouvé à la position 3.

Implémentation en Python

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

3️⃣ Limites de la méthode naïve

En cas de nombreuses répétitions dans le texte, on refait beaucoup de comparaisons inutiles.

Exemple :

• texte = "aaaaaaaaab"
• motif = "aaab"

On compare plusieurs fois les mêmes caractères avant d’échouer.

Idée clé : éviter de refaire des comparaisons déjà effectuées.

4️⃣ L’algorithme de Boyer-Moore

L’algorithme de Boyer-Moore est une méthode efficace de recherche textuelle. Il est au programme de Terminale NSI.

Son idée principale :

• Comparer le motif en partant de la droite
• Utiliser un prétraitement du motif
• Décaler le motif de plusieurs positions en cas d’échec

5️⃣ Pourquoi un prétraitement du motif ?

Avant la recherche, on analyse le motif pour construire des informations utiles.

Ce prétraitement permet :

• de savoir combien de positions on peut sauter
• d’éviter des comparaisons inutiles
• d’accélérer fortement la recherche

Contrairement à la méthode naïve, on ne décale pas toujours d’un seul caractère.

6️⃣ Principe simplifié : règle du mauvais caractère

Lorsqu’un caractère du texte ne correspond pas au caractère du motif, on décale le motif pour aligner ce caractère avec sa dernière apparition dans le motif.

Si le caractère n’apparaît pas dans le motif, on peut décaler complètement le motif.

Exemple explicatif

texte = "HERE IS A SIMPLE EXAMPLE"
motif = "EXAMPLE"

On compare en partant de la droite du motif. En cas d’erreur, on utilise les informations issues du prétraitement pour effectuer un grand décalage.

7️⃣ Construction de la table du mauvais caractère

On construit un dictionnaire associant à chaque caractère sa dernière position dans le motif.

def table_mauvais_caractere(motif):
    table = {}
    for i in range(len(motif)):
        table[motif[i]] = i
    return table
# Appel de la fonction
motif = "EXEMPLE"
table = table_mauvais_caractere(motif)
print(table)

Si motif vaut "EXEMPLE", le dictionnaire obtenu sera :

{'E': 6, 'X': 1, 'M': 3, 'P': 4, 'L': 5}

Explication :

• Chaque caractère est associé à sa dernière position dans le motif
• La lettre 'E' apparaît plusieurs fois, mais seule la dernière position (6) est conservée
• Ce dictionnaire constitue le prétraitement utilisé par l’algorithme de Boyer-Moore

On peut ensuite accéder à une valeur avec :

print(table['M'])   # affiche 3

Cette information permettra de calculer le décalage lors d’une comparaison échouée.

8️⃣ Implémentation simplifiée de Boyer-Moore

def boyer_moore(texte, motif):
    n = len(texte)
    m = len(motif)
    table = table_mauvais_caractere(motif)
    
    i = 0
    while i <= n - m:
        j = m - 1
        
        while j >= 0 and motif[j] == texte[i + j]:
            j -= 1
        
        if j < 0:
            return i
        else:
            caractere = texte[i + j]
            decalage = j - table.get(caractere, -1)
            i += max(1, decalage)
    
    return -1

Exemple d’appel

texte = "VOICI UN EXEMPLE SIMPLE"
motif = "EXEMPLE"

position = boyer_moore(texte, motif)

print(position)   # affiche 9

Le motif "EXEMPLE" commence à la position 9 dans le texte.

Explication du déroulement

• On commence par construire la table avec table_mauvais_caractere(motif) → {'E': 6, 'X': 1, 'M': 3, 'P': 4, 'L': 5}
• On aligne le motif avec le texte à la position i
• On compare les caractères de droite à gauche grâce à l’indice j
• En cas d’erreur, on calcule un décalage grâce à la table
• On évite ainsi de tester toutes les positions une par une

Exemple avec motif absent

texte = "CETTE PHRASE NE CONTIENT PAS LE MOT"
motif = "EXEMPLE"

print(boyer_moore(texte, motif))   # affiche -1

Si le motif n’est pas trouvé, la fonction retourne -1.

Résumé du fonctionnement

• Prétraitement du motif → construction d’une table
• Comparaison de droite à gauche
• Décalages parfois supérieurs à 1 caractère
• Moins de comparaisons que la recherche naïve

L’efficacité de Boyer-Moore repose principalement sur le prétraitement et la stratégie de décalage intelligent.

9️⃣ Conclusion : intérêt et applications

L’algorithme de Boyer-Moore est généralement beaucoup plus rapide que la recherche naïve, notamment lorsque le texte est long.

Son efficacité repose sur deux idées essentielles :

• la comparaison de droite à gauche
• le prétraitement du motif, qui permet d’éviter des comparaisons inutiles

Cette optimisation est cruciale dans des domaines où les données sont très volumineuses.

En biologie, par exemple, l’ADN peut être vu comme une très longue chaîne composée des lettres A, T, C et G. Rechercher une séquence particulière revient à effectuer une recherche de motif dans un texte pouvant contenir plusieurs milliards de caractères.

Des algorithmes efficaces comme Boyer-Moore permettent alors :

• d’identifier des gènes dans un génome
• de repérer des mutations
• de comparer des séquences entre espèces

La recherche textuelle est donc un outil fondamental, aussi bien en informatique qu’en sciences du vivant.

🔟 À retenir

• Un motif est une chaîne que l’on cherche dans un texte
• La méthode naïve teste toutes les positions
• Boyer-Moore compare de droite à gauche
• Le prétraitement du motif est essentiel
• Applications importantes en informatique et en biologie