Algorithme de Boyer‑Moore

L’algorithme de Boyer‑Moore est l’un des plus élégants et performants pour la recherche d’un motif dans une chaîne de caractères. Il repose sur une idée simple, mais puissante : éviter au maximum les comparaisons inutiles. Là où des algorithmes naïfs testeraient chaque position une par une, Boyer‑Moore préfère sauter intelligemment plusieurs caractères à la fois.

Cet algorithme travaille de droite à gauche dans le motif. Plutôt que de comparer le motif au texte en commençant par le début, il va d’abord regarder la fin du motif. Si une lettre ne correspond pas, il déduit combien de caractères il peut sauter sans risque de rater une occurrence.

Deux heuristiques clés rendent cela possible :

La règle du mauvais caractère (bad character rule) : Lorsqu’une lettre ne correspond pas, on cherche la dernière apparition de cette lettre dans le motif. Si elle n’y est pas, on peut sauter tout le motif.
La règle du bon suffixe (good suffix rule) : Si une partie du motif a bien correspondu mais qu’un caractère précédent échoue, on cherche un autre endroit dans le motif où ce suffixe apparaît, ou un suffixe plus court qui pourrait fonctionner.

Exemple

Étape 1


A	B	B	A	C	A
C	A

Étape 2


A	B	B	A	C	A
		C	A


A	B	B	A	C	A
		C	A

Étape 3


A	B	B	A	C	A
				C	A


A	B	B	A	C	A
				C	A

Exemple en python

Voici un exemple de code Python illustrant la logique général des tableaux ci-dessus

def boyer_moore(text, pattern):
    m = len(pattern)
    n = len(text)
    skip = [m] * 256

    for i in range(m - 1):
        skip[ord(pattern[i])] = m - i - 1

    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        if j < 0:
            return i  # motif trouvé
        i += skip[ord(text[i + m - 1])]
    return -1

À noter : Boyer‑Moore fonctionne particulièrement bien sur de longues chaînes et avec de grands alphabets (comme l’ASCII ou l’Unicode). Son efficacité diminue quand le motif est très court ou que l’alphabet est minuscule (par exemple, en binaire).

Règle du mauvais caractère

def preprocess_bad_char(motif):
    """
    Prétraitement pour la règle du mauvais caractère.
    Crée un dictionnaire avec le dernier indice de chaque caractère dans le motif.
    
    :param motif: Le motif à rechercher
    :return: Dictionnaire des décalages pour chaque caractère
    """
    bad_char = {}
    m = len(motif)
    for i in range(m):
        # On garde la dernière occurrence de chaque caractère
        bad_char[motif[i]] = i
    return bad_char

Règle du bon suffixe

def preprocess_good_suffix(motif):
    """
    Prétraitement pour la règle du bon suffixe.
    
    :param motif: Le motif à rechercher
    :return: Tableaux good_suffix et prefix
    """
    m = len(motif)
    good_suffix = [0] * m
    prefix = [False] * m
    
    # Première passe: recherche des suffixes communs
    for i in range(m - 1):
        j = i
        k = 0  # Longueur du suffixe commun
        while j >= 0 and motif[j] == motif[m - 1 - k]:
            j -= 1
            k += 1
            good_suffix[k] = j + 1
        if j == -1:
            prefix[k] = True
    
    return good_suffix, prefix

Boyer Moore

def boyer_moore(texte, motif):
    """
    Implémentation de l'algorithme de Boyer-Moore pour la recherche de motif.
    Retourne l'indice de la première occurrence du motif dans le texte, ou -1 si non trouvé.
    
    :param texte: Le texte dans lequel chercher
    :param motif: Le motif à rechercher
    :return: Indice de la première occurrence ou -1
    """
    
    # Longueurs du texte et du motif
    n = len(texte)
    m = len(motif)
    
    # Cas particulier: motif vide
    if m == 0:
        return 0
    
    # Préparation des règles de décalage:
    # 1. Tableau du mauvais caractère
    bad_char = preprocess_bad_char(motif)
    
    # 2. Tableau du bon suffixe
    good_suffix, prefix = preprocess_good_suffix(motif)
    
    # Initialisation de l'indice de recherche
    i = 0  # Position courante dans le texte
    while i <= n - m:
        j = m - 1  # Parcours du motif de droite à gauche
        
        # Comparaison des caractères du motif et du texte
        while j >= 0 and motif[j] == texte[i + j]:
            j -= 1
        
        # Si le motif est trouvé
        if j == -1:
            return i
        
        # Calcul du décalage selon les règles de Boyer-Moore
        # 1. Décalage du mauvais caractère
        char_shift = bad_char.get(texte[i + j], m)
        bc_shift = max(1, j - char_shift)
        
        # 2. Décalage du bon suffixe
        gs_shift = 1
        if j < m - 1:  # Un suffixe a été trouvé
            gs_shift = compute_good_suffix_shift(j, m, good_suffix, prefix)
        
        # Appliquer le décalage maximal
        i += max(bc_shift, gs_shift)
    
    # Motif non trouvé
    return -1


def compute_good_suffix_shift(j, m, good_suffix, prefix):
    """
    Calcule le décalage selon la règle du bon suffixe.
    
    :param j: Position de la non-correspondance
    :param m: Longueur du motif
    :param good_suffix: Tableau good_suffix
    :param prefix: Tableau prefix
    :return: Valeur du décalage
    """
    k = m - 1 - j  # Longueur du suffixe correspondant
    if good_suffix[k] != -1:
        return j - good_suffix[k] + 1
    
    # Recherche d'un préfixe qui correspond à un suffixe plus long
    for r in range(j + 2, m):
        if prefix[m - r]:
            return r
    
    # Cas par défaut
    return m

Exemple :

if __name__ == "__main__":
    texte = "ABAAABCDABCABCABC"
    motif = "ABC"
    result = boyer_moore(texte, motif)
    print(f"Le motif '{motif}' a été trouvé à l'indice {result} dans le texte '{texte}'")

L'algorithme de Boyer‑Moore

All work licensed under CC BY-NC-SA 4.0