NSI Terminale
fonction recherche_naive: texte, motif
ENTRÉES :
texte = texte de n caractères
motif = motif de p caractères ( p < n )
SORTIE :
le tableau des occurrences du motif dans le texte, c'est à dire le tableau du (ou des) indice(s) dans le texte où a été trouvé le motif
Tableau vide si le motif n'a pas été trouvé
occurrences ← tableau vide
pour i variant de l'indice 0 à l'indice n - p :
j ← 0
tant que j < p et motif[j] = texte[i+j] :
j ← j + 1
si j = p :
occurrences ← i
renvoyer occurrences
fonction decalages: motif
ENTRÉE :
motif = chaîne de p caractères
SORTIE :
le dictionnaire associant à chaque caractère de la chaîne son décalage par rapport à la fin de la chaîne
dec ← dictionnaire vide
pour i variant de l'indice 0 à l'indice p - 2 : // on exclut le dernier caractère
dec[motif[i]] = longueur du motif - i - 1
fonction recherche_BMH: texte, motif
ENTRÉES :
texte = texte de n caractères
motif = motif de p caractères ( p < n )
SORTIE :
le tableau des occurrences du motif dans le texte, c'est à dire le tableau du (ou des) indice(s) dans le texte où a été trouvé le motif
Tableau vide si le motif n'a pas été trouvé
occurrences ← tableau vide
dec ← decalages(motif) // appel à la fonction de construction du dictionnaire des décalages
i ← 0
tant que i <= n - p :
j ← p - 1 // indice du dernier caractère du motif
tant que j >= 0 et que texte[i + j] = motif[j] :
j ← j - 1
si j = - 1 : // on a parcouru tout le motif, alors on l'a trouvé dans le texte !
occurrences ← i
i ← i + longueur du motif
sinon si texte[i+j] = motif[p-1] // 1er cas : caractère = dernier caractère du motif
i ← i + longueur du motif
sinon si texte[i+j] n'est pas dans motif : // 2ème cas : caractère pas dans le motif
i ← i + longueur du motif
sinon :
i ← i + décalage correspondant à texte[i+j] // 3ème cas : caractère dans le motif, décalage à appliquer
renvoyer occurrences
def rech_naive(texte: str, motif: str)->list:
occur = []
n = len(texte)
p = len(motif)
i = 0
for i in range(n-p+1):
j = 0
while j < p and motif[j] == texte[i + j]:
j += 1
if j == p:
occur += [i]
return occur
→ on voit que pour tout caractère d'indice i dans le motif, : decalage = len(motif)-i-1
def decalages(motif: str)->dict:
dec = {}
p = len(motif)
for i in range(p-1):
dec[motif[i]] = p - i - 1
return dec
Remarque : si il y a plusieurs fois le même caractère dans le motif, une précédente valeur de décalage sera "écrasée" dans le dictionnaire par la nouvelle; mais comme on parcourt le motif de son début vers sa fin, c'est toujours le décalage le plus petit que l'on stockera dans le dictionnaire.
def rech_BMH(texte: str, motif: str)->list:
n = len(texte)
p = len(motif)
dec = decalages(motif)
occur = []
i = 0
while i <= n-p :
j = p - 1
while j >= 0 and motif[j] == texte[i+j]:
j -= 1
if j == -1:
occur += [i]
i += p
elif texte[i+j] not in motif or texte[i+j] == motif[p-1]:
i += p
else:
i += dec[texte[i+j]]
return occur
from timeit import timeit
motif = "Valjean"
with open('les-miserables.txt','r') as f: # ouverture du fichier en lecture seule
texte = f.read()
dec = decalages(motif) # récupération du dictionnaire des décalages
print(timeit(stmt="rech_naive(texte, motif)", globals = globals(), number = 10)) # mesure et affichage du temps total de 10 exécutions de chacun des algorithmes
print(timeit(stmt="rech_BMH(texte, motif, dec)", globals = globals(), number = 10))
1.2386205780003365
0.436998481000046
>>>
3 fois moins de temps... On voit bien la différence, mais ce n'est pas non plus exceptionnel : pour un motif court, les deux algorithmes sont au coude à coude;
Par contre, l'algorithme BMH est d'autant plus efficace que le motif est long.