Algorithme de boyer-moore

L'algorithme de Boyer-Moore est un algorithme de recherche de sous-chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977.

Présentation

L'algorithme de Boyer-Moore pré-traite la sous-chaîne (c'est-à-dire la chaîne recherchée), et non pas le texte (c'est-à-dire la chaîne dans laquelle la recherche est effectuée), à l'inverse de certains algorithmes, qui amortissent le coût du prétraitement du texte en effectuant de très nombreuses recherches répétitives. Le coût d'exécution de l'algorithme de Boyer-Moore peut être sub-linéaire, c'est-à-dire qu'il n'a pas besoin de vérifier chacun des caractères du texte, mais peut au contraire sauter certains d'entre eux. En général, l'algorithme devient plus rapide lorsque la longueur de la sous-chaîne s'allonge. Cette efficacité provient du fait que, pour chaque tentative infructueuse de correspondance entre les deux chaînes (texte et sous-chaîne), il utilise les informations déduites de cet échec pour éliminer le plus grand nombre possible de positions à vérifier.

Fonctionnement de l'algorithme

Beaucoup de personnes sont surprises par l'algorithme de Boyer-Moore lorsqu'elles le découvrent pour la première fois, car il effectue la vérification, c'est-à-dire qu'il tente d'établir la correspondance de la sous-chaîne à une certaine position, à l'envers. Par exemple, s'il commence la recherche de la sous-chaîne WIKIPEDIA au début d'un texte, il vérifie d'abord la neuvième position en regardant si elle contient un A. Ensuite, s'il a trouvé un A, il vérifie la huitième position pour regarder si elle contient le dernier I de la sous-chaîne, et ainsi de suite jusqu'à ce qu'il ait vérifié la première position du texte pour y trouver un W.

La raison pour laquelle l'algorithme de Boyer-Moore utilise cette approche à rebours est plus claire si l'on considère ce qui se produit quand la vérification échoue, par exemple si au lieu de trouver un A en neuvième position, un X est lu. Le X n'apparaît nulle part dans la sous-chaîne WIKIPEDIA, ce qui signifie qu'aucune correspondance avec la sous-chaîne n'existe au tout début du texte, ainsi que dans les huit positions qui la suivent. Après la vérification d'un seul caractère, l'algorithme est capable de passer ces huit caractères et de rechercher le début d'une correspondance à partir de la dixième position dans le texte, juste après le X.

Ce principe de fonctionnement à rebours explique la quelque peu contre-intuitive affirmation disant que plus la sous-chaîne est longue, et plus l'algorithme est efficace pour la trouver.

Pré-traitement

L'algorithme précalcule deux tableaux pour traiter l'information qu'il obtient pour chaque vérification ayant échoué. La première indique le nombre de positions à sauter avant de reprendre la recherche, en se basant sur l'index du caractère qui a provoqué l'échec de la vérification. La seconde donne une information similaire, basée sur le nombre de caractères vérifiés avec succès avant que la vérification échoue. Comme ces deux tableaux indiquent le nombre de positions qu'il faut sauter dans le texte avant de poursuivre la recherche, ils sont parfois appelés "tables de sauts".

Première table

Le premier tableau est facile à remplir : démarrer au dernier caractère de la sous-chaîne avec le compteur à 0, et aller en direction du premier caractère. Pour chaque déplacement vers la gauche, incrémenter le compteur, et si le caractère à la position courante n'est pas déjà dans le tableau, l'ajouter avec la valeur actuelle du compteur. Tous les autres caractères reçoivent un nombre égal à la longueur de la sous-chaîne.

Exemple : avec la sous-chaîne WIKIPEDIA, le premier tableau est rempli comme suit (pour plus de clarté, les entrées sont données dans l'ordre où elles sont ajoutées dans le tableau) :

Le lecteur attentif remarquera que le A, le dernier caractère de la sous-chaîne, n'a pas été ajouté dans le tableau. La raison est que l'algorithme utilise le tableau après avoir trouvé un caractère qui ne correspond pas. Le tableau lui indique le nombre de positions vers l'avant que l'algorithme doit sauter avant que ce caractère puisse théoriquement correspondre dans le texte. Par exemple, si en vérifiant la neuvième position du texte, l'algorithme trouve un I plutôt qu'un A, cela indiquerait que la prochaine correspondance potentielle pourrait être trouvée une position plus loin vers l'avant, et que la dixième position doit être vérifiée pour y chercher un A. S'il s'agit d'un A, soit l'algorithme le trouve dans la dernière position, et dans ce cas, la vérification est un succès, soit la dernière position a déjà été vérifiée. Dans le second cas, il n'existe aucun endroit dans le reste de la sous-chaîne où le A peut correspondre. De ce fait, aucune correspondance n'est possible jusqu'à ce que l'algorithme cherche complètement au-delà de la position du A.

Seconde table

Le second tableau est sensiblement plus compliqué à calculer : pour chaque valeur de N inférieure à la longueur de la sous-chaîne, il faut calculer le motif composé des N derniers caractères de la sous-chaîne, précédé d'un caractère qui ne correspond pas. Puis, il faut trouver le plus petit nombre de caractères pour lequel le motif partiel peut être décalé vers la gauche avant que les deux motifs ne correspondent. Par exemple, pour la sous-chaîne ANPANMAN, le tableau est rempli de cette manière :

Il est plus facile de voir comment sont déterminés les nombres de la colonne Décalage en regardant le tableau qui suit. Il montre chaque motif, décalé d'autant de positions vers la gauche que nécessaire pour correspondre avec la sous-chaîne. Le caractère ne devant pas correspondre choisi est la minuscule de ce caractère ; par exemple, le motif mAN peut être lu comme « la chaîne AN, précédée par n'importe quel autre caractère, excepté un M. »

      ANPANMAN
      --------
            n  1
    aN         8
        mAN    3
    nMAN       6
   aNMAN       6
  pANMAN       6
 nPANMAN       6
aNPANMAN       6

Performances

Meilleur cas

Dans le cas le plus favorable, les performances de l'algorithme sont N/M, pour un texte de N caractères et une sous-chaîne de M caractères. Dans ce meilleur cas, seul un caractère sur M doit être vérifié. Ainsi, plus la sous-chaîne est longue, et plus l'algorithme est efficace pour la trouver.

Pire cas

Dans le pire cas, les performances de l'algorithme pour trouver toutes les correspondances est de l'ordre de N*M. Ce pire cas se produit quand la sous-chaîne consiste en une répétition d'un unique caractère, et que le texte correspond à la répétition de M-1 fois ce même caractère, précédé par un seul autre caractère différent. Dans ce cas de figure, l'algorithme doit vérifier N-M+1 décalages différents dans le texte pour chaque correspondance. Or, chacune de ces vérifications nécessite M comparaisons.

Le pire cas pour établir s'il y a correspondance ou non requiert environ 3*N comparaisons. La preuve est due à Richard Cole.^[1]

Exemple d'implementation

Voici un exemple d'implementation de l'algorithme Boyer-Moore en C.

Note : La méthode de construction d'une bonne table de correspondance (skip[]) dans cet exemple est plus lent que ce qu'il devrait être (pour la simplicité de l'implémentation). Cela ne donne donc pas une comparaison valable avec les autres algorithmes, si vous cherchez à comparer leur vitesse. Une méthode plus rapide doit être utilisée à la place.

#include <string.h>
#include <limits.h>
 
/* This helper function checks, whether the last "portion" bytes
 * of "needle" (which is "nlen" bytes long) exist within the "needle"
 * at offset "offset" (counted from the end of the string),
 * and whether the character preceding "offset" is not a match.
 * Notice that the range being checked may reach beyond the
 * beginning of the string. Such range is ignored.
 */
static int boyermoore_needlematch
    (const unsigned char* needle, size_t nlen, size_t portion, size_t offset)
{
    ssize_t virtual_begin = nlen-offset-portion;
    ssize_t ignore = 0;
    if (virtual_begin < 0)
    {
        ignore = -virtual_begin;
        virtual_begin = 0;
    }
 
    if (virtual_begin > 0 && needle[virtual_begin - 1] == needle[nlen-portion - 1])
        return 0;
 
    return
        memcmp(needle + nlen - portion + ignore,
               needle + virtual_begin,
               portion - ignore) == 0;
} 
 
static size_t max(ssize_t a, ssize_t b) { return a>b ? a : b; }
 
/* Returns a pointer to the first occurrence of "needle"
 * within "haystack", or NULL if not found.
 */
const unsigned char* memmem_boyermoore
    (const unsigned char* haystack, size_t hlen,
     const unsigned char* needle,   size_t nlen)
{
    size_t skip[nlen]; /* Array of shifts with self-substring match check */
    ssize_t occ[UCHAR_MAX + 1]; /* Array of last occurrence of each character */
    size_t a, hpos;
 
    if (nlen > hlen || nlen <= 0 || !haystack || !needle)
        return NULL;
 
    /* Preprocess #1: init occ[]*/
 
    /* Initialize the table to default value */
    for (a = 0; a < UCHAR_MAX + 1; ++a)
        occ[a] = -1;
 
    /* Then populate it with the analysis of the needle */
    /* But ignoring the last letter */
    for (a = 0; a < nlen - 1; ++a)
        occ[needle[a]] = a;
 
    /* Preprocess #2: init skip[] */  
    /* Note: This step could be made a lot faster.
     * A simple implementation is shown here. */
    for (a = 0; a < nlen; ++a)
    {
        size_t value = 0;
        while (value < nlen && !boyermoore_needlematch(needle, nlen, a, value))
            ++value;
        skip[nlen - a - 1] = value;
    }
 
    /* Search: */
    for (hpos = 0; hpos <= hlen - nlen; )
    {
        size_t npos = nlen - 1;
        while (needle[npos] == haystack[npos + hpos])
        {
            if (npos == 0)
                return haystack + hpos;
            --npos;
        }
        hpos += max(skip[npos], npos - occ[haystack[npos + hpos]]);
    }
 
    return NULL;
}

Voir aussi

Articles connexes

• Algorithme de recherche de sous-chaîne
• Algorithme de Knuth-Morris-Pratt
• Algorithme de Rabin-Karp

Liens externes

• Animation de l'algorithme de Boyer-Moore ;
• (en) Analyse, bibliographie et animation de l'algorithme de Boyer-Moore ;
• (en) Un exemple de l'algorithme de Boyer-Moore sur la page Internet de J. Strother Moore, co-inventeur de l'algorithme.

Référence

• Portail de l’informatique