- Comprendre le fonctionnement d'une recherche textuelle ;
- Mettre en place une solution algorithmique de recherche textuelle.
Activité 1 - Introduction à la recherche textuelle
La recherche textuelle est un type de recherche algorithmique dite de recherche de sous-chaîne. Son objectif est donc d'identifier la position d'une chaîne de caractères donnée dans un texte.
C'est notamment ce qu'effectue le navigateur lorsque l'on appuie sur les touches ctrl + F dans une page web, ou bien un éditeur de texte, pour chercher la position d'un mot (ou ensemble de mots) demandé.
Recherche naïve
La recherche naïve consiste à transposer le mot que l'on cherche au tout début du texte, et à le déplacer d'un rang si les lettres ne correspondent pas.
Soit la phrase suivante, le mot que l'on cherche est faire :
Un programme informatique fait ce que vous lui avez dit de faire, pas ce que vous voulez qu'il fasse.
faire
Cas 1
La première lettre de chaque mot ne correspond pas, on va donc avancer d'un rang :
Un programme informatique fait ce que vous lui avez dit de faire, pas ce que vous voulez qu'il fasse.
faire
Cas 2
Un programme informatique fait ce que vous lui avez dit de faire, pas ce que vous voulez qu'il fasse.
faire
La première lettre correspond, donc on va tester la 2ème lettre du mot, la 3ème également, mais la 4ème non, donc on continue.
Cas 3
Un programme informatique fait ce que vous lui avez dit de faire, pas ce que vous voulez qu'il fasse.
faire
La première lettre correspond, donc on va tester la 2ème lettre du mot, la 3ème également, la 4ème, et la 5ème correspondent, on a trouvé notre mot, à un certain indice.
Réfléchir à un algorithme récursif permettant de mettre en place cette solution avec un texte et un mot à trouver en paramètres et retournant l'indice de la position du mot s'il est trouvé, -1 dans le cas contraire.
Mettre en place la fonction python se basant sur l'algorithme écrit.
Elle pourra être testée avec la phrase et le mot donnés en exemple.
Algorithme de Boyer-Moore Horspool
Développé par Robert S. Boyer et J Strother Moore en 1977, l'algorithme se veut être plus efficace que la recherche naïve, lors d'une recherche de motif.
Une simulation du fonctionnement peut-être faite sur ce site.
On souhaite chercher le motif nsi dans le texte bvssixnsikjesi :
| indice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| texte | b | v | s | s | i | x | n | s | i | k | j | e | s | i |
| motif | n | s | i |
On commence par vérifier si la dernière lettre du motif correspond à la lettre du texte, au même indice :
motif[2] != texte[2] car i != s.
Il va y avoir 2 cas :
- Soit la lettre du texte existe dans le motif (il faut donc vérifier toutes les lettres du motif), dans ce cas on décale d'autant d'indice qu'il le faut pour que les lettres soient superposées ;
- Soit la lettre du texte n'existe pas dans le motif, dans ce cas on décale d'autant de lettres existantes dans le motif.
La lettre s est présente dans le motif, à une distance de 1, on peut donc décaler d'un rang vers la droite, et on recommence :
| indice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| texte | b | v | s | s | i | x | n | s | i | k | j | e | s | i |
| motif | n | s | i |
On continue :
| indice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| texte | b | v | s | s | i | x | n | s | i | k | j | e | s | i |
| motif | n | s | i |
Si la dernière lettre du motif est égale à la lettre correspondante du texte, dans ce cas on vérifie l'avant dernière lettre, et ainsi de suite. On a à nouveau 2 cas :
- Si on a vérifié toutes les lettres et qu'elles sont toutes correspondantes, on a trouvé notre motif ;
- Si une des lettres vérifiées est différentes, on recommence les décalages.
motif[2] != texte[2], or il n'y a plus de lettres à vérifier, on décale d'autant de lettres qu'il y a dans le motif :
| indice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| texte | b | v | s | s | i | x | n | s | i | k | j | e | s | i |
| motif | n | s | i |
motif[7] != texte[7], or la lettre s est présente dans le motif, on décale de 1 :
| indice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| texte | b | v | s | s | i | x | n | s | i | k | j | e | s | i |
| motif | n | s | i |
- motif[8] == texte[8], on vérifie les lettres d'avant
- motif[7] == texte[7], on vérifie les lettres d'avant
- motif[6] == texte[6], il n'y a plus de lettres à vérifier, le motif est à l'indice
6dans le texte.
Pour rendre le travail plus simple, l'algorithme initialise au préalable une table des sauts.
Cette table est un dictionnaire dont les clés sont les lettres du motif, et la valeur associée est la distance entre la lettre par rapport au début du motif. On prend en compte toutes les lettres, sauf la dernière :
Avec la clé nsi on aurait le dictionnaire suivant :
dico = {'n' : 2, 's' : 1}
La clé bonjour donnerait :
dico = {'b' : 6, 'o' : 2 , 'n' : 4, 'j' : 3, 'u' : 1}
Ainsi, si une lettre de notre texte appartient à la clé, on pourra piocher dans le dictionnaire directement la valeur du décalage à effectuer.
Travail sur papier
On dispose de la phrase suivante (de Confucius):
"La plus grande gloire n'est pas de ne jamais tomber, mais de se relever à chaque chute."
On cherche le motif mais.
- Créer la table des sauts correspondant au motif.
- Effectuer et faire le détail des opérations nécessaires à la recherche du motif dans le texte.
- Écrire un algorithme permettant d'effectuer la recherche avec Boyer-Moore Horspool.
Programmation
- Créer une fontion
pretraitement(motif)qui prend un motif (str) en paramètre, et retourne un dictionnaire contenant les lettres en clé, et la distance de la lettre en valeur. - Créer une fonction
boyer_moore(texte, motif)qui prend un texte et un motif en paramètres (str), et qui adapte l'algorithme écrit précédemment pour effectuer une recherche textuelle selon Boyer-Moore.
Compléter le puzzle :
Comparaison d'algorithmes
On souhaite, à partir du livre Le rouge et le noir de Stendhal, téléchargeable ici, comparer le temps d'exécution de différents algorithmes de recherche.
On souhaite également cette fois-ci compter le nombre de fois qu'un motif se répète dans un texte.
Modifier les fonctions précédentes pour ne plus renvoyer l'indice de la première itération du motif, mais le nombre d'itérations du motif dans le texte.
- En utilisant la documentation python à cette adresse, ouvrir dans un premier temps le fichier
le rouge et le noir. - Importer la bibliothèque
time, permettant de calculer des temps d'exécution. Voici le schéma permettant de calculer un temps :
t1 = time()
#j'effectue mon calcul
t2 = time()
print("le temps est :",t2-t1)
J'effectue dans t1 un instantané du temps de mon programme, je fais mon calcul, je fais pareil avec t2. Le temps qu'aura mis mon programme à s'exécuter est la différence entre t2 et t1.
- Avec la fonction de recherche naïve, afficher le temps mis par le programme pour compter le nombre de répétitions du motif
route. - Question réflexion : Quel motif faudrait-il chercher pour afficher le nombre de chapitre du livre ? Écrire l'instruction permettant d'obtenir cette valeur.
- La fonction
count(motif)sur une chaine de caractères permet de compter le nombre d'occurence du motif dans la chaine. Calculer le temps d'exécution de cette fonction. - Calculer le temps d'exécution avec la fonction de Boyer Moore Horspool, et le même motif.
- Pourquoi les résultats des 2 fonctions sont différents ?
- Réessayer avec le motif
Julien. Comparer les temps d'exécution de ces 3 fonctions, et en déduire laquelle serait la plus rapide.