Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

701 UMLV  Reconnaissance de motifs Problème localiser les segments d'un texte

701 UMLV  Reconnaissance de motifs Problème localiser les segments d'un texte décrits par une expression rationnelle (régulière) r texte t segment x décrit par r Applications édition : vi, emacs , sed, ed, ... recherche : grep, egrep , ... traduction : lex, sed , … langages : awk, perl, … compression : compress, gzip, … 702 UMLV  GREP unix > grep toto t.txt produit les lignes de t.txt qui contiennent le mot toto Applications recherche de fichiers par le contenu contrôle du contenu d ’un fichier Versions egrep, fgrep, ... 703 UMLV  Algorithme de base Deux phases 1 génération d’un automate A( r ) 2 analyse du texte avec A( r ) les phases peuvent être intégrées texte segments reconnus A( r ) automate équivalent r génération analyse 704 UMLV  Expression / langage Expression rationnelle r Langage représenté L( r ) a, b, … {a} , {b} , … a, b ∈A ∅, ε ∅, {mot vide} [ u , v L(u) , L(v) ] (u) L(u) u + v L(u) ∪L(v) uv { xy | x ∈L(u), y ∈L(v) } u* { x1x2…xk | k ≥0, xi ∈L(u) } 1(0+1)*0 {écritures binaires des entiers pairs} (a*b)*a* {suites finies de a et b} (c*l)*c*f {fichiers textes} 705 UMLV  Analyse des expressions Une grammaire des expressions rationnelles E →T | T ‘+’ E T →F | F T F →S G G →ε | ‘*’ G S →‘a’ | ‘b’ | ‘∅’ | ‘ε ’ | ‘(’ E ‘)’ E expression, T terme F facteur, S facteur simple (a+b)*c {suites finies de a et b terminées par c} 706 UMLV  Analyse de (a+b)*c Arbre de l’analyse Grammaire E →T | T ‘+’ E T →F | F T F →S G G →ε | ‘*’ G S →‘a’ | ‘b’ | ‘∅’ | ‘ε’ | ‘(’ E ‘)’ E T S F G E T G ‘(’ ‘)’ T T E ‘+’ G F S ‘a’ ‘ε’ G F S ‘b’ ‘ε’ G F S ‘c’ ‘ε’ ‘*’ ‘ε’ 707 UMLV  Diagrammes syntaxiques Expression Terme Facteur Expression Terme ‘+’ Terme Facteur Expression ‘a’ ‘*’ ‘ε’ ‘∅’ ‘b’ ‘(’ ‘)’ 708 UMLV  Algorithme d’analyse caractère car; /* caractère suivant, global */ Analyse(expression rationnelle r){ car ←premier caractère de r ; Expression(); si(car ≠fin d’expression) erreur(); } Expression(){ Terme(); si(car = ‘+’){ car ←caractère suivant; Expression(); } } Terme(){ Facteur(); si(car ∈{‘a’, ‘b’, ‘∅’, ‘ε’, ‘(’}) Terme(); } 709 UMLV  Algorithme d’analyse (suite) Facteur(){ si(car ∈{‘a’, ‘b’, ‘∅’, ‘ε’}){ car ←caractère suivant; }sinon si(car = ‘(’){ car ←caractère suivant; Expression(); si(car = ‘)’) car ←caractère suivant; sinon erreur(); }sinon erreur(); tant que(car = ‘*’) car ←caractère suivant; } 710 UMLV  Diagrammes syntaxiques (autre) Expression Terme Facteur Terme ‘+’ Facteur Expression ‘a’ ‘*’ ‘ε’ ‘∅’ ‘b’ ‘(’ ‘)’ 711 UMLV  Algorithme d’analyse (autre) caractère car; /* caractère suivant, global */ Analyse(expression rationnelle r){ car ←premier caractère de r ; Expression(); si(car ≠fin d’expression) erreur(); } Expression(){ Terme(); tant que(car = ‘+’){ car ←caractère suivant; Terme(); } } Terme(){ répéter Facteur(); tant que(car ∈{‘a’, ‘b’, ‘∅’, ‘ε’, ‘(’}) } 712 UMLV  Expression / automate A( r ) automate associé à l’expression rationnelle r sur l ’alphabet A Invariants de la construction A( r ) possède un seul état initial i un seul terminal t aucune flèche n’entre dans i aucune flèche ne sort de t Graphique A( r ) : i t r 713 UMLV  Transformation Expr. rat. Aut. équiv. a ε ∅ (u) uv u a Expr. rat. Aut. équiv. u + v u* u v u u v 714 UMLV  Automate obtenu Proposition A( r ) reconnaît le langage L( r ) Propriétés supplémentaires A( r ) possède 2.|r | états, sans compter ‘(‘ ni ‘)’ de chaque état sortent au plus 2 flèches si exactement 2, elles sont sans étiquette sur chaque état arrivent au plus 2 flèches 715 UMLV  Exemple Expression : (b* + aa + ab)*b bab reconnu ? non, mais infinité de chemins d’origine 17 et d'étiquette bab 2 3 4 9 10 15 5 6 7 8 16 11 12 13 14 17 18 19 20 b a a a b 1 b 716 UMLV  Implantation adaptée état = indice table des flèches struct{ caractère lettre; état suiv1, suiv2; } Trans[MAX]; automate (identifié à 2 états) struct{ état initial; état terminal; } automate; Trans 1 ‘ b ’ 2 2 1 4 3 1 4 4 10 5 ‘ a ’ 6 6 7 7 ‘ a ’ 8 8 10 9 3 5 10 16 11 ‘ a ’ 12 12 13 13 ‘ b ’ 14 14 16 15 9 11 16 15 18 17 15 18 18 19 19 ‘ b ’ 20 20 initial = 17 terminal = 20 p ‘a’ p1 q q1 q2 717 UMLV  Algorithme de traduction Analyse(expression rationnelle r){ car ←premier caractère de r ; A ←Expression(); si(car ≠fin d’expression) erreur(); sinon retour A; } Production de l ’automate A( r ) associé à l ’expression rationnelle r 718 UMLV  Algorithme de traduction (suite) Expression(){ A ←Terme(); tant que(car = ‘+’){ car ←caractère suivant; B ←Terme(); A ←Union(A,B); } retour A; } Terme(){ A ←Facteur(); tant que(car ∈{‘a’, ‘b’, ‘∅’, ‘ε’, ‘(’}){ B ←Facteur(); A ←Produit(A,B); } retour A; } 719 UMLV  Algorithme de traduction (suite) Facteur(){ si(car ∈{‘a’, ‘b’, ‘∅’, ‘ε’}){ A ←Automate-élémentaire(car); car ←caractère suivant; }sinon si(car = ‘(’){ car ←caractère suivant; A ←Expression(); si(car = ‘)’) car ←caractère suivant; sinon erreur(); }sinon erreur(); tant que(car = ‘*’){ A ←Etoile(A); car ←caractère suivant; } retour A ; } 720 UMLV  Reconnaissance (avec automate non-déterministe) Écrire une fonction booléen reconnaît( automate A, mot x ) qui prend la valeur vraie ssi il existe un chemin d'étiquette x depuis A.initial jusqu’à A.terminal Programmation par essais et erreurs (attention aux cycles) programmation dynamique (mémorisation des états possibles) Clôture clôture(p) = { états accessibles à partir p par chemins sans étiquette } 721 UMLV  Clôture Clôture de 17 = {1,3,4,5,9,10,11,15,16,17,18,19} 2 3 4 9 10 15 5 6 7 8 16 11 12 13 14 17 18 19 20 b a a a b 1 b 17 15 18 19 11 9 5 3 1 4 10 16 722 UMLV  Reconnaissance État initial 17 Clôture {1, 3, 4, 5, 9, 10, 11, 15, 16, 17, 18, 19} Expression : (b* + aa + ab)*b Reconnaissance de bab 2 3 4 9 10 15 5 6 7 8 16 11 12 13 14 17 18 19 20 b a a a b 1 b 723 UMLV  Reconnaissance (suite) {1, 3, 4, 5, 9, 10, 11, 15, 16, 17, 18, 19} Transition par b {2, 20} Clôture {1, 2, 3, 4, 5, 9, 10, 11, 15, 16, 18 , 19, 20} Expression : (b* + aa + ab)*b Reconnaissance de bab 2 3 4 9 10 15 5 6 7 8 16 11 12 13 14 17 18 19 20 b a a a b 1 b 724 UMLV  {1, 2, 3, 4, 5, 9, 10, 11, 15, 16, 18, 19, 20} Transition par a {6, 12} Clôture {6, 7, 12, 13} Expression : (b* + aa + ab)*b Reconnaissance de bab 2 3 4 9 10 15 5 6 7 8 16 11 12 13 14 17 18 19 20 b a a a b 1 b Reconnaissance (suite) 725 UMLV  {6, 7, 12, 13} Transition par b {14} Clôture {1, 3, 4, 5, 9, 10, 11, 14, 15, 16, 18, 19} bab non reconnu car 20 non atteint Expression : (b* + aa + ab)*b Reconnaissance de bab 2 3 4 9 10 15 5 6 7 8 16 11 12 13 14 17 18 19 20 b a a a b 1 b Reconnaissance (suite) 726 UMLV  Algorithme de reconnaissance booléen reconnaît(automate A, mot x){ ensemble E; E ←clôture(A.initial); tant que(non fin de x){ car ←lettre suivante de x; E ←clôture(transition(E,car)); } si(A.terminal ∈E) retour(vrai); sinon retour(faux); } Lecture séquentielle du mot. Mémorisation (tampon) d'une seule lettre de x. Temps : O(nb états de A . | x |) (si bonne gestion de l ’ensemble E) 727 UMLV  Recherche de motif Motif défini par l'expression rationnelle r A( r ) automate associé à r Motif dans le texte Principe de la recherche comme reconnaissance avec : ajout l’état initial à chaque position arrêt de la recherche dès que l’état terminal est atteint texte t segment x reconnu par A( r ), x ∈L(r) 728 UMLV  Algorithme de recherche booléen recherche(automate A, mot t){ ensemble E; E ←clôture(A.initial); tant que(non fin de t){ car ←lettre suivante de t; E ←clôture({A.initial}∪transition(E,car)); si(A.terminal ∈E) retour(vrai); } retour(faux); } Lecture séquentielle du texte. Mémorisation (tampon) d'une seule lettre de t. Temps : O(nb états de A . | t |) (si bonne gestion de l ’ensemble uploads/s3/ reconnaissance-de-motifs.pdf