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.
Principe[modifier | modifier le code]
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[modifier | modifier le code]
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[modifier | modifier le code]
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[modifier | modifier le code]
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[modifier | modifier le 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[modifier | modifier le code]
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 :
![{\displaystyle T[a]=min(\{m\}\cup \{|m|-1-k,0\leq k\leq |m|-2{\text{ et }}m[k]=a\})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7252c31b00bacb21607f414adb707b5c3db0ef9)
.
![{\displaystyle T[a]={\begin{cases}|u|{\text{ si }}au{\text{ est suffixe de }}m{\text{, }}u{\text{ non vide et }}a{\text{ ne figure pas dans }}u\\|m|{\text{si }}a{\text{ ne figure pas dans m}}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/043ba2b166add389634f9a7be7a7b9d4e5db26d6)
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[modifier | modifier le code]
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.
Exemples[modifier | modifier le code]
Cas où texte[j] est dans le motif[modifier | modifier le code]
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[modifier | modifier le code]
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é[modifier | modifier le code]
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[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 - 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[modifier | modifier le code]
- 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".
- 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)
- Maxime Crochemore, Christophe Hancart, Thierry Lecroq, Algorithmique du texte, Vuibert informatique, p. 30
- Beauquier, Berstel, Chrétienne, Eléments d'algorithmique, 484 p. (lire en ligne), Section 10.2, p. 359
- (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 )
