Objectifs

Consignes

Contexte

La recherche d'une sous-chaine (appelée aussi motif) dans une chaîne de caractères est souvent utilisée en informatique.

Voici quelques exemples d'application :

Recherche "naïve"

On dispose d'une première chaîne de caractères chaine et d'une autre chaîne de caractères (de longueur inférieure à la première) motif.

Proposer le code d'une fonction Python recherche_motif_naive(chaine,motif) qui détecte la présence de motif dans la chaine de caractères chaine.

Cette fonction devra retourner une liste avec les positions du premier caractère de motif dans chaine.

Si motif n'est pas présent dans chaine la liste retournée sera vide.

Exemple :

			
chaine  = "Paris ! Paris outragé ! Paris brisé ! Paris martyrisé ! Mais Paris libéré !"
motif = "Paris"
print(recherche_motif_naive(chaine,motif)

Doit afficher :

[0, 8, 24, 38, 61]

En effet, le motif "Paris" apparaît 5 fois dans la phrase proposée en positions 0, 8, 24, 38 et 61.

Recherche optimisée en utilisant l'algorithme de Boyer - Moore - Horspool

Cet algorithme a été proposé par Nigel Horspool et qui est une version simplifiée du meilleur algorithme connu : celui de Boyer-Moore.

Il repose sur les deux idées clefs suivantes :

Voici une animation qui permet de comprendre le principe de fonctionnement de l'algorithme de Horspool.

Implémentation en Python de l'algorithme de Hoorspool

Pour établir les décalages à effectuer à chaque étape du traitement, on utilise un dictionnaire dont les clefs sont les lettres du motif et les valeurs le décalage par rapport à la fin du motif.

Proposer le code d'une fonction Python derniere_occurence(motif) qui construit le dictionnaire décrit ci-dessus.

Remarque : Il n'est pas utile de traiter la dernière lettre de motif.

Exemple :

			
		derniere_occurence("rappel")

doit retourner le dictionnaire suivant : 

			
	{'r':5,'a':4,'p':2,'e:1}

En effet, en parcourant le mot rappel à partir de la fin (sans prendre en compte le dernier caractère), la lettre "e" apparait en position 1, la lettre "p" en position 2, la lettre "a" en position 4 et la lettre "r" en position 5.

La fonction principale de l'algorithme de Horspool

Voici en en pseudo-code, une version possible de la fonction principale de l'algorithme de Horspool.

 recherche_motif_horspool(,)
	 = longueur()
	 = longueur()
	// création du dictionnaire des décalages des lettres du motif
	 = derniere_occurence()
	// On créé la liste des positions du premier caractère de motif dans chaine
	 = Liste vide
	// On commence par la fin du motif
	 =  - 1
	  <  
		 = élement en position  de 
		 = Faux
		  = dernier élément de  
			 = éléments de  compris entre les indices () et 
			  =  
				Ajouter  à 
				 = Vrai
			
		
		  = Vrai 
			 =  + 1
		
			  appartient à la liste des clefs de  
				 =  + valeur de  pour la clef 
			
				 =  +

Coder en Python la fonction recherche_motif_horspool(chaine,motif).

Applications

En bio-informatique : recherche d'une séquence dans une chaîne ADN.

On se propose de reproduire la recherche d'une séquence dans une chaîne ADN proposée dans l'animation présentée ci-dessus.

Proposer le code d'une fonction Python nommée genere_chaine_ADN(lg) qui génère aléatoirement une chaine ADN de longueur lg parmi les bases azotées "A","C","G" et "T".

Exemple : genere_chaine_ADN(10) peut retourner la chaîne ADN : "AACTGGTAGC".

Construction d'un "vérificateur" des fonctions recherche_motif_naive(chaine,motif) et recherche_motif_horspool(chaine,motif)

Voici le code Python de deux fonctions cree_jeu_tests_chaine_et_motif_ADN(exp1,exp2) et compare_methodes_naive_et_horspool(jeu_tests) qui construise un jeu de tests pour des chaînes ADN et des motifs différents et vérifie que les résultats retournés par les deux fonctions de recherche du motif (méthode naïve et celle avec l'algorithme de Horspool) sont identiques. 

			
def cree_jeu_tests_chaine_et_motif_ADN(exp1,exp2):
    jeu_tests = []
    for exposant in range(exp1,exp2):
        lg_chaine = 2 ** exposant
        chaine_ADN = genere_chaine_ADN(lg_chaine)
        for lg_motif in range(1,lg_chaine//3):
            pos_debut = randint(0,lg_chaine-lg_motif)
            motif = chaine_ADN[pos_debut:pos_debut+lg_motif]
            jeu_tests.append((chaine_ADN,motif))
    return jeu_tests


def compare_methodes_naive_et_horspool(jeu_tests):
    for test in jeu_tests:
        chaine = test[0]
        motif = test[1]
        lst_positions_motif_methode_naive = recherche_motif_naive(chaine, motif)
        lst_positions_motif_algo_Horspool = recherche_motif_horspool(chaine, motif)
        assert lst_positions_motif_methode_naive == lst_positions_motif_algo_Horspool

Commenter le code de ces deux fonctions en ajoutant des docstrings dans les entêtes et décrire le jeu de tests généré.

Utiliser ces deux fonctions pour valider vos deux fonctions développées recherche_motif_naive(chaine,motif) et recherche_motif_horspool(chaine,motif).

Recherche de mots dans un roman

Voici le fichier au format ".txt" du texte intégral du roman de Victor Hugo "Les Misérables" : Texte intégral "Les Misérables".

Proposer un code Python qui permet de répondre aux questions suivantes :

Indications :

Complexité algorithmique des deux méthodes de recherche

Pour la fonction de recherche naïve, donner le nombre de comparaisons effectuées caractère par caractère dans le pire des cas en fonction de la taille de la chaîne de départ lg_chaine et la taille du motif recherché lg_motif.

Pour l'algorithme de recherche de Horspool, l'étude théorique de la complexité algorithmique dépasse le cadre de NSI.

Une étude "expérimentale" de la complexité algorithmique de l'algorithme de Horspool.

A l'aide des deux applications précédentes (motif dans une chaine ADN et recherche de mots dans un livre), utilisez les compteurs du nombre de comparaisons effectuées lettre à lettre pour estimer en moyenne le facteur nombre de recherches algorithme naïf / nombre de recherches algorithme de Horspool.

On peut montrer qu'en moyenne la complexité est de l'ordre de $O(3 \times lg\_chaine)$ et que dans le pire des cas la complexité est de l'ordre de $O(lg\_chaine \times lg\_motif)$.

Pour aller plus loin

L'algorithme de Boyer-Moore utilise un autre tableau dit du bon préfixe, qui permet d'optimiser un peu plus la recherche. Si vous êtes interessé en voici une implémentation en Python proposée ici.

L'algorithme de Boyer-Moore complet est implémenté dans le langage Python pour les fonctions find, index.

Auteur : Hugues Malherbe

Document inspiré des ressources suivantes :