Algorithme de Boyer-Moore - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

L'algorithme de Boyer-Moore est un algorithme de recherche de sous-chaîne particulièrement efficace. Il a été développé par Bob Boyer et J Strother Moore en 1977.

Efficacité / complexité en temps

L'algorithme de Boyer-Moore (L'algorithme de Boyer-Moore est un algorithme de recherche de sous-chaîne...) pré-traite la sous-chaîne (c'est-à-dire la chaîne (Le mot chaîne peut avoir plusieurs significations :) recherchée), et non pas le texte (c'est-à-dire la chaîne dans laquelle la recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue...) est effectuée), à l'inverse (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de...) de certains algorithmes, qui amortissent le coût du prétraitement du texte en effectuant de très nombreuses recherches répétitives. Le coût d'exécution de l'algorithme de Boyer-Moore peut être sub-linéaire, c'est-à-dire qu'il n'a pas besoin (Les besoins se situent au niveau de l'interaction entre l'individu et l'environnement. Il est...) de vérifier chacun des caractères du texte, mais peut au contraire sauter certains d'entre eux. En général, l'algorithme devient plus rapide lorsque la longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus...) de la sous-chaîne s'allonge. Cette efficacité provient du fait que, pour chaque tentative infructueuse de correspondance (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le...) entre les deux chaînes (texte et sous-chaîne), il utilise les informations déduites de cet échec pour éliminer le plus grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre...) possible de positions à vérifier.

En comparaison des méthodes de recherches basiques par la méthode de « force brute » (qui recherche la sous-chaîne en commençant par chercher partout dans le texte une correspondance du premier caractère de la sous-chaîne, puis en vérifiant si les caractères suivants correspondent) et dont la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par...) en temps (Le temps est un concept développé par l'être humain pour appréhender le...) (calculée par exemple selon le nombre de paires de caractères à comparer) croit en O(L · K) où K est la longueur de la sous-chaîne clé recherchée, et L la longueur où l’on recherche s’il existe au moins une occurrences de la clé, l’algorithme de Boyer-Moore peut trouver les occurrences en un temps :

  • De l’ordre de O(L / K) dans le cas le plus favorable : dans ce meilleur cas, seul un caractère sur M doit être vérifié. Ainsi, plus la sous-chaîne est longue, et plus l’algorithme est efficace pour la trouver ;
  • de l’ordre de O(L + K) dans le pire cas (en utilisant la variante améliorée de l’algorithme avec la seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui...) table de vérification des occurrences).
  • et très souvent en un temps à peine supérieur au meilleur cas (qui devient de plus en plus probable quand la longueur K de la clé s’accroit). Le pire cas est obtenu quand le texte contient de très nombreuses occurrences d’un même caractère, et quand la clé cherchée contient ce caractère fréquent de nombreuses fois en fin de chaine sauf pour le premier caractère qui est différent.

Le cas moyen pour établir s’il y a correspondance ou non requiert environ (3 · K) comparaisons. La preuve est due à Richard Cole.

Dans le pire cas, les performances de l'algorithme de base (sans la variante avec la seconde table de vérification des occurrences) pour trouver toutes les correspondances est de l'ordre de O(K · L). Le pire cas se produit quand la sous-chaîne consiste en une répétition d’un unique caractère, et que le texte correspond à la répétition de (K - 1) fois ce même caractère, précédé par un seul autre caractère différent. Dans ce cas de figure, l’algorithme doit vérifier (L - K+ 1) décalages différents dans le texte pour chaque correspondance. Or, chacune de ces vérifications nécessite K comparaisons.

En raison de l’intérêt de la variante avec la seconde table qui permet un comportement sous-linéaire même dans le pire cas, cette variante est décrite ici (et est celle aujourd'hui intégrée dans de nombreuses librairies de traitement du texte pour C/C++, Java, etc.).

Page générée en 0.038 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique