Aller au contenu

Algorithme de Boyer-Moore

Recherche de Motifs dans un Texte⚓︎

La recherche de motifs dans un texte est une tâche classique en informatique, particulièrement dans le domaine du traitement de texte. Voici deux algorithmes populaires : l'algorithme naïf et l'algorithme de Boyer-Moore.

Algorithme Naïf⚓︎

Description⚓︎

L'algorithme naïf est le moyen le plus simple de rechercher un motif dans un texte. Il consiste à comparer le motif avec chaque "fenêtre" du texte de la même longueur que le motif.

Les comparaisons vont être effectuées en déplaçant la fenêtre glissante jusqu'à la fin du texte si nécessaire. Pour chaque position de la fenêtre glissante, les caractères du motifs vont être comparés un à un. Si tous les caractères correspondent, le motif a été trouvé, sinon on décale la fenêtre d'un caractère et on recommence.

Complexité⚓︎

  • Pire cas : \(O(n \cdot m)\), où \(n\) est la longueur du texte et \(m\) la longueur du motif.

Code à compléter

Code Python⚓︎

Python
1
2
3
4
5
6
def recherche_naive(texte, motif):
    n = len(texte)
    m = len(motif)

    for i in range(....):
        ....

Algorithme de Boyer-Moore⚓︎

Description⚓︎

L'algorithme de Boyer-Moore est plus efficace que l'algorithme naïf, surtout pour les grands textes. Il utilise des heuristiques pour sauter des sections du texte, réduisant ainsi le nombre de comparaisons.

Heuristiques Utilisées⚓︎

  1. La règle du dernier caractère : Lorsqu'un caractère du motif ne correspond pas, déplacez le motif en fonction de la position de ce caractère dans le motif.
  2. La règle du mauvais caractère : Utilisez la position de la dernière occurrence du caractère du texte dans le motif pour optimiser le saut.

Complexité⚓︎

  • Pire cas : \(O(n \cdot m)\) dans certains cas, mais généralement \(O(n/m)\) grâce aux sauts.

Code Python⚓︎

solution
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def pretraitement(motif):
    m = len(motif)
    dernier = {}
    for i in range(m):
        dernier[motif[i]] = i
    return dernier

def recherche_boyer_moore(texte, motif):
    n = len(texte)
    m = len(motif)
    dernier = pretraitement(motif)
    i = 0  # index du texte
    while i <= n - m:
        j = m - 1  # index du motif
        while j >= 0 and texte[i + j] == motif[j]:
            j -= 1
        if j < 0:
            print(f"Motif trouvé à l'index {i}")
            i += (m - dernier.get(texte[i + m], -1)) if i + m < n else 1
        else:
            i += max(1, j - dernier.get(texte[i + j], -1))