NUMERIQUE ET SCIENCES INFORMATIQUES

Niveau : Terminale générale, enseignement de spécialité NSI

Recherche Textuelle

1 - Introduction

Tout logiciel de traitement de texte possède une fonction de recherche textuelle, permettant de trouver un mot ou une partie d'un mot (chaine ou sous-chaine) appelé motif. Il en est de même pour les navigateurs internet. Appuyer sur ctrl f puis rechercher dans la page la chaine "mot"

Recherche naïve

Un premier algorithme dit naïf permet de comparer la première lettre de la chaine recherchée en parcourant le texte de gauche à droite

Principe :

L'une des citations de Laurent de Lavoisier est la suivante : "rien ne se perd, rien ne se crée, tout se transforme".

Cherchons la chaine "rien" dans le texte de la citation.

Le motif est trouvé dans le texte, on rajoute son indexe (0 ou 17) à la liste des indexes puis on le décale d'un cran vers la droite
La recherche se termine lorsqu'on atteint le rang : longueur du texte - longueur du motif

Algorithme

Fonction recherche_naive(texte,motif)
m ← longueur du motif
n ← longueur du texte - m + 1
positions ← []
pour i variant de 0 à n faire
	si motif=texte[i...i+m] alors
		ajouter i à la liste positions
retourne positions

Code python

def recherche_naive(texte,motif): print(recherche_naive("rien ne se perd, rien ne se crée, tout se transforme.","rien")

Exécuter

Algorithme de Boyer Moore Horspool :

L’algorithme de Boyer-Moore-Horspool ou Horspool est un algorithme de recherche de sous-chaîne publié en 1980 par Nigel Horspool, un professeur à l’université de Victoria au Canada. Il consiste en une simplification de l’algorithme de Boyer-Moore qui ne garde que la première table de saut.

Principe :

L’algorithme de Boyer-Moore effectue la vérification, c’est-à-dire qu’il tente d’établir la correspondance entre le motif et le texte à une certaine position, à l’envers.

• Si la dernière lettre du motif ne correspond pas à la lettre du texte et qu'elle n'existe pas dans le motif alors, on décale le motif vers la droite correspondant à sa longueur.
• Si la dernière lettre du texte comparée existe dans le motif on décale le motif du nombre de cases permettant d'aligner la dernière lettre du texte et celle existant dans le motif

exemples de décalages lorsque la lettre existe dans le motif :

Exemple 1	Exemple 2
Texte s f o r Saut 3 2 1 Motif r i e n	Texte r i e Saut 3 2 1 Motif r i e n

La structure choisie peut être un dictionnaire dont la clé représente la lettre : saut={"r":3,"i":2,"e":1} toute autre lettre impose un saut de la longueur du motif, ici 4 cases.

Voici les opérations que l'on peut effectuer sur un dictionnaire :

• ajouter : on associe une nouvelle valeur à une nouvelle clé
  

  saut['n']=7 # on associe à le clé 'n' la valeur 7.
  print(saut)

  {'e': 1, 'i': 2, 'n': 7, 'r': 3}

• modifier : on modifie un couple clé:valeur en remplaçant la valeur courante par une autre valeur (la clé restant identique)
  

  saut['e']=4
  print(saut)

  {'e': 4, 'i': 2, 'n': 7, 'r': 3}

• supprimer : on supprime une clé (et donc la valeur qui lui est associée)
  

  saut.pop('n')
  print(saut)

  {'e': 4, 'i': 2, 'r': 3}

• rechercher : on recherche une valeur à l'aide de la clé associée à cette valeur.
  

  print(saut['e'])

  4

• afficher clés : on peut afficher toutes les clés existantes.
  

  print(saut.keys())

  dict_keys(['r', 'e', 'i'])

• clé présente : retourne vrai si la clé est dans le dictionnaire sinon retourne faux.
  

  print('n' in saut)

  False

Cas où le motif contient des lettres identiques

On recherche "rien ne se" : e, espace et n apparraissent plusieurs fois. Il faut donc éviter les sauts trop grand.
Le tableau cidessous donne les valeurs des sauts pour chaque lettre :

Saut	9	8				4	3	2	1
Motif	r	i	e	n		n	e		s	e

Contenu du dictionnaire saut :

saut={'s': ?, 'n': ?, 'e': ?, 'r': ?, 'i': ?, ' ': ?}

Algorithme

Fonction dic_saut(motif,avd)
# Parcourt le motif de gauche à droite jusqu'à l'avant dernière lettre
début
	saut ← {}
	pour i variant de 0 à avd faire
		ajouter au dictionnaire saut la clé [motif[i]] et la valeur avd-i
	retourne saut
fin

Fonction recherche(texte,motif)
début
	lm ← longueur(motif)
	saut ← dic_saut(motif,lm-1)
	lt ← longueur du texte
	positions ← []
	i ← lm
	tant que i ≤ lt alors
		si motif = texte[i-lm...i] alors
			ajouter positions i-lm
			i ← i+lm
		sinon
			si la clé texte[i-1] est présente dans saut alors
				i ← i + valeur de la clé texte[i-1] de saut
			sinon
				i ← i + lm
	retourne positions
fin

Code python

def dic_saut(motif,avd): return saut def recherche(texte,motif): return positions print(recherche("rien ne se perd, rien ne se crée, tout se transforme.","rien"))

Exécuter le code

• Placez un compteur dans les deux programmes afin de connaître le nombre de comparaisons permettant de trouver le motif

Nombre de comparaisons de la recherche naïve :

Nombre de comparaisons de la recherche de Boyer-Moore-Horspool :

• modifier le programme pour qu'il affiche le nombre de fois que la "e" apparaît dans le texte ci-dessous

Pour charger le texte on procède comme suit :

fichier=open("Texte.txt,"r")
texte= fichier.read()   
fichier.close()  

Lettre aux instituteurs et institutrices Vous tenez en vos mains l'intelligence et l'âme des enfants ; vous êtes responsables de la patrie. Les enfants qui vous sont confiés n'auront pas seulement à écrire et à déchiffrer une lettre, à lire une enseigne au coin d'une rue, à faire une addition et une multiplication. Ils sont Français et ils doivent connaître la France, sa géographie et son histoire : son corps et son âme. Ils seront citoyens et ils doivent savoir ce qu'est une démocratie libre, quels droits leur confère, quels devoirs leur impose la souveraineté de la nation. Enfin ils seront hommes, et il faut qu'ils aient une idée de l'homme, il faut qu'ils sachent quelle est la racine de toutes nos misères : l'égoïsme aux formes multiples ; quel est le principe de notre grandeur : la fierté unie à la tendresse. Il faut qu'ils puissent se représenter à grands traits l'espèce humaine domptant peu à peu les brutalités de la nature et les brutalités de l'instinct, et qu'ils démêlent les éléments principaux de cette œuvre extraordinaire qui s'appelle la civilisation. Il faut leur montrer la grandeur de la pensée ; il faut leur enseigner le respect et le culte de l'âme en éveillant en eux le sentiment de l'infini qui est notre joie, et aussi notre force, car c'est par lui que nous triompherons du mal, de l'obscurité et de la mort. Eh quoi ! Tout cela à des enfants ! Oui, tout cela, si vous ne voulez pas fabriquer simplement des machines à épeler. Je sais quelles sont les difficultés de la tâche. Vous gardez vos écoliers peu d'années et ils ne sont point toujours assidus, surtout à la campagne. Ils oublient l'été le peu qu'ils ont appris l'hiver. Ils font souvent, au sortir de l'école, des rechutes profondes d'ignorance et de paresse d'esprit, et je plaindrais ceux d'entre vous qui ont pour l'éducation des enfants du peuple une grande ambition, si cette grande ambition ne supposait un grand courage. J'entends dire, il est vrai : À quoi bon exiger tant de l'école ? Est-ce que la vie elle-même n'est pas une grande institutrice ? Est-ce que, par exemple, au contact d'une démocratie ardente, l'enfant devenu adulte ne comprendra point de lui-même les idées de travail, d'égalité, de justice, de dignité humaine qui sont la démocratie elle-même ? Je le veux bien, quoiqu'il y ait encore dans notre société, qu'on dit agitée, bien des épaisseurs dormantes où croupissent les esprits. Mais autre chose est de faire, tout d'abord, amitié avec la démocratie par l'intelligence ou par la passion. La vie peut mêler, dans l'âme de l'homme, à l'idée de justice tardivement éveillée, une saveur amère d'orgueil blessé ou de misère subie, un ressentiment et une souffrance. Pourquoi ne pas offrir la justice à des cœurs tout neufs ? Il faut que toutes nos idées soient comme imprégnées d'enfance, c'est-à-dire de générosité pure et de sérénité. Comment donnerez-vous à l'école primaire l'éducation si haute que j'ai indiquée ? Il y a deux moyens. Il faut d'abord que vous appreniez aux enfants à lire avec une facilité absolue, de telle sorte qu'ils ne puissent plus l'oublier de la vie et que, dans n'importe quel livre, leur œil ne s'arrête à aucun obstacle. Savoir lire vraiment sans hésitation, comme nous lisons vous et moi, c'est la clef de tout. Est-ce savoir lire que de déchiffrer péniblement un article de journal, comme les érudits déchiffrent un grimoire ? J'ai vu, l'autre jour, un directeur très intelligent d'une école de Belleville, qui me disait : « Ce n'est pas seulement à la campagne qu'on ne sait lire qu'à peu près, c'est-à-dire point du tout; à Paris même, j'en ai qui quittent l'école sans que je puisse affirmer qu'ils savent lire.» Vous ne devez pas lâcher vos écoliers, vous ne devez pas, si je puis dire, les appliquer à autre chose tant qu'ils ne seront point par la lecture aisée en relation familière avec la pensée humaine. Qu'importent vraiment à côté de cela quelques fautes d'orthographe de plus ou de moins, ou quelques erreurs de système métrique ? Ce sont des vétilles dont vos programmes, qui manquent absolument de proportion, font l'essentiel. [...] Sachant bien lire, l'écolier, qui est très curieux, aurait bien vite, avec sept ou huit livres choisis, une idée, très générale, il est vrai, mais très haute de l'histoire de l'espèce humaine, de la structure du monde, de l'histoire propre de latere dans le monde, du rôle propre de la France dans l'humanité. Le maître doit intervenir pour aider ce premier travail de l'esprit ; il n'est pas nécessaire qu'il dise beaucoup, qu'il fasse de longues leçons ; il suffit que tous les détails qu'il leur donnera concourent nettement à un tableau d'ensemble. De ce que l'on sait de l'homme primitif à l'homme d'aujourd'hui, quelle prodigieuse transformation ! et comme il est aisé à l'instituteur, en quelques traits, de faire sentir à l'enfant l'effort inouï de la pensée humaine ! Seulement, pour cela, il faut que le maître lui-même soit tout pénétré de ce qu'il enseigne. Il ne faut pas qu'il récite le soir ce qu'il a appris le matin; il faut, par exemple, qu'il se soit fait en silence une idée claire du ciel, du mouvement des astres; il faut qu'il se soit émerveillé tout bas de l'esprit humain, qui, trompé par les yeux, a pris tout d'abord le ciel pour une voûte solide et basse, puis a deviné l'infini de l'espace et a suivi dans cet infini la route précise des planètes et des soleils; alors, et alors seulement, lorsque, par la lecture solitaire et la méditation, il sera tout plein d'une grande idée et tout éclairé intérieurement, il communiquera sans peine aux enfants, à la première occasion, la lumière et l'émotion de son esprit. Ah ! sans doute, avec la fatigue écrasante de l'école, il vous est malaisé de vous ressaisir ; mais il suffit d'une demi-heure par jour pour maintenir la pensée à sa hauteur et pour ne pas verser dans l'ornière du métier. Vous serez plus que payés de votre peine, car vous sentirez la vie de l'intelligence s'éveiller autour de vous. Il ne faut pas croire que ce soit proportionner l'enseignement aux enfants que de le rapetisser. Les enfants ont une curiosité illimitée, et vous pouvez tout doucement les mener au bout du monde. Il y a un fait que les philosophes expliquent différemment suivant les systèmes, mais qui est indéniable : « Les enfants ont en eux des germes, des commencements d'idées. » Voyez avec quelle facilité ils distinguent le bien du mal, touchant ainsi aux deux pôles du monde ; leur âme recèle des trésors à fleur de terre : il suffit de gratter un peu pour les mettre à jour. Il ne faut donc pas craindre de leur parler avec sérieux, simplicité et grandeur. Je dis donc aux maîtres, pour me résumer : lorsque d'une part vous aurez appris aux enfants à lire à fond, et lorsque d'autre part, en quelques causeries familières et graves, vous leur aurez parlé des grandes choses qui intéressent la pensée et la conscience humaine, vous aurez fait sans peine en quelques années œuvre complète d'éducateurs. Dans chaque intelligence il y aura un sommet, et, ce jour-là, bien des choses changeront. Jean Jaurès, La Dépêche, journal de la démocratie du midi, 15 janvier 1888.

Résultats obtenus avec la recherche naïve :

Nombre de comparaisons : 7152
Nombre de "e" : 848
Nombre de comparaisons : 7146
Nombre de "enfants" : 10
Nombre de comparaisons : 7139
Nombre de "intérieurement" : 1

Résultats obtenus avec l'algorithme de Boyer Moore Horspool :

Nombre de tests : 7152
Nombre de "e" : 848
Nombre de tests : 1196
Nombre de "enfants" : 10
Nombre de tests : 702
Nombre de "intérieurement" : 1

Conclure sur l’efficacité de l’algorithme suivant la taille du motif.

Fond :  Texte :  Tables :  Thème du langage: default 3024-day 3024-night abbott abcdef ambiance ayu-dark ayu-mirage base16-dark base16-light bespin blackboard cobalt colorforth darcula dracula duotone-dark duotone-light eclipse elegant erlang-dark gruvbox-dark hopscotch icecoder idea isotope juejin lesser-dark liquibyte lucario material material-darker material-palenight material-ocean mbo mdn-like midnight monokai moxer neat neo night nord oceanic-next panda-syntax paraiso-dark paraiso-light pastel-on-dark railscasts rubyblue seti shadowfox solarized dark solarized light the-matrix tomorrow-night-bright tomorrow-night-eighties ttcn twilight vibrant-ink xq-dark xq-light yeti yonce zenburn

Contenu sous licence CC BY-NC-SA 3.0
Pascal Hassenforder 21/11/2020
source : Gisèle Bareux