Algorithme de Boyer-Moore

Algorithme de Boyer-Moore 

[pic 1]

L’algorithme Boyer-Moore est un algorithme de recherche de chaînes. Cet algorithme est la référence standard pour la littérature pratique sur la recherche de chaînes.        

Il a été développé par Robert.S.Boyer et J Strother Moore en 1977, qui sont d’anciens professeurs d’informatique à la retraite et est largement utilisé dans de nombreux logiciels et applications. L'article original contenait des tables statiques pour calculer les changements de modèle sans explication sur la façon de les produire. L'algorithme de production des tableaux a été publié dans un article de suivi ; cet article contenait des erreurs qui ont ensuite été corrigées par Wojciech Rytter en 1980.

L'algorithme Boyer-Moore recherche les occurrences de P dans T en effectuant des comparaisons de caractères explicites à différents alignements. Au lieu d'une recherche par force brute de tous les alignements (dont il existe                          [pic 2]

Boyer-Moore utilise les informations obtenues par le prétraitement de P pour ignorer autant d'alignements que possible. 

L'objectif principal de l'algorithme de Boyer-Moore est d'optimiser la recherche de motifs en évitant autant que possible les comparaisons inutiles. Contrairement à d'autres algorithmes de recherche, comme l'algorithme de force brute ou l'algorithme de Knuth-Morris-Pratt, Boyer-Moore utilise des informations sur le motif lui-même pour sauter certaines parties de la chaîne de recherche.

L'algorithme de Boyer-Moore se compose de deux phases principales : la prétraitement du motif et la recherche proprement dite. Pendant la phase de prétraitement, des tables de saut sont construites pour le motif en se basant sur les caractères qui se répètent ou qui ne sont pas présents dans le motif. Ces tables de saut permettent de déterminer combien de caractères peuvent être sautés lorsqu'une correspondance n'est pas trouvée.

Lors de la phase de recherche, l'algorithme de Boyer-Moore effectue une recherche de droite à gauche dans la chaîne de caractères en comparant les caractères du motif avec ceux de la chaîne. En utilisant les tables de saut précalculées, il est capable de sauter plusieurs caractères lorsqu'une incompatibilité est détectée. Cela permet d'éliminer des parties entières de la chaîne de recherche et d'accélérer le processus de recherche.

L'avantage majeur de l'algorithme de Boyer-Moore réside dans son efficacité pour les motifs de recherche de grande taille ou pour les recherches dans de gros volumes de données. En utilisant les tables de saut, il évite de nombreuses comparaisons inutiles et peut être significativement plus rapide que d'autres algorithmes de recherche.

En conclusion, l'algorithme de Boyer-Moore est un algorithme puissant pour la recherche de motifs dans une chaîne de caractères. Sa capacité à sauter des caractères lorsqu'une incompatibilité est détectée permet d'accélérer la recherche et le rend particulièrement adapté aux situations où les motifs ou les volumes de données sont importants.

...