Algorithmique

⚙️ 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 :

Le motif apparaît aux positions 0 et 7.

On note généralement :

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 :

Exemple explicatif

texte = "banane"
motif = "ane"

On compare :

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 :

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 :

5️⃣ Pourquoi un prétraitement du motif ?

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

Ce prétraitement permet :

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 :

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

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

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 :

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 :

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

🔟 À retenir