Prérequis : dictionnaires , notion de complexité algorithmique
À l’issue de ce chapitre, vous saurez :
La recherche d’un motif dans un texte est un problème fondamental en informatique : elle intervient dans les éditeurs de texte (Ctrl+F), les moteurs de recherche, l’analyse de séquences ADN ou encore les outils comme
grep. Nous allons d’abord étudier une approche naïve, puis découvrir qu’en comparant le motif à l’envers, on peut aller beaucoup plus vite.
On dispose d’un texte de longueur \(n\) et d’un motif de longueur \(m\) (avec \(m \leqslant n\)). On cherche à déterminer si le motif apparaît dans le texte, et si oui, à quelles positions.
Par exemple, pour texte = 'abracadabra' et motif = 'bra', le motif apparaît aux positions 1 et 8 :
| a | b | r | a | c | a | d | a | b | r | a |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Pour résoudre ce problème, on va « glisser » le motif le long du texte. La question centrale est : de combien de positions avancer après chaque tentative ?
L’idée la plus simple consiste à tester chaque position de départ possible : pour chaque indice \(i\) de 0 à \(n - m\), on compare les caractères du motif un par un avec ceux du texte à partir de la position \(i\). Dès qu’un caractère ne correspond pas, on passe à la position suivante.
Illustrons avec texte = 'abracadabra' et motif = 'dab' :
i=0: abracadabra → 'a' ≠ 'd' → échec immédiat
dab
i=1: abracadabra → 'b' ≠ 'd' → échec immédiat
dab
i=2: abracadabra → 'r' ≠ 'd' → échec immédiat
dab
...on continue position par position...
i=6: abracadabra → 'd' = 'd', 'a' = 'a', 'b' = 'b' → trouvé !
dab
On avance toujours d’une seule position, même quand le premier caractère ne correspond pas : c’est ce qui rend cet algorithme lent.
def algo_naif(texte, motif):
"""Recherche toutes les occurrences de motif dans texte.
Paramètres
----------
texte : str – le texte dans lequel on effectue la recherche
motif : str – le motif recherché
Renvoie
-------
list[int] – la liste des indices de début de chaque occurrence
"""
n = len(texte)
m = len(motif)
indices = []
for i in range(n - m + 1):
trouvé = True
for j in range(m):
if texte[i + j] != motif[j]:
trouvé = False
break
if trouvé:
indices.append(i)
return indices
assert algo_naif("abracadabra", "bra") == [1, 8]
assert algo_naif("abracadabra", "dab") == [6]
assert algo_naif("aaaa", "aa") == [0, 1, 2]
assert algo_naif("abc", "abc") == [0]
assert algo_naif("abc", "xyz") == []
Remarques sur le code :
n - m + 1 (et non n - m) car la position \(n - m\) est la dernière position valide pour aligner le motif.trouvé est initialisée avant la boucle intérieure, pas à l’intérieur : c’est important pour qu’elle soit correctement réinitialisée à chaque nouvelle position.break pour interrompre la comparaison dès le premier caractère qui ne correspond pas.La boucle extérieure parcourt \(n - m + 1\) positions. Pour chacune, la boucle intérieure effectue au plus \(m\) comparaisons. La complexité dans le pire des cas est donc :
$$\mathcal{O}\left( (n - m + 1) \times m \right) \approx \mathcal{O}(n \times m)$$
Pour un motif court (\(m\) petit devant \(n\)), ce coût est proportionnel à \(n\). Il devient quadratique, en \(\mathcal{O}(n^2)\), quand \(m\) est de l’ordre de \(n\) (par exemple \(m = n/2\)).
Exemple de pire cas : chercher 'aab' dans 'aaaaaaaaa'. À chaque position, les deux premiers caractères correspondent ('a' = 'a', 'a' = 'a') avant d’échouer sur le troisième ('a' ≠ 'b'). On effectue presque \(3 \times (n - 2)\) comparaisons.
Nous allons voir qu’il est possible de faire beaucoup mieux en comparant le motif de droite à gauche.
Nous allons étudier une version simplifiée de l’algorithme de Boyer-Moore, proposée par Nigel Horspool en 1980. Cet algorithme repose sur deux idées :
Cherchons motif = 'dab' dans texte = 'abracadabra'.
Étape 1 – on aligne le motif en début de texte et on compare le dernier caractère du motif avec le caractère correspondant du texte :
abracadabra
dab
↑ on compare ici : 'r' ≠ 'b'
Échec. Le caractère du texte est 'r' : or 'r' n’apparaît nulle part dans le motif. On peut donc décaler le motif de toute sa longueur, soit 3 positions, sans risquer de rater une occurrence.
Étape 2 – on aligne le motif à la position 3 :
abracadabra
dab
↑ on compare ici : 'a' ≠ 'b'
Échec. Le caractère du texte est 'a' : or 'a' apparaît dans le motif en avant-dernière position. On décale d’une seule position pour aligner les deux 'a'.
Étape 3 – on aligne le motif à la position 4 :
abracadabra
dab
↑ on compare ici : 'd' ≠ 'b'
Échec. Le caractère du texte est 'd' : or 'd' apparaît dans le motif en première position (soit à distance 2 de la fin). On décale de 2 positions.
Étape 4 – on aligne le motif à la position 6 :
abracadabra
dab
↑ on compare : 'b' = 'b', puis 'a' = 'a', puis 'd' = 'd'
Tous les caractères correspondent de droite à gauche : le motif est trouvé à la position 6.
Bilan : pour trouver cette occurrence, on a testé 4 positions au lieu des 7 de l’algorithme naïf (positions 0 à 6). Pour parcourir tout le texte, la fonction du cours teste 5 fenêtres (0, 3, 4, 6 et 7) au lieu de 9. Le gain vient des « sauts » permis par le pré-traitement.
Pour chaque caractère \(c\) du motif (sauf le dernier), on calcule la distance entre sa dernière occurrence dans le motif (hors dernière position) et la fin du motif. Si un caractère n’est pas dans le motif, le décalage vaut \(m\) (la longueur du motif).
Formellement, pour un motif de longueur \(m\), si le caractère \(c\) apparaît à la position \(i\) (la plus à droite, hors dernière position) :
$$\text{décalage}(c) = m - 1 - i$$
On stocke ces valeurs dans un dictionnaire.
Exemple avec motif = 'dab' (longueur 3) :
| Caractère | Dernière position (hors fin) | Décalage |
|---|---|---|
'd' |
0 | 3 − 1 − 0 = 2 |
'a' |
1 | 3 − 1 − 1 = 1 |
'b' |
(dernière position, exclue) | — |
| tout autre | (absent du motif) | 3 |
Le dictionnaire renvoyé est {'d': 2, 'a': 1}.
Exemple avec motif = 'maman' (longueur 5) :
Le caractère 'm' apparaît aux positions 0 et 2 : on garde la plus à droite (2), ce qui donne un décalage de \(5 - 1 - 2 = 2\). Le caractère 'a' apparaît aux positions 1 et 3 : on garde la position 3, décalage \(5 - 1 - 3 = 1\).
Le dictionnaire renvoyé est {'m': 2, 'a': 1}.
def pre_traitement(motif):
"""Construit la table de décalages pour Boyer-Moore-Horspool.
Paramètres
----------
motif : str – le motif recherché
Renvoie
-------
dict – dictionnaire {caractère: décalage}
"""
m = len(motif)
décalages = {}
for i in range(m - 1): # on parcourt le motif sauf le dernier caractère
décalages[motif[i]] = m - 1 - i
return décalages
assert pre_traitement("dab") == {'d': 2, 'a': 1}
assert pre_traitement("maman") == {'m': 2, 'a': 1}
assert pre_traitement("abracadabra") == {'a': 3, 'b': 2, 'r': 1, 'c': 6, 'd': 4}
Pourquoi exclure le dernier caractère ? Parce que si le caractère du texte aligné avec la fin du motif est identique au dernier caractère du motif, on ne veut pas décaler de 0 (ce qui ferait boucler). On veut plutôt le décalage vers la prochaine occurrence de ce caractère plus à gauche dans le motif, ou \(m\) s’il n’apparaît pas ailleurs.
def recherche_boyer_moore(texte, motif):
"""Recherche toutes les occurrences de motif dans texte
avec l'algorithme de Boyer-Moore-Horspool.
Paramètres
----------
texte : str – le texte dans lequel on effectue la recherche
motif : str – le motif recherché
Renvoie
-------
list[int] – la liste des indices de début de chaque occurrence
"""
n = len(texte)
m = len(motif)
décalages = pre_traitement(motif)
indices = []
i = 0 # position de début de la fenêtre dans le texte
while i <= n - m:
j = m - 1 # on compare de droite à gauche
while j >= 0 and texte[i + j] == motif[j]:
j -= 1
if j < 0: # tous les caractères correspondent
indices.append(i)
i += 1 # on avance d'une position pour chercher les suivantes
else:
# on décale selon le caractère du texte aligné avec la fin du motif
c = texte[i + m - 1]
if c in décalages:
i += décalages[c]
else:
i += m
return indices
assert recherche_boyer_moore("abracadabra", "dab") == [6]
assert recherche_boyer_moore("abracadabra", "bra") == [1, 8]
assert recherche_boyer_moore("abracadabra", "abra") == [0, 7]
assert recherche_boyer_moore("abracadabra", "obra") == []
assert recherche_boyer_moore("aaaa", "aa") == [0, 1, 2]
assert recherche_boyer_moore("abc", "abc") == [0]
assert recherche_boyer_moore("bonjour", "papa") == []
Points importants du code :
i représente la position de début de la fenêtre de comparaison.while j >= 0.j < 0), on avance d’une position pour trouver les éventuelles occurrences suivantes.texte[i + m - 1]), conformément à la règle de Horspool.'baa' dans 'aaaaaa' : le décalage vaut toujours 1 et chaque fenêtre est comparée en entier).On peut comparer les deux algorithmes avec le module timeit sur un texte long :
import timeit
texte = open("un_fichier.txt").read() # un texte de plusieurs milliers de caractères
motif = "algorithme"
t_naif = timeit.timeit(lambda: algo_naif(texte, motif), number=1000)
t_boyer = timeit.timeit(lambda: recherche_boyer_moore(texte, motif), number=1000)
print(f"Naïf : {t_naif:.4f} s")
print(f"Boyer-Moore : {t_boyer:.4f} s")
L’appel timeit.timeit(f, number=k) exécute k fois la fonction sans paramètre f et renvoie la durée totale, en secondes. L’expression lambda: algo_naif(texte, motif) fabrique justement cette fonction sans paramètre, qui lance la recherche.
Plus le motif est long et l’alphabet varié, plus l’avantage de Boyer-Moore-Horspool est marqué.
n - m + 1 et non n - m ?
n - m est la dernière position valide où le motif de longueur m peut commencer dans le texte de longueur n. Avec range(n - m), cette position ne serait jamais testée et on raterait un motif situé à la toute fin du texte."aab" dans "aaaaaaa"), chaque position échoue au dernier caractère, ce qui donne environ n × m comparaisons. Ce coût est quadratique quand m est de l'ordre de n, par exemple m = n/2 ; pour un motif court, il reste proportionnel à n.pre_traitement("dab") et comment l’interpréter ?
{'d': 2, 'a': 1}. Si, lors d'un échec, le caractère du texte aligné avec la fin du motif est 'd', on décale de 2 positions ; si c'est 'a', on décale de 1. Un caractère absent du dictionnaire (comme 'r') provoque un décalage maximal de 3 (la longueur du motif).'a') : les décalages sont presque toujours de 1 et on retombe sur un parcours position par position, comme dans l'algorithme naïf.grep, Ctrl+F).