Correction : recherche textuelle

Algorithme naïf

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
			

Algorithme de Boyer-Moore-Horspool

Fonction de calcul des décalages

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		
			

Recherche du motif

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
	
			

Implémentation Python

Algorithme naïf

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			
		

Algorithme BMH

Fonction de calcul des décalages

→ 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.

Implémentation de l'algo de recherche BMH

 
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			
		

Comparaison des deux algorithmes

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.