Automates de Localisation

La mise en oeuvre informatique est basée sur les files, les états et les Automate (ou machine) à états finis.

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

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.

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) ¹⁾

1. M ← NOUVEL_AUTOMATE() : un état q₀ sans successeurs initialement
2. pour chaque mot x ∈ X faire
   1. t ← initial[M] : t est un état
   2. pour chaque lettre a de x faire
      1. p ← CIBLE(t,a) : la lettre est-elle successeur
      2. si p = NIL alors
         1. p ← NOUVEL_ETAT()
         2. Succ[t] ← Succ[] ∪ {(a,p)}
      3. t ← p
   3. terminal[t] ← vrai
3. 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).

Automate A(X) reconnaissant {aa, abaaa, abab }

                  ε
                  | \
                  a  ?!
                /   \
               a     b
               |     | \
               #     a   ?!
                    / \
                   a   b
                 / |   | 
               ?!  a   #  
                   | 
                   #        
                                 

1. x ← 'aa'
2. p ← CIBLE(racine, a)
3. p == NIL
4. p ← NOUVEL_ETAT()
5. Succ[racine] ∪= ('a', p)
6. t ← p

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).

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^*

• 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))

La fonction h satisfait les propriétés suivantes :

1. u ∈ A^* X ⇔ h(u) ∈ A^* X pour tout u ∈ A^*
2. h(ε) = ε
3. h(ua) ) h(h(u)a) pour tout (u,a) ∈ A^* × A

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. : à completer

L'automate D(X) étant complet, il est possible d'implanter sa fonction de transition par sa matrice de transition (algorithme non donné).