Accueil🇫🇷Chercher

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.

Illustration de la recherche de la sous-chaîne "long des" dans la première strophe du poème Chanson d'automne de Paul Verlaine.

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 :

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, . 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 :

.


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.

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 afin de stocker la table. Le pré-traitement (construction de la table) a une complexité en temps en . La recherche a une complexité en temps en dans les cas pathologiques et en en moyenne[5].

Implémentation

Exemple d'implémentation en C.

#define ALPHABET_SIZE   256     // taille de l'alphabet ASCII
/**
 * Implémentation de Boyer-Moore-Horspool
 *
 * Note : retourne directement la position du premier pattern trouvé dans text, sinon -1
 */
int bmh(char *text, char *pattern)
{
        unsigned int skip_table[ALPHABET_SIZE];
        ssize_t tsize, psize;
        int i;
        tsize = strlen(text);
        psize = strlen(pattern);
        /* pré-traitement */
        /** remplir la table avec la valeur de saut maximum */
        for (i = 0; i < ALPHABET_SIZE; i++)
                skip_table[i] = psize;
        /** puis calculer pour chaque caractère de pattern le saut */
        for (i = 0; i < psize - 1; i++)
                skip_table[(int) pattern[i]] = psize - i - 1;
        /* recherche */
        i = 0;
        while (i <= tsize - psize) {
                if (text[i + psize - 1] == pattern[psize - 1])
                        if (memcmp(text + i, pattern, psize - 1) == 0)
                                return i;
                /* si les deux caractères comparés sont différents, 
                sauter en utilisant la valeur de la table de saut à
                l'index du caractère de text */
                i += skip_table[(int) text[i + psize - 1]];
        }
        return -1;
}

Références

  1. Dans leur livre Elements d'algorithmique, Beauquier, Berstel et Chrétienne présentent cet algorithme dans la section 10.2.1 p. 358 intitulée "Algorithme de Horspool", bien qu'ils disent que cet algorithme s'appelle "algorithme de Boyer-Moore-Horspool".
  2. R. N. Horspool, « Practical fast searching in strings », Software: Practice and Experience, vol. 10, no 6,‎ , p. 501–506 (DOI 10.1002/spe.4380100608, S2CID 6618295, CiteSeerx 10.1.1.63.3421)
  3. Maxime Crochemore, Christophe Hancart, Thierry Lecroq, Algorithmique du texte, Vuibert informatique, p. 30
  4. Beauquier, Berstel, Chrétienne, Eléments d'algorithmique, 484 p. (lire en ligne), Section 10.2, p. 359
  5. (en) Ricardo A. Baeza-Yates et Mireille Régnier, « Average running time of the Boyer-Moore-Horspool algorithm », Theoretical Computer Science, vol. 92, no 1,‎ , p. 19–31 (ISSN 0304-3975, DOI 10.1016/0304-3975(92)90133-Z, lire en ligne, consulté le )
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.