====== Automates de Localisation ====== ===== Implantation Informatique ===== La mise en oeuvre informatique est basée sur les files, les états et les [[m1ilc:search_fsm|]]. Opérations de base pour les files : * FILE_VIDE() crée puis retourne (un pointeur sur) une file vide * FILE_EST_VIDE(F) retourne vrai si la file F est vide et faux sinon * ENFILER(F,x) ajoute l'élément x en queue de la file F (c'est une file, pas une pile) * TETE(F) retourne l'élément situé en tête de la file F **sans l'enlever** * DEFILER(F) supprime l'élément en tête de la file F * DEFILEMENT(F) retourne l'élément en tête de la file F et le supprime de la file (''TETE(F);DEFILER(F);'') * LONGUEUR(F) retourne le nombre d'éléments dans la file F ==== Les états ==== Un automate comporte un ensemble A des états "acceptants"; ici on considère qu'un état y appartenant a l'attribut //terminal//. Un automate a aussi une application T: Q\times \Sigma \rightarrow Q dite les transitions. Ici on considère que les états figurant dans les transitions de q_i sont ses successeurs (//Succ//). On propose deux opérations standard sur les états : * NOUVEL_ETAT() : crée puis retourne (un pointeur sur) un état non terminal d'ensemble des successeurs étiquetés vide. * CIBLE(p,a) : retourne un état sachant l'état p et l'étiquette a, ou la valeur spéciale NIL si une telle étiquette n'existe pas. Autrement dit, s'il existe un état q tel que (a,q) ∈ Succ[p]-- T(q,a)=p -- alors c'est lui. ===== Arbre d'un dictionnaire ===== Soient X⊆ A^* un __dictionnaire__ sur A, c'est à dire un langage fini non vide ne contenant pas le mode vide ε, et y ∈ A^* le texte dans lequel on cherche à localiser toutes les occurrences de mots de X. L'automate A(X) déterministe, appelé arbre du dictionnaire de X, reconnaissant X est défini de la façon suivante : * Préf(X) : l'ensemble des états * ε : état initial * X : l'ensemble des états terminaux (acceptant) * flèches (transitions) sont de la forme :(u,a,ua) ((pourquoi 'u,a,ua' et non 'u,a,v'?)) ==== ARBRE(X) : Construction de l'automate A(X) ==== - M <- NOUVEL_AUTOMATE() : un état q₀ sans successeurs initialement - pour chaque mot x ∈ X faire - t <- initial[M] : t est un état - pour chaque lettre a de x faire - p <- CIBLE(t,a) : la lettre est-elle successeur - si p = NIL alors - p <- NOUVEL_ETAT() - Succ[t] <- Succ[] ∪ {(a,p)} - t <- p - terminal[t] <- vrai - retourner M Pour chaque mot de X, on repars de la racine ε et suit l'arbre de parent en fils tant qu'on retrouve la lettre suivant du mot dans un noeud fils. Lorsqu'on ne trouve plus un fils correspondant à la lettre, on on crée un et poursuit le développement de l'arbre à partir de lui (on crée des fils successivement pour chacune des lettres restant de x). === Exemple/Exercice === Automate A(X) reconnaissant {aa, abaaa, abab } ε | \ a ?! / \ a b | | \ # a ?! / \ a b / | | ?! a # | # - x <- 'aa' - p <- CIBLE(racine, a) - p == NIL - p <- NOUVEL_ETAT() - Succ[racine] ∪= ('a', p) - t <- p ===== Localisation de Plusieurs Mots ===== Un automate D(X) déterministe det complet permet de reconnaître le langage A^*X. Ses états sont les préfixes des mots de X. Ainsi, lors d'une lecture séquentielle du texte y, il suffit de ne retenir que **le plus long des suffixes de la partie de texte déjà lue qui est un préfixe d'un mot de X**. D(X) n'est pas minimal en général mais il est relativement simple à construire. Il est aussi à la base des différentes variantes d'automates. D(X) possède les mêmes états que A(X) et le même état initial. Il contient les états terminaux et les flèches de A(X). === Automate-dictionnaire === Afin de formaliser l'automate de localisation du dictionnaire X ⊆ A^* on introduit la fonction * h : A^* -> Préf(X) définie par * h(u) = plus long suffixe de u qui appartient à Préf(X), pour tout mot u ∈ A^* === L'automate D(X) est déterministe et complet === * comme A(X) * Préf(X) = ensemble des états * ε = état initial * nouveautés : * terminaux (acceptants) = Préf(X) ∩ A^* X * flèches sont de la forme (u, a, h(ua)) === Proposition === La fonction h satisfait les propriétés suivantes : - u ∈ A^* X <=> h(u) ∈ A^* X pour tout u ∈ A^* - h(ε) = ε - h(ua) ) h(h(u)a) pour tout (u,a) ∈ A^* × A == Preuve == 1. On pose u ∈ A^* X. * => u = vx avec v ∈ A^* et x ∈ X * => x Suff h(u), par définition de h * => h(u) ∈ A^* X. * Réciproquement on pose h(u) ∈ A^* X. * => u ∈ A^* X. parce que h(u) Suff u etc. FIXME : à completer ==== Construction de l'automate-dictionnaire ==== ==== Localisation des occurrences ==== ==== Implantation par matrice de transition ==== L'automate D(X) étant complet, il est possible d'implanter sa fonction de transition par sa matrice de transition (algorithme non donné). ===== Automate avec fonction de suppléance ===== ===== Automate avec optimisation de la fonction de suppléance ===== ===== Implantation avec successeur par défaut =====