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(t: str, m: str)->list:
occur = []
i = 0
for i in range(len(t)-len(m)+1):
j = 0
while j < len(m) and m[j] == t[i + j]:
j += 1
if j == len(m):
occur += [i]
i += 1
return occur
→ on voit que pour tout caractère d'indice i dans le motif, : decalage = len(motif)-i-1
def decalages(m: str)->dict:
dec = {}
for i in range(len(m)-1):
dec[m[i]] = len(m) - 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(t: str, m: str)->list:
dec = decalages(m)
occur = []
i = 0
while i <= len(t)-len(m):
j = len(m) - 1
while j >= 0 and m[j] == t[i + j]:
j -= 1
if j == -1:
occur += [i]
i += len(m)
elif t[i + j] not in m or t[i+j] == m[len(m)-1]:
i += len(m)
else:
i += dec[t[i + j]]
return occur
from timeit import timeit
def rech_naive(t: str, m: str)->list:
....
def decalages(m: str)->dict:
....
def rech_bmh(t: str, m: str, dec: dict)->list:
....
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.