Implémentation d'algorithmes classiques/Algorithmique du texte/Algorithme de Boyer-Moore

L'algorithme de Boyer-Moore recherche une sous-chaîne de caractères en commençant par la fin.

C

Note : la méthode de construction de la seconde table de correspondance (skip[]) dans cet exemple est plus lente que ce qu’elle 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 (et on peut tenir compte des remarques exprimées ci-dessus concernant sa taille, le bornage de ses valeurs possibles en fonction de la taille de l’alphabet et la limitation du prétraitement nécessaire à une partie seulement de la clé si celle-ci est très longue et dépasse certaines limites liées à la taille de l‘alphabet quand il est plus petit que la clé recherchée).

#include <string.h>
#include <limits.h>

static inline ssize_t max(ssize_t a, ssize_t b) { return a > b ? a : b; }

/* 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 inline 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;
} 

/* 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; /* Array of shifts with self-substring match check */
    size_t a, hpos;
    ssize_t occ[UCHAR_MAX + 1]; /* Array of last occurrence of each character */

    if (nlen > hlen || nlen <= 0 || !haystack || !needle)
        return NULL;

    /* Preprocess #1: init occ[] */
    /* Initialize the table to default value */
    for (a = UCHAR_MAX + 1; --a >= 0)
        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. */
    skip = (size_t *) malloc(nlen * sizeof(size_t));
    /* We should check here if skip is NULL (allocation failed) ! */
    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) {
                free(skip);
                return haystack + hpos;
            }
            --npos;
        }
        hpos += max(skip[npos], npos - occ[haystack[npos + hpos]]);
    }
    free(skip);
    return NULL;
}

Tout ou partie de cette page est issue de l'article Wikipédia « Algorithme de Boyer-Moore » dans sa version du 25 août 2010.