Recherche textuelle
Source : Gilles Lassus
I. La méthode find de Python⚓︎
⌛ Avant de commencer
Vous devez travailler sur Basthon
Télécharger dans le même dossier :
-
🌐 Fichier
pg798.txt: "Clic droit", puis "Enregistrer la cible du lien sous" -
🌐 TD
find_sujet.ipynb: "Clic droit", puis "Enregistrer la cible du lien sous"
Dans Basthon ouvrir find_sujet.ipynb, puis dans find_sujet.ipynb ouvrir pg798.txt (cliquer sur OK).
😀 La correction est arrivée ...
Télécharger dans le même dossier :
-
🌐 Fichier
pg798.txt: "Clic droit", puis "Enregistrer la cible du lien sous" -
🌐 Correction du TD
find_corr.ipynb: "Clic droit", puis "Enregistrer la cible du lien sous"
Dans Basthon ouvrir find_corr.ipynb, puis dans find_corr.ipynb ouvrir pg798.txt (cliquer sur OK).
II. Recherche textuelle naïve⚓︎
Regarder les 5 premières minutes de la vidéo de l'introduction.
L'algorithme naïf et l'algorithme de Horspool en vidéo : Recherche textuelle
Illustration de l'algorithme
Auteur : Gilles Lassus
Animation de Nicolas Revéret
Algorithme de recherche naïve
Compléter ci-dessous :
Version booléenne de l'algorithme de recherche naïve
Re-écrire l'algorithme précédent en s'arrêtant dès qu'une occurrence de motif est trouvée dans texte.
La fonction renverra uniquement un booléen.
Temps de recherches
⌛ Avant de commencer
Vous devez travailler sur Basthon
Télécharger dans le même dossier :
-
🌐 Fichier
pg798.txt: "Clic droit", puis "Enregistrer la cible du lien sous" -
🌐 TD
temps_naif.ipynb: "Clic droit", puis "Enregistrer la cible du lien sous"
Dans Basthon ouvrir temps_naif.ipynb, puis dans temps_naif.ipynb ouvrir pg798.txt (cliquer sur OK).
III Le principe de l'algorithme Boyer Moore Horspool⚓︎
En bio-informatique
Les algorithmes de recherche textuelle sont aussi notamment utilisés en bio-informatique. C’est dans ce domaine que l’on va prendre les exemples du TP qui suivra.
- Comme son nom l'indique, la bio-informatique est issue de la rencontre de l'informatique et de la biologie : la récolte des données en biologie a connu une très forte augmentation ces 30 dernières années. Pour analyser cette grande quantité de données de manière efficace, les scientifiques ont de plus en plus recourt au traitement automatique de l'information, c'est-à-dire à l'informatique.
- Analyse de l'ADN : Comme vous le savez déjà, l'information génétique présente dans nos cellules est portée par les molécules d'ADN. Les molécules d'ADN sont, entre autres, composées de bases azotées ayant pour noms : Adénine (représenté par un A), Thymine (représenté par un T), Guanine (représenté par un G) et Cytosine (représenté par un C).
Auteur du schéma : Victoria Denys/CEA sur https://www.cea.fr/comprendre/Pages/sante-sciences-du-vivant/l-ADN-dechiffrer-pour-mieux-comprendre-le-vivant.aspx?Type=Chapitre&numero=1
Algorithme de recherche naïve en partant à l'envers
Auteur : Gilles Lassus
Re-écrire l'algorithme de recherche naïve, mais en démarrant de la fin du motif et non du début. Certes, c'est pour l'instant très artificiel, mais cela va nous aider 😊.
Compléter ci-dessous :
Le principe
L'idée est d'améliorer le code précédent (celui où l'on parcourt le motif à l'envers) en sautant directement au prochain endroit potentiellement valide.
Pour cela on regarde le caractère X du texte sur lequel on s'est arrêté (car X n'était pas égal au caractère de rang équivalent dans le motif):
Si X n'est pas dans le motif, il est inutile de se déplacer "de 1" : on retomberait tout de suite sur X, c'est du temps perdu. On se décale donc juste assez pour dépasser X, donc de la longueur du motif cherché. Si X est dans le motif (sauf à la dernière place du motif!), on va regarder la place de la dernière occurence de X dans le motif. On se décale afin de faire coïncider le X du motif et le X du texte.
Visualisation Boyer Moore Horspool par Nicolas Revéret
IV. Implémentation de l'algorithme Boyer Moore Horspool⚓︎
utiliser un prétraitement du motif pour déterminer les décalages
On va d'abord coder une fonction dico_lettres qui renvoie un dictionnaire associant à chaque lettre de mot (paramètre d'entrée)
son dernier rang dans la variable mot. On exclut la dernière lettre, qui poserait un problème lors du décalage (on décalerait de 0...)
Dans l'exemple suivant :
Etape 0 :
Le dictionnaire créé sera donc : dico = {"s": 0, "t": 1, "r": 2, "i": 3, "n": 4}
Etape 1 :
iprend la valeur 5 c'est à direlen(motif) - 1"d"n'étant pas dansdico, on va faire un décalage de 6, c'est à dire delen(motif)
Etape 2 :
iprend la valeur 5 + 6 c'est à dire dei + decalagedico["n"] = 4, on va faire un décalage de 5 - 4, c'est à dire delen(motif) - 1 - dico["n"]
Etape 3 :
iprend la valeur 11 + 1 c'est à dire dei + decalage- On a concordance pour la lettre "g", on vérifie la concordance des lettres en partant vers la gauche,
donc pour les indicesi - k,kaugmentant de 1 à chaque nouvelle comparaison. On observe qu'il n'y a plus concordance lorsquei - k = 8. "p"n'étant pas dansdico, on va faire un décalage de 6, c'est à direlen(motif)à partir de l'indice où l'on se trouve.
iprendra la valeur 8 + 6 = 14, c'est à dire queiprend la valeuri - k + len(motif)
Etape 4 :
iprend la valeur 14dico["s"] = 0, on va faire un décalage de 5 - 0 = 5, c'est à direlen(motif) - 1 - dico["s"]
A vous de jouer : Implémenter l'algorithme Boyer Moore Horspool
Compléter ci-dessous :
V. Crédits⚓︎
Gilles LASSUS, Jean-Louis THIROT, Marine MERA et Mireille COILHAC