Recherche textuelle — l'algorithme de Boyer-Moore

Introduction

Rechercher un motif dans un texte est une opération omniprésente : la barre de recherche d'un éditeur de texte, la commande grep sous Unix, les filtres anti-spam, la bio-informatique… Plutôt que de comparer le motif caractère par caractère à toutes les positions du texte (force brute, coût $\mathcal{O}(nm)$ avec $n$ longueur du texte et $m$ longueur du motif), l'algorithme de Boyer-Moore prétraite le motif pour pouvoir effectuer de grands sauts lors d'un échec, et descend parfois en $\mathcal{O}(n/m)$ — il saute des caractères du texte sans les regarder.

Pensez à la façon dont vous cherchez un mot dans un livre papier : si votre œil tombe sur une lettre qui n'appartient pas du tout au mot recherché, vous tournez la page sans relire les mots autour — c'est l'intuition exacte de la règle du mauvais caractère introduite plus bas.

Recherche naïve — pour comparer

L'algorithme naïf glisse le motif sur le texte, position par position, et compare. Dès qu'un caractère diffère, on décale d'un cran et on recommence.

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

Coût : jusqu'à $n - m + 1$ tentatives, chacune jusqu'à $m$ comparaisons, soit $\mathcal{O}(nm)$ en pire cas. Acceptable pour des petits textes, prohibitif sur des génomes ou des corpus.

L'intuition de Boyer-Moore

Deux idées fondatrices, contre-intuitives :

1. Comparer de droite à gauche : on aligne le motif à une position du texte, puis on compare ses caractères en partant de la fin.
2. Prétraiter le motif pour savoir, en cas d'échec, combien de cases on peut sauter sans risquer de manquer une occurrence.

Le prétraitement consiste à construire une table du mauvais caractère : pour chaque lettre de l'alphabet, on note sa position la plus à droite dans le motif.

La règle du mauvais caractère

Supposons qu'on compare le motif et le texte en partant de la droite, et que le premier caractère discordant soit c dans le texte, à la position $i$ du texte alignée avec la position $j$ du motif.

• Si c n'apparaît pas du tout dans le motif, on peut décaler de $j + 1$ : aucune occurrence possible qui contiendrait c à cette position.
• Si c apparaît dans le motif à la position $k$ la plus à droite ($k < j$), on décale pour aligner cette occurrence sur le texte : décalage de $j - k$.

def table_mauvais_caractere(motif):
    """Pour chaque caractère du motif, sa dernière position (0-indexée)."""
    table = {}
    for i, c in enumerate(motif):
        table[c] = i
    return table

def boyer_moore(texte, motif):
    n, m = len(texte), len(motif)
    if m == 0: return 0
    table = table_mauvais_caractere(motif)
    i = 0
    while i <= n - m:
        j = m - 1
        # Compare de droite à gauche.
        while j >= 0 and motif[j] == texte[i + j]:
            j -= 1
        if j < 0:
            return i                        # occurrence trouvée
        # Décalage par règle du mauvais caractère.
        c = texte[i + j]
        saut = j - table.get(c, -1)
        i += max(1, saut)                   # garantit la progression
    return -1

Un exemple déroulé

Recherchons ABCDE dans XYZQABCDE.

Position 0 :   X Y Z Q A B C D E
               A B C D E             ← échec en j=4 : E ≠ A
                                       texte[i+j]='A', table['A']=0
                                       saut = 4 - 0 = 4 → i passe à 4
Position 4 :   X Y Z Q A B C D E
                       A B C D E     ← match complet, retourne 4

L'astuce, c'est que dès le premier échec, on saute directement 4 cases au lieu d'1 — un seul échec a remplacé 4 comparaisons inutiles.

Coût — sans entrer dans la preuve

Le BO le mentionne explicitement : « l'étude du coût, difficile, ne peut être exigée ». On retient cependant :

En pratique, plus l'alphabet est grand (texte naturel, ADN), plus la table permet des sauts longs — Boyer-Moore est l'algorithme utilisé par grep classique pour cette raison.

Pour aller plus loin

D'autres algorithmes prétraitent le motif différemment : Knuth-Morris-Pratt (KMP) garantit $\mathcal{O}(n + m)$ en pire cas, Rabin-Karp utilise des fonctions de hachage. Sur de très grandes bases de données textuelles (génome humain de 3 milliards de paires de bases), on prétraite plutôt le texte : c'est le rôle des index (suffix arrays, FM-index) qui permettent des recherches en temps quasi-constant après un prétraitement initial coûteux.