Recherche textuelle

Identification du problème posé

Soit le texte suivant :

« 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)

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

Résolution du problème, avec un premier algorithme

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.
Il existe une occurrence du motif à la position p si la séquence de caractères du texte compris entre p et p + lm est identique au motif.

Proposer un algorithme permettant de résoudre le problème posé.

Complétez les instructions qui suivent écrites en Python afin qu’elles exécutent l’algorithme proposé ci-dessus (« Un algorithme possible ») en indiquant ce qui convient à votre avis, là où se trouvent des ‘???’
Écrivez une courte documentation pour cette fonction ainsi que quelques lignes de commentaires indiquant les grandes étapes de l’algorithme.

def recherche(t, m):
	lt = ???
	lm = ???
	lp = ???
	for ??? in range (???):
		s = ''
		for car in range(p, ???):
			s = s + t[???]
		if s ??? m :
			lp.append(???)
	return lp

Fiche-réponse – Document numérique à télécharger
Fichier .py contenant le code ci-dessus à compléter ainsi qu’un jeu de tests.

Évaluation du coût de l’algorithme

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

Vous disposez de 6 textes de longueur croissante.
Dans un programme écrit en Python, pour ouvrir un fichier au format « txt » et charger son contenu dans une variable de type « string » il faut ajouter les instructions suivantes :

    • fichier_texte = open("exemple.txt")
    • texte = fichier_texte.read().replace("\n", "")
    • fichier_texte.close()