Principe de l’algorithme
Cet algorithme utilise un pré-traitement du motif m à chercher dans le texte t afin d’accélérer la recherche d’occurrences.
Ce pré-traitement consiste à construire une ‘table de décalage’ qui pour chaque caractère c du motif m associe l’index de chacun des caractères qui le précèdent dans le motif. Si un caractère existe en plusieurs exemplaires, c’est la position du plus près qui est conservée.
Il s’agit ensuite de parcourir le texte en décalant le motif, mais contrairement à l’algorithme naïf qui ne décale le motif que d’une position à chaque itération, il s’agira ici de le décaler de plusieurs positions dans certains cas.
La comparaison des caractères du motif et du texte se fait à partir du dernier caractère du motif – donc dans le sens inverse de la lecture :
- tant que le caractère du motif est identique à celui du texte, on continue la comparaison.
- Si on atteint le premier caractère du motif, il y a une occurrence du motif dans le texte.*
- Sinon : si le caractère du motif situé à l’index i diffère de celui du texte et que le caractère du texte en question ne figure pas dans la liste des caractères du motif situés avant l’index i, alors le motif sera décalé vers la gauche d’une valeur égale à l’index i et à laquelle on ajoute 1.
- Sinon : si le caractère du motif situé à l’index i diffère de celui du texte et que le caractère du texte en question figure à l’index j dans la liste des caractères du motif situés avant l’index i, alors le motif sera décalé vers la gauche d’une valeur égale à l’index i et à laquelle on retire la valeur de l’index j.
- La lettre ‘m’ du motif ‘commande’ située à l’index 2 ne correspond pas à la lettre du texte qui est un ‘a’ et la lettre ‘a’ ne figure pas dans les lettres du motif situées avant le ‘m’ de l’index 2.
Donc le motif est décalé de la valeur de l’index i plus 1, soit 2 +1 = 3 caractères.
- Le décalage est maximal lorsque la différence porte sur la dernière lettre du motif, c’est à dire celle qui comparée en premier. Le décalage sera égal à la longueur du motif.
Par exemple si le motif était ‘commando’, le motif serait décalé de 8 caractères, de telle sorte que le ‘c‘ du motif ferait face au ‘s‘ de ‘amandes‘.
- Le décalage est minimal lorsque la différence porte sur la première lettre du motif seulement, c’est à dire celle qui sera comparée en dernier. Le décalage vaut 1 dans ce cas.
Par exemple si le motif était ‘bande’, avec le ‘b’ de ‘bande’ positionné sous le ‘m’ de ‘amandes’).
- La lettre ‘s’ du motif ‘extension’ située à l’index 5 ne correspond pas à la lettre du texte qui est un ‘t’ et la lettre ‘t’ figure dans les lettres du motif situées avant le ‘s’, à l’index 2.
Donc le motif est décalé de la valeur de l’index i moins 2, soit 5 – 2 = 3 caractères.
- Le décalage est maximal lorsque la lettre qui diffère est la dernière du motif et lorsque la lettre du texte correspond à la première du motif.
Par exemple si le dernier ‘e’ du motif ‘nouvelle’ se trouve en face le ‘n’ de ‘communications’.
- Le décalage est minimal lorsque la lettre du texte qui diffère se trouve être celle qui précède immédiatement le lettre du motif.
Par exemple si le ‘s’ du motif ‘actions’ se trouve en face du ‘n’ du mot ‘communications’ du texte.
Construction d’une table de décalage
Étude d’un exemple : pour le motif « abracadabra » la table est la suivante :
Table de décalage de 'abracadabra'
| a | b | r | c | d | |
|---|---|---|---|---|---|
| a : 0 | |||||
| b : 1 | 0 | ||||
| r : 2 | 0 | 1 | |||
| a : 3 | 0 | 1 | 2 | ||
| c : 4 | 3 | 1 | 2 | ||
| a : 5 | 3 | 1 | 2 | 4 | |
| d : 6 | 5 | 1 | 2 | 4 | |
| a : 7 | 5 | 1 | 2 | 4 | 6 |
| b : 8 | 7 | 1 | 2 | 4 | 6 |
| r : 9 | 7 | 8 | 2 | 4 | 6 |
| a : 10 | 7 | 8 | 9 | 4 | 6 |
Le principe est le suivant :
- si en face du dernier ‘a’ du motif qui occupe l’index 10 (donc on écrira sur la ligne numérotée 10 du tableau), on trouve un ‘r’ dans le texte, à quel index le plus proche de ce ‘a’ se trouve le ‘r’ dans le motif ? Réponse : à l’index 9.
- Et si maintenant à la place de ‘a’ toujours, se trouve un ‘b’ dans le texte, le ‘b’ le plus proche de ce ‘a’ dans le motif est à l’index 7.
- Et ainsi de suite pour le ‘c’ et le ‘d’.
- Puis on passe au ‘r’ en avant-dernière position dans le motif, donc qui occupe l’index 9.
- Et ainsi de suite jusqu’au premier ‘b’ du motif qui occupe l’index 1. Pour le premier ‘a’ du motif qui occupe la ligne 0 du tableau, comme il n’est précédé d’aucune lettre on laisse vide toutes les cases de la ligne 0.
Construire les tables de décalages pour les motifs suivants : « banane » et « chercher »