|
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. PrincipeExpliquons le principe sur la recherche du motif m Rappel de l'algorithme naïfOn 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 wikipedia string Mais on voit que tous ces décalages mèneront à un échec : wikipedia string string string AméliorationDans 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 wikipedia string Ces deux caractères étant différents, on cherche donc à savoir de combien il faut décaler le texte. Comme wikipedia
string
L'algorithme termine en déclarant que IdéeDans l'exemple précédent, le caractère Pseudo-codeDans 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 occurrenceL'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 : .
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 principalePuis 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. ExemplesCas où texte[j] est dans le motifVoici 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 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 motifVoici un exemple d'alignement où la lettre sous le curseur dans le texte n'apparaît pas dans le 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é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émentationExemple 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
|
![{\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)
