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
à un mot m.
Le mot m' diffère de au plus une erreur d'un autre mot m,
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
l'automate est déterministe et facile à construire.
notés e0, … , en, son état initial est e0, son état
Voici par exemple l'automate associé au mot coucou.
Utiliser cet automate pour reconnaître si un mot quelconque est égal à
coucou n'a pas d'intérêt, mais cet automate se revèle
Notons que, si à un instant quelconque l'état final en appartient à Ei,
alors une occurence du mot m est identifiée.
bits, voire par des entiers quand la taille du mot m est inférieure
automates sont parfois dénommés shift-or.
Les automates se révèlent encore plus intéressants lorsqu'il s'agit de
reconnaître les sous-mots du texte qui diffèrent de m de au plus k
En se limitant pour simplifier à une seule erreur,
Notons µj le préfixe de taille j de m.
détecter les lignes d'un texte dont un sous-mot est filtré par un
un motif p à k erreurs près.
On se simplifiera la vie en ne considérant que le jeu de caractère
Dans un premier temps on pourra traiter le cas des motifs restreints à
un mot.
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,