Pourquoi prétraiter un motif avant une recherche de type Horspool ?
Réponse courte
Le prétraitement construit une table de décalages à partir du motif. Après une comparaison ratée, Horspool l’utilise pour déplacer la fenêtre de plusieurs positions sûres au lieu de recommencer au départ suivant.
Comprendre
Construire la table avant la recherche
Horspool prépare une table qui associe à chaque caractère un décalage. Pour la construire, on parcourt le motif sauf son dernier caractère et on retient, pour chaque lettre, sa position la plus à droite dans cette partie. Le décalage correspond à la distance entre cette position et le bord droit du motif. Les caractères absents reçoivent le décalage égal à la longueur du motif.
Utiliser l’information d’un échec
Pendant la recherche, les caractères d’une fenêtre sont comparés de droite à gauche. Si la comparaison échoue, on regarde le caractère situé au bord droit de la fenêtre dans le texte ; la table donne alors le nombre de positions à avancer. Cette valeur évite certains départs où le caractère observé ne pourrait pas s’aligner avec une lettre compatible du motif.
Garantir la progression
La dernière case du motif est exclue du calcul de la table : sa distance au bord droit serait nulle et risquerait de laisser la fenêtre immobile. Les décalages préparés sont donc positifs. Le prétraitement est fait une fois par motif et peut être réutilisé pour toutes les fenêtres, ce qui devient intéressant quand le texte est long ou le même motif recherché plusieurs fois.
Exemples
- Pour le motif CHAT, de longueur 4, la table donne C : 3, H : 2, A : 1 et 4 pour tout caractère absent de CHA, y compris T.
- Pour ABACA, la partie utilisée est ABAC : A reçoit 2, B reçoit 3, C reçoit 1 et les autres caractères reçoivent 5.
- Si le bord droit de la fenêtre contient Z et Z n’apparaît pas avant la dernière lettre du motif CHAT, la fenêtre avance de 4 positions.
Pièges fréquents
- Inclure la dernière lettre dans la table peut lui associer un décalage nul ; la recherche ne progresserait alors pas.
- Retenir la première occurrence d’une lettre au lieu de la plus à droite peut produire un décalage inadéquat et faire sauter un départ utile.
Pourquoi ça marche
La table exploite les lettres du texte et du motif pour écarter des alignements qui ne peuvent pas correspondre.
