Algorithmes de recherche textuelle
Partie 1: Algorithmes de recherche textuelle
Question 1.1
Écrire une fonction recherche_motif qui prend en paramètres une chaîne de caractères motif non vide et une chaîne de caractères texte, la fonction renvoie la liste des positions de motif dans texte. Si motif n’apparaît pas, la fonction renvoie une liste vide.
Exemples de résultats:
>>> recherche_motif("ab", "")
[ ]
>>> recherche_motif("ab", "cdcdcdcd")
[ ]
>>> recherche_motif("ab", "abracadabra")
[0, 7]
>>> recherche_motif("ab", "abracadabraab")
[0, 7, 11]
Question 1.2
On considère l'algorithme de Boyer Moore étudié en classe, voir la partie Ressources:
Établir la table de décalage pour le motif "abra", coder ( manuellement ) cette table avec le dictionnaire dico.
Question 1.3
Ecrire la fonction table_dec (m) qui renvoie le dictionnaire dico pour le motif, tester pour le mot "abra"
Question 1.4
Ecrire la fonction décalage (dico, j, k ) qui renvoie le décalage à opérer lorsque le caractère k du texte à la position j est non conforme afin de décaler le motif pour le mettre en correspondance au niveau de ce caractère ou afin de décaler tout le motif en j+1
Question 1.5
Ecrire la fonction boyer_moore (motif, texte) qui renvoie la liste des positions de motif dans texte en utilisant l'algorithme de Boyer-Moore. Si motif n’apparaît pas dans texte, la fonction renvoie une liste vide.
Créé avec HelpNDoc Personal Edition: Produire des livres Kindle gratuitement