N.S.I. WorkSpace T-Th-E,Terminale E.5 – Recherche textuelle (Chercher un motif dans un texte)

E.5 – Recherche textuelle (Chercher un motif dans un texte)

Categories:

La nature du problème à résoudre…

Le problème posé est le suivant : dans le texte ci-après, combien de fois et à quels endroits peut-on trouver cette suite des trois lettres : ‘ion’ ?

« Chante, déesse, du Pèlèiade Akhilleus la colère désastreuse, qui de maux infinis accabla les Akhaiens, et précipita chez Aidès tant de fortes âmes de héros, livrés eux-mêmes en pâture aux chiens et à tous les oiseaux carnassiers. Et le dessein de Zeus s’accomplissait ainsi, depuis qu’une querelle avait divisé l’Atréide, roi des hommes, et le divin Akhilleus.
Qui d’entre les dieux les jeta dans cette dissension ? Le fils de Zeus et de Lètô. Irrité contre le roi, il suscita dans l’armée un mal mortel, et les peuples périssaient, parce que l’Atréide avait couvert d’opprobre Khrysès le sacrificateur.
Et celui-ci était venu vers les nefs rapides des Akhaiens pour racheter sa fille ; et, portant le prix infini de l’affranchissement, et, dans ses mains, les bandelettes de l’Archer Apollôn, suspendues au sceptre d’or, il conjura tous les Akhaiens, et surtout les deux Atréides, princes des peuples :
– Atréides, et vous, anciens aux belles knèmides, que les dieux qui habitent les demeures olympiennes vous donnent de détruire la ville de Priamos et de vous retourner heureusement ; mais rendez-moi ma fille bien-aimée et recevez le prix de l’affranchissement, si vous révérez le fils de Zeus, l’archer Apollôn.
Et tous les Akhaiens, par des rumeurs favorables, voulaient qu’on respectât le sacrificateur et qu’on reçût le prix splendide ; mais cela ne plut point à l’âme de l’Atréide Agamemnôn, et il le chassa outrageusement, et il lui dit cette parole violente :
– Prends garde, vieillard, que je te rencontre auprès des nefs creuses, soit que tu t’y attardes, soit que tu reviennes, de peur que le sceptre et les bandelettes du dieu ne te protègent plus. Je n’affranchirai point ta fille. La vieillesse l’atteindra, en ma demeure, dans Argos, loin de sa patrie, tissant la toile et partageant mon lit. Mais, va ! ne m’irrite point, afin de t’en retourner sauf.
Il parla ainsi, et le vieillard trembla et obéit. Et il allait, silencieux, le long du rivage de la mer aux bruits sans nombre. Et, se voyant éloigné, il conjura le roi Apollôn que Lètô à la belle chevelure enfanta :
– Entends-moi, porteur de l’arc d’argent, qui protèges Khrysè et Killa la sainte, et commandes fortement sur Ténédos, Smintheus ! Si jamais j’ai orné ton beau temple, si jamais j’ai brûlé pour toi les cuisses grasses des taureaux et des chèvres, exauce mon vœu : que les Danaens expient mes larmes sous tes flèches !
Il parla ainsi en priant, et Phoibos Apollôn l’entendit ; et, du sommet Olympien, il se précipita, irrité dans son cœur, portant l’arc sur ses épaules, avec le plein carquois. Et les flèches sonnaient sur le dos du dieu irrité, à chacun de ses mouvements. Et il allait, semblable à la nuit.
Assis à l’écart, loin des nefs, il lança une flèche, et un bruit terrible sortit de l’arc d’argent. Il frappa les mulets d’abord et les chiens rapides ; mais, ensuite, il perça les hommes eux-mêmes du trait qui tue. Et sans cesse les bûchers brûlaient, lourds de cadavres.
Depuis neuf jours les flèches divines sifflaient à travers l’armée ; et, le dixième, Akhilleus convoqua les peuples dans l’agora. Hèrè aux bras blancs le lui avait inspiré, anxieuse des Danaens et les voyant périr. Et quand ils furent tous réunis, se levant au milieu d’eux, Akhilleus aux pieds rapides parla ainsi :
– Atréide, je pense qu’il nous faut reculer et reprendre nos courses errantes sur la mer, si toutefois nous évitons la mort, car, toutes deux, la guerre et la contagion domptent les Akhaiens. Hâtons-nous d’interroger un divinateur ou un sacrificateur, ou un interprète des songes, car le songe vient de Zeus. Qu’il dise pourquoi Phoibos Apollôn est irrité, soit qu’il nous reproche des vœux négligés ou qu’il demande des hécatombes promises. Sachons si, content de la graisse fumante des agneaux et des belles chèvres, il écartera de nous cette contagion.
Ayant ainsi parlé, il s’assit. Et le Thestoride Kalkhas, l’excellent divinateur, se leva. Il savait les choses présentes, futures et passées, et il avait conduit à Ilion les nefs Akhaiennes, à l’aide de la science sacrée dont l’avait doué Phoibos Apollôn. Très sage, il dit dans l’agora :
– Ô Akhilleus, cher à Zeus, tu m’ordonnes d’expliquer la colère du roi Apollôn l’archer. Je le ferai, mais promets d’abord et jure que tu me défendras de ta parole et de tes mains ; car, sans doute, je vais irriter l’homme qui commande à tous les Argiens et à qui tous les Akhaiens obéissent.
Un roi est trop puissant contre un inférieur qui l’irrite. Bien que, dans l’instant, il refrène sa colère, il l’assouvit un jour, après l’avoir couvée dans son cœur. Dis-moi donc que tu me protégeras.
Et Akhilleus aux pieds rapides, lui répondant, parla ainsi :
– Dis sans peur ce que tu sais. Non ! par Apollôn, cher à Zeus, et dont tu découvres aux Danaens les volontés sacrées, non ! nul d’entre eux, Kalkhas, moi vivant et les yeux ouverts, ne portera sur toi des mains violentes auprès des nefs creuses, quand même tu nommerais Agamemnôn, qui se glorifie d’être le plus puissant des Akhaiens.
Et le divinateur irréprochable prit courage et dit :
– Apollôn ne vous reproche ni vœux ni hécatombes ; mais il venge son sacrificateur, qu’Agamemnôn a couvert d’opprobre, car il n’a point délivré sa fille, dont il a refusé le prix d’affranchissement. Et c’est pour cela que l’archer Apollôn vous accable de maux ; et il vous en accablera, et il n’écartera point les lourdes kères de la contagion, que vous n’ayez rendu à son père bien-aimé la jeune fille aux sourcils arqués, et qu’une hécatombe sacrée n’ait été conduite à Khrysè. Alors nous apaiserons le dieu. »

Extrait de L’Iliade, Chant 1, Homère. (source : https://www.atramenta.net/lire/liliade/1507/1#oeuvre_page)

Chargement d’un fichier ‘txt’ en Python

"""Spécialité NSI - Terminale - MODULE : Algorithme de recherche textuelle"""

def charge_texte(fichier: str) -> str:
    """Charge le contenu d'un fichier 'txt'
    
    Parameters
    ----------
    fichier : str
        nom du fichier

    Returns
    -------
    t : str
        chaîne de caractères contenant le texte du fichier.

    """
    
    r = open(fichier, mode="r", encoding="utf-8")
    t = r.read()
    t = t.replace(chr(13), "")
    r.close()
    return t

if __name__ == "__main__":
    t = charge_texte("texte.txt")

Code Python ci-dessus + Fichier « texte.txt » à télécharger (Archive .zip)

Programmation et étude d’un algorithme « naïf »

Conventions : pour la suite du travail, on appelle m le motif de caractères de longueur lm que l’on recherche dans un texte t de longueur lt.
S’il existe une occurrence du motif à la position i alors les caractères du texte compris entre t[i] et t[i + lm – 1] coïncident avec les caractères du motif compris entre m[0] et m[lm – 1]

Objectifs d’apprentissage ou d’entraînement et pré-requis (acquis antérieurs mobilisés)

  • implémenter un algorithme en langage Python
  • documenter une fonction
  • commenter des instructions
  • Représentation des données : types et valeurs de base – Caractères et chaînes de caractères (NSI – Première)

Programmation en langage Python : compétences requises ( à acquérir, à mobiliser, à développer, à maîtriser)

  • Chaîne de caractères : type construit (propriétés et méthodes)

Soit l’algorithme suivant :

Algorithme de recherche d’un motif m dans un texte t

    soit lt le nombre de caractères de t
    soit lm le nombre de caractères de m

    parcours de t, du 1er jusqu'au (lt-lm)ième caractère, avec un pas de 1 caractère

        soit p la position du caractère de t auquel on est rendu dans le parcours

        si tous les caractères de t compris entre p et (p + lm) coïncident avec ceux de m,
           alors il existe une occurrence de m dans t à la position p

fin de algorithme

Complétez les instructions qui suivent écrites en Python afin qu’elles exécutent l’algorithme ci-dessus en indiquant ce qui convient à votre avis, là où se trouvent des ‘???’

from rech_text import *

def recherche_naive1(t: str, m: str)->list:
    
    # initialisation d'une liste de stockage des indices des occurrences
    resultat = []
    
    # affectation des nombres de caractères de t et m à lt et lm
    lt = len(t)
    lm = len(m)
    
    # parcours de t du 1er jusqu'au (lt -lm)ième caractère
    for i in range (???):
        
        # Initialisation d'un booléen de présence d'une occurrence
        occ = ???
        
        # Comparaison des lm caractères de t avec ceux de m
        for j in range(???):
            if t[???] != m[???]:
                # si un caractère de t diffère de celui de m, pas d'occurrence
                ??? = False
        # Si présence d'une occurrence
        if occ:
            # ajout de sa position dans la liste de résultats
            resultat.append(???)
            
    return resultat

if __name__ == "__main__":
    t = charge_texte("texte.txt")
    r = recherche_naive1(t, "ion")

Auto-correction : fichier python avec programme complet

Vérifier les réponses données

Ouvrir le texte dans un éditeur tel que « Notepad++ »

Avec la fonction « rechercher » (Search), localiser la première occurrence.

Sélectionner le texte qui précède et observer la longueur de ce texte.

Le texte qui précède la première occurrence comporte 413 caractères. La première occurrence commence donc en position 414.

Fichier Python à télécharger


Prouver la terminaison de cet algorithme

Evaluer le coût de cet algorithme

Rappelez une définition du coût d’un algorithme.

A quoi semble lié le coût de la fonction ‘recherche()’ précédente?
Et de quelle façon (quelle relation ?) ?

Vérifiez vos hypothèses en réalisant des mesures de temps d’exécution.

Ajoutez les instructions suivantes  :

from time import perf_counter
debut_rech = perf_counter()
fin_rech = perf_counter()
duree_execution = fin_rech – debut_rech

à l’endroit qui convient dans le code suivant :

"""Spécialité NSI - Terminale - MODULE : Algorithme de recherche textuelle"""

from rech_text2 import *
???

def cout(texte, motif):
    ???
    occ = recherche_naive1(texte, motif)
    ???
    return ???
        
texte1 = "a" * 1000
texte2 = "a" * 2000
texte3 = "a" * 4000
texte4 = "a" * 8000
texte5 = "a" * 16000
texte6 = "a" * 32000
motif = "z" * 50

textes = [texte1, texte2, texte3, texte4, texte5, texte6]
couts = []
for txt in textes:
    couts.append(cout(txt, motif))
Télécharger le code complet

Télécharger le code complet avec affichage d’un graphe.

Examinez les mesures de coût suivantes (provenant de l’exécution du code précédent). Valident-elles votre hypothèse précédente ?

Exercice – Amélioration de l’algorithme « naïf ».

Examinez la fonction qui suit, écrite en Python.

def recherche(m, t):
  	resultat = ""
    lt = len(t)
    lm = len(m)
    for i in range (0,lt - lm + 1):
        reponse = True
        j = 0
        while j < lm :
            if t[i + j]!= m[j] :
                reponse = False
                j = lm
            else:
                j = j + 1
        if reponse == True:
          	resultat += "Occurence à la position : " + str(i + 1) + chr(10)
            
	return resultat

Écrivez l’algorithme qui correspond à cette fonction.

Comparez le au précédent et montrez qu’il permet de réduire le coût de l’algorithme précédent.

Ajoutez les instructions nécessaires qui permettent de comparer les durées d’exécution des deux implémentation de la fonction recherche().

Algorithme de Boyer-Moore

Principe de l’algorithme

Cet algorithme utilise un pré-traitement du motif m à chercher dans le texte t afin d’accélérer la recherche d’occurrences.

Ce pré-traitement consiste à construire une ‘table de décalage’ qui pour chaque caractère c du motif m associe l’index de chacun des caractères qui le précèdent dans le motif.
Si un caractère existe en plusieurs exemplaires, c’est la position du plus près qui est conservée.

Il s’agit ensuite de parcourir le texte en décalant le motif, mais contrairement à l’algorithme naïf qui ne décale le motif que d’une position à chaque itération, il s’agira ici de le décaler de plusieurs positions dans certains cas.

La comparaison des caractères du motif et du texte se fait à partir du dernier caractère du motif – donc dans le sens inverse de la lecture :

tant que le caractère du motif est identique à celui du texte, on continue la comparaison.

Si on atteint le premier caractère du motif, il y a une occurrence du motif dans le texte.

Sinon : si le caractère du motif situé à l’index i diffère de celui du texte et que le caractère du texte en question ne figure pas dans la liste des caractères du motif situés avant l’index i, alors le motif sera décalé vers la gauche d’une valeur égale à l’index i et à laquelle on ajoute 1.

Exemple 1

La lettre ‘m’ du motif ‘commandes’ située à l’index 2 ne correspond pas à la lettre du texte qui est un ‘a’ et la lettre ‘a’ ne figure pas dans les lettres du motif situées avant le ‘m’ de l’index 2. Donc le motif est décalé de la valeur de l’index i plus 1, soit 2 +1 = 3 caractères.
Dans ce cas le décalage est maximal lorsque la différence porte sur la dernière lettre du motif, c’est à dire celle qui comparée en premier. Le décalage sera égal à la longueur du motif. Par exemple si le motif était ‘commander’
    • Dans ce cas le décalage est minimal lorsque la différence porte sur la première lettre du motif seulement, c’est à dire celle qui sera comparée en dernier. Le décalage vaut 1 dans ce cas. Par exemple si le motif était ‘bandes’ (avec le ‘b’ de ‘bandes’ positionné sous le ‘m’ de ‘amandes’).

Implémentation d’une fonction de création d’une table de décalage en langage Python

Objectifs d’apprentissage ou d’entraînement et pré-requis (acquis antérieurs mobilisés)

  • indexation d’un dictionnaire ‘Python’ (tableau associatif)
  • ajout d’un élément dans un dictionnaire ‘Python’

On propose de représenter une table de décalage par un tableau indexé (liste en ‘Python’) de taille égale au nombre de caractères (i.e. à la longueur) du motif.

Chaque élément (= ligne) de ce tableau sera un dictionnaire.

On rappelle qu’un élément d’un dictionnaire est constitué d’un premier élément appelé « clé » (key) – la valeur de la clé est unique -, et d’un second élément appelé « valeur » (value) affectée à cette clé.

Ici, une clé d’un élément d’un dictionnaire sera un des caractères du motif et la valeur qui lui est associée sera l’index de ce caractère dans ce motif.

Par exemple, le tableau de décalage du motif « abracadabra » sera :

table_decal = [
{},
{‘a’: 0},
{‘a’: 0, ‘b’: 1},
{‘a’: 0, ‘b’: 1, ‘r’: 2},
{‘a’: 3, ‘b’: 1, ‘r’: 2},
{‘a’: 3, ‘b’: 1, ‘r’: 2, ‘c’: 4},
{‘a’: 5, ‘b’: 1, ‘r’: 2, ‘c’: 4},
{‘a’: 5, ‘b’: 1, ‘r’: 2, ‘c’: 4, ‘d’: 6},
{‘a’: 7, ‘b’: 1, ‘r’: 2, ‘c’: 4, ‘d’: 6},
{‘a’: 7, ‘b’: 8, ‘r’: 2, ‘c’: 4, ‘d’: 6},
{‘a’: 7, ‘b’: 8, ‘r’: 9, ‘c’: 4, ‘d’: 6}
]

Écrire dans le langage Python les instructions d’une fonction qui prend en argument un motif de type chaîne de caractères et qui renvoie une table de décalage conforme au format présenté ci-dessus.

Des difficultés ? Coup de pouce !

Implémentation d’une fonction de calcul de la valeur de décalage en langage Python

Objectifs d’apprentissage ou d’entraînement et pré-requis (acquis antérieurs mobilisés)

  • Extraire une valeur dans une liste (tableau indexé) de dictionnaires (tableaux associatifs)

Programmation en langage Python : compétences requises ( à acquérir, à mobiliser, à développer, à maîtriser)

  • Liste et dictionnaire : propriétés et méthodes

On veut écrire en langage Python une fonction qui renverra sous la forme d’un nombre entier la valeur du décalage du motif, à effectuer, dans le cas où un caractère du texte est différent de celui du motif.

Déterminer les arguments nécessaires à la fonction qui va effectuer ce calcul.
Écrire les instructions de cette fonction en langage Python.

Des difficultés ? Coup de pouce !

Implémentation de la fonction principale de l’algorithme de Boyer-Moore

Écrire en langage Python une fonction qui implémente l’algorithme de Boyer-Moore, et qui fera appel aux deux fonctions définies précédemment.
Montrer la terminaison de la fonction principale.

Construire un module à partir de ces trois fonctions.
Écrire un programme principal qui importe ce module et dans lequel une recherche textuelle sera effectuée.

Des difficultés ? Coup de pouce !

Comparer le coût de l’algorithme ‘naïf’ avec celui de l’algorithme de Boyer-Moore .

Article sous licence << Cliquez pour plus d’informations <<