Tutoriel Algorithmique : Recherche Boyer Moore Horspool

Lorsque l'on recherche une chaîne de caractère dans un texte on se repose aujourd'hui sur les fonctions proposées par notre langage de programmation mais comment feriez vous pour trouver une chaîne si vous n'aviez pas accès à ces fonctions ? Comment ses fonctions recherchent-t-elles efficacement ?

L'approche Naïve / Brute force

La première approche qui peut venir en tête est l'approche "naïve" qui consiste à faire glisser le mot clef de recherche le long de notre chaîne jusqu'à trouver une correspondance.
On commence par comparer la première lettre de notre mot à la première lettre de notre texte.

v
je recherche le mot "mot" dans cette chaîne de caractère un peu longue
cette chaîne de caractère

Si cela correspond on passe à la lettre suivante, si cela ne correspond pas on décale le mot d'un cran et on recommence.

 v
je recherche le mot "mot" dans cette chaîne de caractère un peu longue
_cette chaîne de caractère

et ainsi de suite jusqu'à arriver au bout de notre chaîne ou jusqu'à arriver au mot recherché

je recherche le mot "mot" dans cette chaîne de caractère un peu longue
_______________________________cette chaîne de caractère

Dans cette situation toutes les lettres correspondent et on peut considérer que le mot a été trouvé.

Complexité

Pour comprendre la complexité de cet algorithme il faut analyser le meilleur et le pire de cas.

Le meilleur des cas se produit lorsque la chaîne de recherche commence par une lettre qui n'est pas présente dans la chaîne. Il y aura alors m - n + 1 itérations (avec m la taille de la chaine de caractère de recherche et n la taille du texte dans lequel on recherche).

je recherche le mot "mot" dans cette chaîne de caractère un peu longue
grafikart

Le pire des cas se produit lorsque la chaine de recherche et le texte utilise les même lettres.

aaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaab

Dans cette situation on aura un nombre d'itération égal à n^(m - n + 1). Cependant dans un cas réaliste on sera plus proche du premier cas (meilleur) que de celui-ci.

Boyer-Moore-Horspool

L'algorihme Boyer Moore Horspool (ou simplement Horspool) est une simplification de l'algorithme Boyer-Moore qui va se baser sur une table de saut. L'objectif de cet alrgorithme est de limiter le nombre d'itérations en sautant plusieurs étapes dans les vérifications. Reprenons notre cas :

                        v
je recherche le mot "mot" dans cette chaîne de caractère un peu longue
cette chaîne de caractère

L'algorithme va commencer par comparer les lettres mais de droite à gauche. Dès le début on a une non-correspondance car la lettre e ne correspond pas au caractère ". De la même manière le caractère " n'est présent nul part dans notre chaîne de recherche (il est donc inutile de faire des tests en glissant d'un seul caractère car on sait à l'avance que ça ne pourra pas convenir). On va alors sauter autant d'étape que l'on a de caractères dans la chaîne de recherche.

                                                 v
je recherche le mot "mot" dans cette chaîne de caractère un peu longue
_________________________cette chaîne de caractère

On tombe a nouveau sur une non-correspondance mais cette fois-ci avec un r. r étant présent dans notre chaîne on va décaler notre mot par rapport à la position du dernier r de notre mot.

                                                  v
je recherche le mot "mot" dans cette chaîne de caractère un peu longue
__________________________cette chaîne de caractère

Et on continue (cette fois ci avec le a)

                                                  v
je recherche le mot "mot" dans cette chaîne de caractère un peu longue
_______________________________cette chaîne de caractère

Et on vient de trouver une correspondance en seulement 4 itérations (contre 31 précédemment) !

Table de saut

Pour que cet algorithme fonctionne il faut dans un premier temps être capable de créer une table de saut. Cette table permet de savoir la longueur du saut à effectuer en fonction de la première lettre vérifiée.

Si vous le souhaitez vous pouvez voir sur ce site le déroulement de la recherche Boyer Moore Horspool.

Pour aller plus loin

Si vous voulez aller plus loin n'hésitez pas à vous rendre sur Wikipedia pour découvrir d'autres algorithmes.