Skip to content

Cours - Algorithme de Boyer-Moore

L'algorithme de Boyer-Moore présent dans le programme de terminale est en réalité une version simplifiée de l'algorithme, appelée algorithme de Boyer-Moore-Horspool, qui consiste à ne garder que la première table de saut (règle du mauvais caractère).

La règle du bon suffixe sera évoquée pour votre culture, mais n'est pas au programme.

Rappel - Recherche textuelle naïve

Avant de voir l'algorithme de Boyer-Moore, rappelons la méthode de recherche textuelle "naïve", qui consiste à rechercher un motif dans un texte en parcourant tout le texte et en comparant le motif à chaque nouveau caractère rencontré.

Algorithme de recherche d'un motif dans un texte

ALGORITHME : recherche
ENTRÉES :
  texte : texte dans lequel rechercher - chaîne de caractères
  motif : motif à rechercher dans le texte - chaîne de caractères
SORTIE : position (indice) de la première occurence de motif dans texte, ou -1

DÉBUT ALGORITHME
  POUR i ALLANT DE 0 À longueur(texte) \(-\) longueur(motif) :
    j ← 0
    TANT QUE j \(<\) longueur(motif) ET QUE texte[i \(+\) j] \(=\) motif[j] :
      j ← j \(+\) 1
    FIN TANT QUE
    SI j \(=\) longueur(motif), ALORS :
      Renvoyer i
    FIN SI
  FIN POUR
  Renvoyer -1
FIN ALGORITHME

Note : On s'arrête à longueur(tableau) - longueur(motif) de manière à éviter de dépasser la taille du texte lors des comparaisons.

En langage Python, cet algorithme pourrait s'écrire ainsi :

def recherche(texte: str, motif: str) -> 'list[int]':
    ''' Renvoie une liste des positions d'un motif dans un texte. '''

    res = []
    for i in range(len(texte) - len(motif) + 1):
        j = 0
        while j < len(motif) and texte[i + j] == motif[j]:
            j += 1
        if j == len(motif):
            res.append(i)
    return res

Boyer-Moore-Horspool - Vidéo explicative

Voici une petite vidéo récapitulant le principe de fonctionnement de l'algorithme de Boyer-Moore-Horspool (version simplifiée de l'algorithme de Boyer-Moore).
Source de la vidéo : https://www.youtube.com/watch?v=9OYJ8L9R1F0.

Animation de l'algorithme de Boyer-Moore-Horspool

Voici une animation montrant le fonctionnement de l'algorithme de Boyer-Moore-Horspool. Vous pouvez changer le texte, le motif (pattern), et avancer en mode pas à pas (avec les boutons Avancer et Reculer) au en mode automatique.

L'algorithme

La table des sauts (ou table de décalage) peut être créée avec l'algorithme suivant, ici écrit en Python :

def decalage(motif):
    ''' Renvoie la table de décalage du motif donné.
    :param motif: (str) un motif
    :return: (dict) table de dacalage du motif '''

    Dec = {}
    for i in range(len(motif) - 1):
        Dec[motif[i]] = len(motif) - 1 - i
    return Dec

À présent, on peut écrire l'algorithme de Boyer-Moore-Horspool de la manière suivante :

def boyer_moore_horspool(texte, motif):
    ''' Recherche d'un motif dans un texte avec l'algorithme de Boyer-Moore-Horspool.
    :param texte: (str) un texte
    :param motif: (str) un motif à chercher dans le texte
    :return: (int) la position de la première occurence du motif dans le texte '''

    decale = decalage(motif)  # définir la table de décalage du motif
    i = len(motif) - 1  # variable de boucle de la première boucle (parcours du texte)
    while i < len(texte):  # tant qu'on a pas parcouru tout le texte
        j = 0  # variable de boucle de la deuxième boucle (parcours du motif)
        while j < len(motif) and texte[i - j] == motif[len(motif) - 1 - j]:  # tant qu'on a pas parcouru tout le motif et que les caractères correspondent
            j += 1  # on incrémente j

        # vérifier si on a parcouru tout le motif
        if j == len(motif):
            return i - len(motif) + 1  # renvoyer la position du motif dans le texte

        # décaler i en fonction de la table de décalage
        if texte[i] in decale:  # regarder si le caractère d'indice i du texte est dans le motif
            i += decale[texte[i]]  # si oui, on décale selon la valeur stockée dans la table de décalage
        else:  # sinon
            i += len(motif)  # on décale de la longueur du motif
    return -1

Visualiser avec Python Tutor

Autre écriture de la fonction

Voici une autre manière d'écrire la fonction, en initialant i avec la valeur 0.
Le principe reste le même, il y a juste quelques petites modifications à faire.

def boyer_moore_horspool(texte, motif):
    decale = decalage(motif)  # définir la table de décalage du motif
    i = 0  # variable de boucle de la première boucle (parcours du texte)
    while i < len(texte) - len(motif):  # tant qu'on a pas parcouru tout le texte
        j = len(motif) - 1  # variable de boucle de la deuxième boucle (parcours du motif, en commençant à la fin)
        while j >= 0 and texte[i + j] == motif[j]:  # tant qu'on a pas parcouru tout le motif et que les caractères correspondent
            j -= 1  # on décrémente j

        # vérifier si on a parcouru tout le motif
        if j < 0:
            return i  # renvoyer la position du motif dans le texte

        # décaler i en fonction de la table de décalage
        car = texte[i + len(motif) - 1]  # caractère à chercher dans la table de décalage
        if car in decale:  # regarder si le caractère 'car' est dans le motif
            i += decale[car]  # si oui, on décale selon la valeur stockée dans la table de décalage
        else:  # sinon
            i += len(motif)  # on décale de la longueur du motif
    return -1

Aller plus loin

Pour aller plus loin, vous pouvez consulter le notebook Boyer_Moore_BS_Eleve.ipynb ci-dessous présentant la règle du bon suffixe, ainsi que le notebook Boyer_Moore_complet.ipynb implémentant l'algorithme de Boyer-Moore complet, utilisant à la fois la règle du mauvais caractère et la règle du bon suffixe.

Notebooks

Voici également une petite vidéo expliquant le principe de la règle du bon suffixe :