¶ Exercice 1 - La recherche naïve
Dans cet exercice, on s'intéresse à la programmation de l'algorithme naïf.
Pour bien comprendre l'algorithme, voici une petite animation : https://boyer-moore.codekodo.net/recherche_naive.php
Question 1 - Écrire une fonction recherche_naive. Cette fonction prend en paramètre deux chaines de caractères texte et motif. Elle indique l'indice du motif dans le texte si celui-ci est présent. Le résultat sera sous la forme d'un tuple composé d'un booléen et de l'indice du motif dans le texte.
def recherche_naive(texte:str, motif:str) -> tuple:
return
Question 2 - Tester votre fonction avec les exemples ci-dessous.
>>> recherche_naive('Bonjour le monde', 'le')
(True, 8)
>>> recherche('Bonjour le monde', 'nj')
(True, 2)
>>> recherche('Bonjour le monde', 'B')
(True, 0)
>>> recherche('Bonjour le monde', 'ya')
(False, -1)
¶ Exercice 2 - L'algorithme de Boyer-Moore
Dans cet exercice, on s'intéresse à la programmation de l'algorithme de Boyer-Moore.
Question 1 - Écrire la fonction decalage. Cette fonction prend en paramètre le motif. Elle retourne un dictionnaire dont les clefs sont les lettres du motif et les valeurs le décalage par rapport à la fin du motif.
La valeur du décalage est égale à la distance entre cette lettre et la fin du motif. Bien sûr, on ne prend pas en compte la dernière lettre du motif, elle correspond à l'analyse qu'on vient de faire.
def decalage(mot:str) -> dict :
return
Question 2 - Écrire la fonction boyer_moore. Cette fonction prend en paramètre deux chaines de caractères texte et motif. Elle indique l'indice du motif dans le texte si celui-ci est présent. Le résultat sera sous la forme d'un tuple composé d'un booléen et de l'indice du motif dans le texte.
Pour bien comprendre l'algorithme, voici une petite animation : https://boyer-moore.codekodo.net/recherche_boyer.php
def boyer_moore(texte:str, motif:str) -> tuple :
return
¶ Exercice 3 - Comparaison des algorithmes
On souhaite maintenant compararer l'efficacité de chacun des algorithme
Question 1 - Modifier la fonction recherche_naive afin d'y ajouter une compteur du nombre de comparaisons effecutées lors de cet algorithme. Le fonction retournera un tuple composé de trois éléments :
- Un booléen selon la présence du motif dans le texte.
- Un entier pour l'indice du motif.
- Un entier pour le nombre de comparaisons au sein de l'algorithme.
Voici un exemple d'exécution de la fonction.
>>> texte = "a"*100 + 'une magnifique maison bleue'
>>> motif = 'maison'
>>> recherche_naive(texte, motif)
(True, 315, 324)
Question 2 - Modifier la fonction recherche_boyer_moore afin d'y ajouter une compteur du nombre de comparaisons effecutées lors de cet algorithme. Le fonction retournera un tuple composé de trois éléments :
- Un booléen selon la présence du motif dans le texte.
- Un entier pour l'indice du motif.
- Un entier pour le nombre de comparaisons au sein de l'algorithme.
Voici un exemple d'exécution de la fonction.
>>> texte = "a"*100 + 'une magnifique maison bleue'
>>> motif = 'maison'
>>> boyer_moore(texte, motif)
(True, 315, 60)
Normalement, vous devez obtenir un nombre de comparaisons nettement inférieur avec l'algorithme de Booyer-Moore.