# Boyer-Moore ## Introduction La méthode `index` qui s'applique aux chaînes de caractères Python permet de renvoyer l'indice d'une sous-chaîne (motif) dans un texte. L'objectif de cet activité est d'analyser deux algorithmes possibles pour cette fonction : - la solution naïve - une solution optimisée : l'algorithme de Boyer-Moore qui met en oeuvre un mécanisme de précalcul. L'idée centrale du **précalcul** est d'éviter les calculs répétitifs (à chaque itération, afin de réduire la complexité (en temps de calcul) aux détriment (souvent) d'une plus grande consommation mémoire. ## La solution naïve ```python def nSearch(text: str, pattern: str) -> int: """ Recherche un motif / une sous-chaîne dans un texte @param text le texte @param pattern le motif recherché @return l'indice du premier caractère du motif dans le texte ou -1 si non trouvé >>> nSearch("Example", "Ex") 0 >>> nSearch("Example", "ple") 4 >>> nSearch("Example", "am") 2 >>> nSearch("Example", "not") -1 >>> nSearch("Exam", "Example") -1 """ global cplx; cplx = 0 #calcul du coût end = len(text) - len(pattern) + 1 match = False; i = 0 while not match and i < end: match = True; j = 0 while match and j != len(pattern): cplx += 1 #calcul du coût if text[i + j] != pattern[j]: match = False j += 1 i += 1 return i - 1 if match else -1 ``` - Tester puis expérimenter cette fonction ; après exécution, le coût est enregistré dans la variable `cplx`. - Faire la trace du programme avec par exemple le troisième test unitaire. - Déterminer quels sont les meilleurs et pire cas. - Déterminer la complexité de cet algorithme dans les meilleurs et pire cas en fonction de `n` (la longueur du texte) et de `m` la longueur du motif). ## L'algorithme de Boyer-Moore simplifié (Horspool) ### Principe de fonctionnement Pour comprendre le principe de cet algorithme, se référer à la vidéo du [cours d'Erwan Demerville](https://nsi.erwandemerville.fr/terminale/recherche_textuelle/cours/) ### Précalcul Soit "amar" le motif recherché. Construire une table de décalage : pour chaque caractère du motif, relever l'indice inversé (de droite à gauche — cf poids des bits) de sa dernière occurence. | motif | a | **m** | **a** | ~~r~~ | | ------- | - | ----- | ----- | ----- | | indices | 3 | **2** | **1** | ~~0~~ | Table de décalage (offsets) : { "a": 1, "m": 2 } — l'offset du dernier caractère du motif est toujours 0. ### Déroulement de l'algorithme Soit le texte : "loren irsum doler amar…" l'algorithme se déroule comme suit : | indices | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | | ------- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | | texte | l | o | r | u | n | | i | r | s | u | m | | d | o | l | a | r | | a | m | a | r | | motif | a | m | a | r | | | | | | | | | | | | | | | | | | | | motif | | | | | a | m | a | r | | | | | | | | | | | | | | | | motif | | | | | | | | a | m | a | r | | | | | | | | | | | | | motif | | | | | | | | | | a | m | a | r | | | | | | | | | | | motif | | | | | | | | | | | | | | a | m | a | r | | | | | | | motif | | | | | | | | | | | | | | | | a | m | a | r | | | | | motif | | | | | | | | | | | | | | | | | a | m | a | r | | | | motif | | | | | | | | | | | | | | | | | | | a | m | a | r | - À la première itération, il y a non-correspondance à l'indice 3 ; comme il n'y a pas de "u" (`texte[3]`) dans le motif, la fenêtre de comparaison est décalée après le u. - À la deuxième itération, il y a correspondance à l'indice 7, mais pas à l'indice 6 ; comme il n'y a pas de "i" dans le motif, la fenêtre est décalée après cette lettre (et non pas après le "r"). - À la troisième itération, il y a non-correspondance à l'indice 10, mais "m" est dans le motif et la fenêtre est décalée de 2 (cf table de décalage) pour aligner la lettre du motif à celle du texte. - À la quatrième itération, il y a correspondance aux indices 16 et 15. - À la cinquième itération, il y a non-correspondance à l'indice 18 - À la sixième itération, il y a non-correspondance à l'indice 19. - À la septième itération, il y a correspondance pour toutes les lettres du motif. Au final, il y a eu 12 comparaisons aux indices 3, 7, 6, 10, 16, 15, 18, 19 puis 21, 20, 19 et 18 (toujours de droite à gauche). ### Code de la fonction de recherche ```python from typing import Dict def bmhSearch(text: str, pattern: str) -> int: """ Recherche un motif / une sous-chaîne dans un texte @param text le texte @param pattern le motif recherché @return l'indice du premier caractère du motif dans le texte ou -1 si non trouvé >>> bmhSearch("Example", "Ex") 0 >>> bmhSearch("Example", "ple") 4 >>> bmhSearch("Example", "am") 2 >>> bmhSearch("Example", "not") -1 >>> bmhSearch("Exam", "Example") -1 """ def getOffsets(pattern: str) -> Dict: #sous-fonction de précalcul table = {} for i in range(len(pattern) - 1): #sauf la dernière lettre letter = pattern[i] table[letter] = len(pattern) - i - 1 return table global cplx; cplx = len(pattern) - 1 #calcul du coût offsets = getOffsets(pattern) #pré-calcul match = False; i = 0 while not match and i < len(text) - len(pattern) + 1: match = True; j = len(pattern) - 1 while match and j >= 0: #parcours du motif de droite à gauche cplx += 1 #calcul du coût if text[i + j] != pattern[j]: match = False letter = text[i + j] #lettre qui ne correspond pas if letter in offsets.keys(): #alignement du motif i += offsets[letter] else: #alignement impossible i += j + 1 j -= 1 return i if match else -1 ``` ### Expérimentation Expérimenter la fonction, et comparer son coût à celui de l'implémentation naïve. ### Questions de réflexion - Faire une trace de la fonction `getOffsets` avec le motif "morem". Expliquer la formule qui détermine l'indice (de droite à gauche) : `len(pattern) - i - 1`. - Faire une trace de la fonction `bmhSearch` à partir du texte et du motif de l'exemple. Expliquer pourquoi l'instruction en cas d'alignement impossible est `i += j + 1` et non pas `i += len(pattern)`. - Indiquer le pire cas et sa complexité.