Reconnaissance de motifs avec erreurs
un entier k, un motif p et un nom de fichier, et qui
affiche les lignes du fichier dont un sous-mot est filtré par le
motif à k erreur près au plus.
Les motifs considérés peuvent être de trois classes de difficulté
croissante. Je présente ici le cas le plus simple où le motif se réduit
Notez que cette relation entre les mots est symétrique et reflexive
On dira que les mots m et m' diffèrent de au plus k erreurs, lorsqu'il
existe k+1 mots e0, …, ek, avec
2.2 Reconnaissance des sous-mots
Selon le cours, étant donné un motif p, on peut construire un automate
fini qui reconnaît l'ensemble des mots filtrés par le motif
reconnaître les mots dont un sous-mot est filtré par p.
Dans le cas simple ou le motif se réduit à un mot m =
L'ensemble des mots filtrés par m se réduit à m et
reconnaître les sous-mots du texte qui diffèrent de m de au plus k
détecter les lignes d'un texte dont un sous-mot est filtré par un
un motif p à k erreurs près.
Dans un premier temps on pourra traiter le cas des motifs restreints à
Puis on considérera des motifs plus généraux,
Le motif « .
» filtre n'importe quel caractère, tandis que
le motif « #
» filtre n'importe quel mot.
Les motifs optionnels
Noté c?
, ce motif filtre le mot vide et le mot formé de la
De même, le motif « .?
» filtre le mot vide et tous les mots réduits
Il s'agit de compiler un motif en un automate non-déterministe,