Algorithme de Boyer-Moore-Horspool

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

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.

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.

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, ${\displaystyle 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 :

${\displaystyle 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   

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.

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

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