Algorithme de Boyer-Moore-Horspool
# Algorithme de Boyer-Moore-Horspool

L'algorithme de Boyer-Moore-Horspool, parfois appelé algorithme de Horspool est un algorithme de recherche de sous-chaîne publié par Nigel Horspool en 1980. Il consiste en une simplification de l’algorithme de Boyer-Moore qui ne garde que la première table de saut. On considère un texte et on note m le motif (la sous-chaîne) à chercher dans ce texte.

## Principe

Expliquons le principe sur la recherche du motif m string dans le texte wikipedia. L'algorithme de Boyer-Moore-Horspool est une adaptation de l'algorithme naïf pour rechercher une sous-chaîne. L'algorithme utilise un pré-traitement du motif afin de calculer le saut maximum à effectuer après avoir trouvé une non-concordance. Durant la recherche la comparaison se fait de la droite vers la gauche.

### Rappel de l'algorithme naïf

On considère le motif comme une fenêtre glissante sur le texte. On commence avec :

Dans l'algorithme naïf (voir l'article algorithme de recherche de sous-chaîne), on compare wikipe et string, constatant qu'ils ont différents, on décale le motif d'une case vers la droite :

Mais on voit que tous ces décalages mèneront à un échec :

### Amélioration

Dans l'algorithme de Boyer-Moore-Horspool, la comparaison du motif avec la portion du texte correspondante s'effectue de droite à gauche. Ainsi à la première étape, le dernier caractère du motif est comparé à sa position dans le texte, à savoir g et e.

Ces deux caractères étant différents, on cherche donc à savoir de combien il faut décaler le texte. Comme e n'apparaît pas dans le motif, il faut complètement décaler le motif, soit de 6. Mais alors, le motif déborde du texte :

L'algorithme termine en déclarant que string n'apparaît pas dans wikipedia. Cet exemple extrême est intéressant car un seul caractère du texte a été lu.

### Idée

Dans l'exemple précédent, le caractère e n'apparaît pas dans le motif. Si jamais la lettre apparaît dans le motif, il faut savoir de combien il faut décaler. L'algorithme précalcule une table de la dernière occurrence, qui indique pour chaque lettre de combien il faut décaler.

## Pseudo-code

Dans cette section, on suppose que les indices dans le texte et motif commence à 0. L'algorithme commence par précalculer une table T. Puis l'algorithme est similaire à l'algorithme naïf sauf que l'on décale de T[texte[j]] au lieu de décaler de 1, où j est l'indice dans le texte, aligné avec le dernier caractère de la fenêtre glissante :

Dans cette section, on suppose que les indices dans le texte et motif commence à 0.

### Construction de la table de la dernière occurrence

L'algorithme commence par précalculer la table T de la dernière occurrence. Crochemore et al. définissent la table T comme suit. Pour toute lettre a, $T[a]=min(\{m\}\cup \{|m|-1-k,0\leq k\leq |m|-2{\text{ et }}m[k]=a\})$. Autrement dit, si la lettre a n'apparaît pas dans le motif, alors T[a] vaut m. Sinon, on considère la position k de la dernière occurrence de a dans le motif m : T[a] est alors |m| - 1 - k. Beauquier, Berstel et Chrétienne proposent une définition équivalente et l'appelle fonction de la dernière occurrence :

$T[a]={\begin{cases}|u|{\text{ si }}au{\text{ est suffixe de }}m{\text{, }}u{\text{ non vide et }}a{\text{ ne figure pas dans }}u\\|m|{\text{si }}a{\text{ ne figure pas dans m}}\end{cases}}$.

La construction de cette table est donnée par :

### Fonction principale

Puis voici le pseudo-code de l'algorithme à proprement parler.

L'algorithme est similaire à l'algorithme naïf sauf que l'on décale de T[texte[j]] au lieu de décaler de 1, où j est l'indice dans le texte, aligné avec le dernier caractère de la fenêtre glissante.

### Exemples

**Cas où texte[j] est dans le motif**

Voici un exemple d'alignement :

La définition de la table T revient donc à considérer la dernière occurrence de la lettre à la position j (ici la lettre o) dans le mot motif, puis à aligner cette dernière occurrence avec l'actuel o dans le texte. Après l'affectation j := j + T[texte[j]], on obtient :

**Cas où texte[j] n'est pas dans le motif**

Voici un exemple d'alignement où la lettre sous le curseur dans le texte n'apparaît pas dans le motif (u n'apparaît pas dans le mot motif) :

Dans ce cas, T[texte[j]] = |m|. Dans l'exemple, on décale donc de |m| = 5 :

## Complexité

Dans la suite, on note ∑ l'alphabet, c'est-à-dire l'ensemble des lettres utilisées. L'algorithme de Horspool a une complexité spatiale $O(\left\vert \Sigma \right\vert )$ afin de stocker la table. Le pré-traitement (construction de la table) a une complexité en temps en $O(\left\vert m\right\vert +\left\vert \Sigma \right\vert )$. La recherche a une complexité en temps en $O(\left\vert m\right\vert *\left\vert texte\right\vert )$ dans les cas pathologiques et en $O(\left\vert texte\right\vert )$ en moyenne.

## Implémentation

Exemple d'implémentation en C.

