Algorithme de Boyer-Moore-Horspool
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’algorithme 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
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
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é
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
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;
}
Portail de l'informatique théorique