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.

Et maintenant ?

Questions proches

← Toutes les questions-réponses