Algorithme de Boyer-Moore : recherche de motifs dans un texte

Introduction : Pourquoi un nouvel algorithme de recherche ?

Tu connais sûrement la méthode .find() en Python ou l'algorithme naïf qui compare le motif lettre par lettre à chaque position du texte. Ces méthodes fonctionnent, mais elles peuvent être très lentes sur de gros textes, comme un livre numérique ou une séquence ADN. Imagine devoir chercher un mot de 5 lettres dans un texte de 100 000 caractères... C'est là qu'intervient l'algorithme de Boyer-Moore, développé par Robert S. Boyer et J Strother Moore en 1977. Sa force ? Il est souvent sous-linéaire : il peut sauter des portions entières du texte, ce qui le rend extrêmement efficace en pratique. C'est un classique de l'informatique que tu dois maîtriser en NSI.

Le principe de base : lire de droite à gauche et sauter intelligemment

Contrairement à l'algorithme naïf qui lit de gauche à droite, Boyer-Moore compare le motif au texte en partant de la dernière lettre du motif. Cette inversion est la clé de sa performance. Prenons un exemple simple :

Texte : "UN ALGORITHME GENIAL"
Motif : "GENIE"

On aligne le début du motif avec le début du texte. On compare la dernière lettre du motif (E) avec le caractère correspondant dans le texte (U). Pas de correspondance. L'astuce : on regarde si ce caractère 'U' du texte apparaît quelque part dans notre motif "GENIE". La réponse est non. Dans ce cas, on peut faire glisser le motif complètement après ce 'U', car il est impossible qu'une correspondance existe si ce caractère n'est même pas dans le motif. On saute ainsi de plusieurs positions d'un coup ! Pour prendre ces décisions de saut, l'algorithme utilise deux heuristiques principales.

Les deux heuristiques magiques : Mauvais caractère et Bon suffixe

Ce sont les règles qui permettent de calculer de combien de positions on peut avancer sans risquer de rater une occurrence.

L'heuristique du Mauvais Caractère (Bad Character)

C'est celle que nous venons d'entrevoir. Lorsqu'une mauvaise correspondance (un "mauvais caractère") est trouvée :

• On regarde ce caractère du texte qui ne correspond pas.
• On cherche sa dernière occurrence dans le motif (en partant de la gauche).
• On décale le motif pour aligner cette occurrence trouvée dans le motif avec le mauvais caractère du texte.
• Si le caractère n'existe pas dans le motif, on décale le motif complètement après lui.

Cette recherche se fait en temps constant grâce à une table de pré-calcul (un dictionnaire en Python) créée avant la recherche.

L'heuristique du Bon Suffixe (Good Suffix)

Elle est utilisée quand une partie finale du motif (un suffixe) correspond au texte, mais que le caractère précédent dans le motif ne correspond pas. L'idée est de chercher une autre occurrence de ce suffixe qui correspond bien dans le motif, et de l'aligner. Si ce n'est pas possible, on décale le motif juste après la fin de la zone qui correspondait.

En pratique, pour chaque décalage, on prend le maximum des décalages proposés par les deux heuristiques. Cela garantit de ne jamais rater une occurrence potentielle tout en optimisant la vitesse.

Implémentation en Python pour la NSI

Voici une implémentation simplifiée qui utilise principalement l'heuristique du Mauvais Caractère, plus simple à coder et déjà très efficace.

def preprocess_bad_character(pattern):
    """Crée la table des derniers indices pour chaque caractère du motif."""
    bad_char = {}
    for i, char in enumerate(pattern):
        bad_char[char] = i  # Stocke la dernière occurrence
    return bad_char

def boyer_moore_search(text, pattern):
    """Recherche le motif dans le texte avec l'heuristique du mauvais caractère."""
    m = len(pattern)
    n = len(text)
    if m == 0:
        return 0
    
    bad_char = preprocess_bad_character(pattern)
    s = 0  # s est le décalage du motif par rapport au texte
    occurrences = []
    
    while s <= n - m:
        j = m - 1  # On commence par la fin du motif
        
        # Comparaison de droite à gauche
        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1
        
        if j < 0:
            # Tout le motif correspond !
            occurrences.append(s)
            # Décalage pour chercher l'occurrence suivante
            s += (m - bad_char.get(text[s + m], -1)) if s + m < n else 1
        else:
            # Mauvais caractère trouvé à la position j
            bc_shift = j - bad_char.get(text[s + j], -1)
            s += max(1, bc_shift)  # On décale d'au moins 1
    
    return occurrences

# Exemple d'utilisation
texte = "abracadabra"
motif = "abra"
print("Occurrences trouvées aux indices :", boyer_moore_search(texte, motif))
# Affiche : [0, 7]

Complexité et applications réelles

Dans le pire des cas (par exemple, chercher "aaa" dans "aaaaaaaa"), la complexité est de O(n * m), comme l'algorithme naïf. Mais dans la pratique, sur des textes et motifs courants (langage naturel, code source), il est souvent en O(n/m) ou proche de O(n), ce qui est excellent. C'est pourquoi il est utilisé dans de nombreux outils :

• Les commandes de recherche dans les fichiers (grep sous Linux).
• Les moteurs de recherche dans les éditeurs de texte (Notepad++, VS Code).
• Les logiciels de traitement de séquences biologiques (ADN, protéines).
• Les systèmes de détection d'intrusion (recherche de signatures de virus).

Comprendre Boyer-Moore, c'est comprendre une idée fondamentale en algorithmique : pré-calculer des informations (les tables) pour accélérer considérablement la phase de recherche principale. C'est une stratégie que tu retrouveras dans bien d'autres algorithmes.