Algorithme de Boyer-Moore-Horspool

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme de Boyer-Moore-Horspool ou Horspool est un algorithme de recherche de sous-chaîne publié par Nigel Horspool en 1980.

Il consiste en une simplification de l'agorithme de Boyer-Moore qui ne garde que la première table de saut.

On notera T le texte de recherche, P la sous-chaîne recherchée et ∑ l'alphabet.

Description[modifier | modifier le code]

L'algorithme utilise un pré-traitement de P 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.

Exemple[modifier | modifier le code]

Si P="string" et que le texte est T="wikipedia" :

  • à la première occurrence, le dernier caractère de P est comparé à sa position dans T, soit 'g' vs 'e'. On cherche la valeur de 'e' dans la table de saut, et comme 'e' n'existe pas dans P la valeur retournée est |P|, soit 6.
  • à la seconde occurrence, le curseur est déplacé de 6 et déborde de T, la recherche s'arrete ici et P n'a pas été trouvé dans T

Ce cas extrême est intéressant car un seul caractère de T a été lu.

Complexité[modifier | modifier le code]

En espace Horspool a une complexité O(|∑|).

Le pré-traitement a une complexité en temps en O(|P|+|∑|).

La recherche a une complexité en temps en O(|T|*|P|) dans les cas pathologiques et en O(|T|) en moyenne.

Implémentation[modifier | modifier le code]

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 - 2) == 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;
}