Automates de Localisation

Implantation Informatique

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

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 qi 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) 1)

ARBRE(X) : Construction de l'automate A(X)

  1. M ← NOUVEL_AUTOMATE() : un état q0 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).

Exemple/Exercice

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

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 :

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

1) pourquoi 'u,a,ua' et non 'u,a,v'?
 
m1ilc/search_automates.txt · Dernière modification: 2010/05/20 13:33 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki