Aller au contenu

TP - Algorithme naïf☘

Dans le dossier [NSI], commencez par créer le dossier [E05-Recherche_Textuelle].

Ce TP a pour but de vous faire programmer l'algorithmes naïf de recherche textuelle, en modifiant au fur et à mesure la « qualité » de l'information renvoyée par cet algorithme.

Rappel

L’algorithme naïf (aussi appelé « force brute ») consiste simplement à comparer un à un, de gauche à droite, les caractères du texte apparaissant dans la fenêtre avec ceux du motif. En cas de non-correspondance on avance simplement la fenêtre d’un indice vers la droite (si c'est possible).

Téléchargez le fichier « à trous » TPE05.10.py (clic droit -> [Enregistrer la cible du lien sous]) et enregistrez-le dans le dossier [E05-Recherche_Textuelle].

Des exemples de tests sont proposés à partir des motifs et des textes ci-après. Il faudra ajouter vos propres tests dans le main de votre programme.

Exemple de tests
>>> motif1 = 'witch'
>>> texte1 = 'A witch which switch'

>>> motif2 = 'scribe'
>>> texte2 = """Vous savez, moi je ne crois pas qu’il y ait de bonne ou de mauvaise
situation. Moi, si je devais résumer ma vie aujourd’hui avec vous, je dirais
que c’est d’abord des rencontres. Des gens qui m’ont tendu la main, peut-être à
un moment où je ne pouvais pas, où j’étais seul chez moi. Et c’est assez
curieux de se dire que les hasards, les rencontres forgent une destinée…
Parce que quand on a le goût de la chose, quand on a le goût de la chose bien
faite, le beau geste, parfois on ne trouve pas l’interlocuteur en face je
dirais, le miroir qui vous aide à avancer. Alors ça n’est pas mon cas, comme je
disais là, puisque moi au contraire, j’ai pu : et je dis merci à la vie, je lui
dis merci, je chante la vie, je danse la vie… je ne suis qu’amour ! Et
finalement, quand beaucoup de gens aujourd’hui me disent « Mais comment fais-tu
pour avoir cette humanité ? », et bien je leur réponds très simplement, je leur
dis que c’est ce goût de l’amour ce goût donc qui m’a poussé aujourd’hui à
entreprendre une construction mécanique, mais demain qui sait ? Peut-être
simplement à me mettre au service de la communauté, à faire le don, le don de
soi…"""

motif3 = 'ment'
texte3 = """Et d'abord, bourdonnement dans les oreilles, éblouissement dans
les yeux. Au-dessus de nos têtes une double voûte en ogive, lambrissée en
sculptures de bois, peinte d'azur, fleurdelysée en or; sous nos pieds, un pavé
alternatif de marbre blanc et noir. À quelques pas de nous, un énorme pilier,
véritable menhir, puis un autre, puis un autre; en tout sept piliers dans la
longueur de la salle, soutenant au milieu de sa largeur les retombées de la
double voûte. Autour des quatre premiers piliers, des boutiques de marchands,
tout étincelantes de verre et de clinquants; autour des trois derniers, des
bancs de bois de chêne, usés et polis par le haut-de-chausses des plaideurs et
la robe des procureurs. À l'entour de la salle, le long de la haute muraille,
entre les portes, entre les croisées, entre les piliers, l'interminable rangée
des statues de tous les rois de France depuis Pharamond; les rois fainéants,
les bras pendants et les yeux baissés; les rois vaillants et bataillards, la
tête et les mains hardiment levées au ciel."""

Partie A - Détecter la présence du motif☘

Vous savez déjà que l'opérateur in de Python permet de renvoyer True si le motif est présent dans le texte.

Sans utiliser cet opérateur, et en programmant l'algorithme naïf, complétez la définition de la fonction est_present_naif() qui prend en paramètres deux chaînes de caractères motif et texte. Cette fonction renvoie True si la chaîne motif est présente dans la chaîne texte, elle renvoie False sinon.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def est_present_naif(motif, texte):
    """
    motif - str, chaîne de caractères
    texte - str, chaîne de caractères
    Sortie: bool - True si motif est dans texte, False sinon

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> est_present_naif(motif, texte)
    True
    """

Exemple de tests

>>> est_present_naif(motif1, texte1)
True

>>> est_present_naif(motif2, texte2)
False

>>> est_present_naif(motif3, texte3)
True
Une piste

Faut-il parcourir les caractères du texte ou bien les indices des des caractères du texte ?

Une autre piste

Parcourir un à un les caractères du texte. Dès que ce caractère correspond au premier caractère du motif, s'arrêter pour parcourir un à un les caractères du motif et vérifier sa correspondance avec les caractères suivants du texte :

  • ou bien on est arrivé à la fin du motif et le motif est présent dans le texte ;
  • ou bien on n'est pas au bout du motif et on poursuit le parcours inital des caractères du texte.

Partie B - Positions et nombre d'occurrences☘

  1. Copiez/collez et modifiez le code réalisé dans la partie précédente pour programmer le corps de la fonction nb_occurrences_naif() qui prend en paramètres deux chaînes de caractères motif et texte. Cette fonction renvoie le nombre d'occurrences de la chaîne motif dans la chaîne texte, elle renvoie 0 si motif n'est pas présent dans texte.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def nb_occurrences_naif(motif, texte):
    """
    motif - str, chaîne de caractères
    texte - str, chaîne de caractères
    Sortie: int - Nombre d'occurrences de motif dans texte

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> nb_occurrences_naif(motif, texte)
    4
    """

    Exemple de tests

    >>> nb_occurrences_naif(motif1, texte1)
2

>>> nb_occurrences_naif(motif2, texte2)
0

>>> nb_occurrences_naif(motif3, texte3)
3

  2. Copiez/collez et modifiez le code réalisé dans la fonction précédente pour programmer le corps de la fonction positions_naif() qui prend en paramètres deux chaînes de caractères motif et texte. Cette fonction renvoie le tableau (éventuellement vide) des positions de la chaîne motif dans la chaîne texte.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def positions(motif, texte):
    """
    motif - str, chaîne de caractères
    texte - str, chaîne de caractères
    Sortie: list - Tableau des positions où trouver motif dans texte

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> positions_naif(motif, texte)
    [2, 8, 20, 30]
    """

    Exemple de tests

    >>> positions_naif(motif1, texte1)
[2, 15]

>>> positions_naif(motif2, texte2)
[]

>>> positions_naif(motif3, texte3)
[21, 54, 1067]

Partie C - Nombre de comparaisons☘

En vous inspirant toujours de l'algorithme naïf, complétez la définition de la fonction nb_comparaisons_naif() qui prend en paramètres deux chaînes de caractères motif et texte. Cette fonction renvoie le nombre de comparaisons effectuées pour déterminer (par exemple) les positions de la chaîne motif dans la chaîne texte en appliquant l'algorithme naïf de recherche textuelle.

On compte une comparaison à chaque fois qu'on vérifie si un caractère du texte correspond à un caractère du motif.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def nb_comparaisons_naif(motif, texte):
    """
    motif - str, chaîne de caractères
    texte - str, chaîne de caractères
    Sortie: int - Nombre de comparaisons nécessaires pour
            déterminer les positions où trouver motif dans texte
            selon l'algorithme naïf de recherche textuelle

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> nb_comparaisons_naif(motif, texte)
    52
    """

Exemple de tests

>>> len(texte1)
20
>>> nb_comparaisons_naif(motif1, texte1)
25

>>> len(texte2)
1205
>>> nb_comparaisons_naif(motif2, texte2)
1265

>>> len(texte3)
1087
>>> nb_comparaisons_naif(motif3, texte3)
1108

Ces derniers tests montrent que l'algorithme naïf peut être presque linaire dans certains cas.