Algorithme de Boyer-Moore-Horspool

L'algorithme de Boyer-Moore-Horspool, parfois appelé algorithme de Horspool^[1] est un algorithme de recherche de sous-chaîne publié par Nigel Horspool en 1980^[2]. 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.

Rappel de l'algorithme naïf

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.

Article détaillé : Algorithme de recherche de sous-chaîne.

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

wikipedia
string

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 :

wikipedia
 string

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

wikipedia
 string
  string
   string

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.

wikipedia
string

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 :

wikipedia
      string

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^[3], 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^[3] 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 :

                                          j
                                          ↓
texte :       texte très long dans lequel on effectue une recherche d'un motif
motif :                               motif

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^[3]. 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^[4] 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 constructionTable(m)
        T := une table indexée par les lettres      
        pour toute lettre a
                T[a] := |m|
        pour k = 0 à |m| - 2
                T[m[k]] := |m| - 1 - k
        renvoyer T

Fonction principale

Puis voici le pseudo-code^[3] de l'algorithme à proprement parler.

fonction rechercher(m, texte)
       T := constructionTable(m)
       j := |m| - 1
       tant que j < |texte|
             signaler si texte[j - (|m|-1) .. j] = m
             j := j + T[texte[j]]

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 :

                                          j
                                          ↓
texte :       texte très long dans lequel on effectue une recherche d'un motif
motif :                               motif

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 :

                                             j
                                             ↓
texte :       texte très long dans lequel on effectue une recherche d'un motif
motif :                                  motif

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) :

                                                   j
                                                   ↓
texte :       texte très long dans lequel on effectue une recherche d'un motif
motif :                                        motif

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

                                                        j
                                                        ↓
texte :       texte très long dans lequel on effectue une recherche d'un motif
motif :                                             motif

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 \times \left\vert texte\right\vert )$ dans les cas pathologiques et en $O(\left\vert texte\right\vert )$ en moyenne^[5].

v · m Algorithmique du texte
Recherche de sous-chaîne	Algorithme de Knuth-Morris-Pratt Algorithme de Boyer-Moore Algorithme de Boyer-Moore-Horspool Algorithme de Raita Algorithme de Baeza-Yates-Gonnet Algorithme Z Algorithme de Rabin-Karp Algorithme d'Aho-Corasick
Alignement de chaînes	Algorithme de Needleman-Wunsch Algorithme de Smith-Waterman Transformée de Burrows-Wheeler
Mesure de similarité	Distance de Jaro-Winkler Distance de Levenshtein Distance de Hamming
Arbre des suffixes	Algorithmes de Weiner et de McCreight Algorithme d'Ukkonen Tableau des suffixes Tableau de Lyndon
Comparaisons	Plus longue sous-séquence commune Plus longue sous-chaîne commune Plus courte super-séquence commune