TP1 : Algorithme naïf

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

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 python « à trous » ci-dessous (clic droit -> [Enregistrer la cible du lien sous]) et enregistrez-le dans votre dossier crée pour l'occasion.

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.

TP Recherche Textuelle Naif [py]

Voici quelques textes et motifs dont vous allez pouvoir vous servir pour vos tests :

1
motif1 = 'witch'
2
texte1 = 'A witch which switch'
3
4
motif2 = 'scribe'
5
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…"""
6
7
motif3 = 'ment'
8
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."""
9
Il est bien sûr tout à fait possible d'utiliser d'autres exemples de tests en plus de ces trois-là.
Partie A - Détecter la présence du motif
Commençons simple... Détectons la présence du motif dans notre texte.
Vous savez déjà que l'opérateur in de Python permet de renvoyer True si le motif est présent dans le texte.
Question
Question 1 :
Sans utiliser cet opérateur in, 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
def est_present_naif(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: bool - True si motif est dans texte, False sinon
6
7
    >>> motif = 'CAAGT'
8
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
9
    >>> est_present_naif(motif, texte)
10
    True
11
    """
Exemples de tests à coder :
1
>>> est_present_naif(motif1, texte1)
2
True
3
4
>>> est_present_naif(motif2, texte2)
5
False
6
7
>>> est_present_naif(motif3, texte3)
8
True
Indice
Faut-il parcourir les caractères du texte ou bien les indices des caractères du texte ?
Indice
Doit-on parcourir tout le texte ? ou peut-on s'arrêter avant ?
Indice
L'usage de la boucle while semble plus adaptée que la boucle for
Indice
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 et donc on renvoie True ;
  • ou bien on n'est pas au bout du motif et on poursuit le parcours initial des caractères du texte.
Partie B - Positions et nombre d'occurrences
Améliorons le code précédent pour renvoyer les positions et le nombre de fois que l'on trouve le motif dans le texte.
Question
Question 2 :
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
def nb_occurrences_naif(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: int - Nombre d'occurrences de motif dans texte
6
7
    >>> motif = 'CAAGT'
8
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
9
    >>> nb_occurrences_naif(motif, texte)
10
    4
11
    """
12
Exemples de tests à coder :
1
>>> nb_occurrences_naif(motif1, texte1)
2
2
3
4
>>> nb_occurrences_naif(motif2, texte2)
5
0
6
7
>>> nb_occurrences_naif(motif3, texte3)
8
3
Indice
Avez-vous bien copié le code précédent dans le corps de la fonction ?
Indice
Un compteur doit permettre de s'en sortir...
Question
Question 3 :
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
def positions(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: list - Tableau des positions où trouver motif dans texte
6
7
    >>> motif = 'CAAGT'
8
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
9
    >>> positions_naif(motif, texte)
10
    [2, 8, 20, 30]
11
    """
Exemples de tests à coder :
1
>>> positions_naif(motif1, texte1)
2
[2, 15]
3
4
>>> positions_naif(motif2, texte2)
5
[]
6
7
>>> positions_naif(motif3, texte3)
8
[21, 54, 1015]
Indice
Il faut renvoyer une liste d'indices...
Partie C - Nombre de comparaisons
On s'intéresse maintenant au nombre de comparaisons qu'il est nécessaire d'effectuer pour recherche le motif dans le texte.
On compte une comparaison à chaque fois qu'on vérifie si un caractère du texte correspond à un caractère du motif.
Question
Question 4 :
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.
1
def nb_comparaisons_naif(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: int - Nombre de comparaisons nécessaires pour
6
            déterminer les positions où trouver motif dans texte
7
            selon l'algorithme naïf de recherche textuelle
8
9
    >>> motif = 'CAAGT'
10
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
11
    >>> nb_comparaisons_naif(motif, texte)
12
    52
13
    """
Exemples de tests à coder :
1
>>> len(texte1)
2
20
3
>>> nb_comparaisons_naif(motif1, texte1)
4
25
5
6
>>> len(texte2)
7
1145
8
>>> nb_comparaisons_naif(motif2, texte2)
9
1205
10
11
>>> len(texte3)
12
1035
13
>>> nb_comparaisons_naif(motif3, texte3)
14
1056
15
Indice
Peut-être avez-vous du mal à trouver où mettre le compteur... Vérifier que vous avez bien compris ce résultat :
1
>>> len(texte1)
2
20
3
>>> nb_comparaisons_naif(motif1, texte1)
4
25
Indice
Il y a les comparaisons avec la variable i, mais aussi les comparaisons avec la variable k.
Partie D : Application à la recherche d'un motif dans un roman
Le Projet Gutenberg permet de télécharger légalement des ouvrages libres de droits dans différents formats.
Nous allons travailler avec le Tome 1 du roman Les Misérables de Victor Hugo, à télécharger ci-dessous au format txt :
Tome 1 du livre Les Misérables [txt]
Question
Question 5 :
Pour manipuler les textes, il ne faut qu'une seule chaîne de caractères. Que faut-il programmer pour n'avoir ce roman qu'en une seule chaîne de caractères ?
Indice
Le caractère à supprimer est le caractère saut de ligne.
Indice
On pourra astucieusement utiliser la fonction replace() appliquée à la fonction read() d'un fichier.
Solution
1
with open("Les_Miserables.txt") as f:
2
    roman = f.read().replace('\n', ' ')
Question
Question 6 :
À l'aide du module time :
  • Mesurer le temps de recherche dans Les Misérables d'un mot court, d'une longue phrase (présente dans le texte) et d'un mot qui n'existe pas.
  • Que remarquez-vous ?
Indice
On note l'heure avec le module time, puis on regarde l'heure après la recherche. On peut en déduire le temps de recherche...
Bonus...
Trouvez de nouveaux cas de tests pour la partie C et tracer une courbe (avec le moyen que vous souhaitez) avec, en abscisse, la longueur du texte et, en ordonnée, le nombre de comparaisons.
Pouvez-vous en tirer une conclusion sur cet algorithme de recherche ?