Algorithme de Boyer-Moore - Définition

Fonctionnement

Beaucoup de personnes sont surprises par l'algorithme de Boyer-Moore lorsqu'elles le découvrent pour la première fois, car il effectue la vérification, c'est-à-dire qu'il tente d'établir la correspondance de la sous-chaîne à une certaine position, à l'envers. Par exemple, s'il commence la recherche de la sous-chaîne WIKIPEDIA au début d'un texte, il vérifie d'abord la neuvième position en regardant si elle contient un A. Ensuite, s'il a trouvé un A, il vérifie la huitième position pour regarder si elle contient le dernier I de la sous-chaîne, et ainsi de suite jusqu'à ce qu'il ait vérifié la première position du texte pour y trouver un W.

La raison pour laquelle l'algorithme de Boyer-Moore utilise cette approche à rebours est plus claire si l'on considère ce qui se produit quand la vérification échoue, par exemple si au lieu de trouver un A en neuvième position, un X est lu. Le X n'apparaît nulle part dans la sous-chaîne WIKIPEDIA, ce qui signifie qu'aucune correspondance avec la sous-chaîne n'existe au tout début du texte, ainsi que dans les huit positions qui la suivent. Après la vérification d'un seul caractère, l'algorithme est capable de passer ces huit caractères et de rechercher le début d'une correspondance à partir de la dixième position dans le texte, juste après le X.

Ce principe de fonctionnement à rebours explique la quelque peu contre-intuitive affirmation disant que plus la sous-chaîne est longue, et plus l'algorithme est efficace pour la trouver.

Prenons un exemple plus significatif : on veut rechercher les occurrences de la clé de K=6 caractères “string” dans le texte de L=20 caractères “stupid_spring_string".

Avec un algorithme classique utilisant une méthode de force brute, on devrait rechercher le s dans tout le texte sauf les 5 derniers caractères, et donc faire toutes les 15 comparaisons. Et on trouverait 3 occurrences du s au début de chaque mot du texte ; pour chacune de ces occurrences on devrait vérifier la suite de la clé tant qu'elle correspond : on détecterait le p une fois pour rejeter l’occurrence commençant par spring, mais le t serait détecté 2 fois dans stupid et string ; on doit alors tester la présence du r après st pour éliminer l’occurrence dans stupid ; il reste encore à vérifier chacun des 3 autres caractères de la clé string, on il faudra donc 23 comparaisons (ce serait pire si le texte contenait de nombreuses occurrences de la quasi-totalité du début de la clé).

Avec l’algorithme de Boyer-Moore, on recherchera aussi les occurrences depuis le début du texte (en affichant ci-dessous la clé cherchée en dessous du texte balayé, les points notés avant la clé indiquant les positions déjà éliminées, le surlignage indique les comparaisons effectuées), mais on commencera en comparant le dernier caractère de la clé cherchée :

stupid_spring_string

string

Les deux caractères d et g ne correspondent pas, on a trouvé à la place un d dans le texte, alors qu’il n’y a aucun d dans la clé. On peut sauter directement dans le texte les 6 caractères de la clé :

stupid_spring_string

······string

Le g de la clé ne correspond pas au n du texte. Cependant, la clé contient un n, 1 caractère avant, on peut donc décaler d’1 position, et vérifier à nouveau en commençant par la fin de clé :

stupid_spring_string

·······string

On a trouvé successivement la correspondance du g, puis du n, puis du i, puis du r, mais pas du t de la clé. Au lieu de cela on a trouvé un p dans le texte, qui ne figure pas dans la clé, ce qui permet de sauter directement dans le texte les 6 caractères de la clé :

stupid_spring_string

·············string

Le g de la clé ne correspond pas au n du texte. Cependant, la clé contient un n, 1 caractère avant, on peut donc décaler d’1 position, et vérifier à nouveau en commençant par la fin de clé :

stupid_spring_string

··············string

On trouve successivement les correspondances du g, puis du n, du i, du r, du t et du s. Il n'y a plus d’autre caractère dans la clé, on a bien trouvé une occurrence en seulement 9 comparaisons (au lieu de 23 avec l’algorithme classique). Si on devait chercher les occurrences suivantes, il suffit de reprendre l’algorithme dans le texte à partir de la position qui suit la position trouvée.