Présentation de l'extension Python de OpenFST¶
OpenFST est une boîte à outil de machine finies orientée principalement vers les transducteurs finis mais capable de créer et manipuler des automates finis. C'est une librairie C++ qu'on peut utiliser en C++ ou via des commandes Shell ou encore avec une interface Python (ce que nous allons utiliser ici).
Pour la création des automates, on part d'un fichier de symboles qui donne l'alphabet avec pour chaque symbole un entier qui sera sa représentation interne dans les structures de données. L'entier 0 est toujours associé à epsilon, pour les autres symboles, on choisit ce qu'on veut (code ascii, codepoint unicode ou n'importe quel autre codage).
Un automate peut être créé ex nihilo en donnant une représentation textuelle qui est une séquence finie de lignes. Chaque ligne donne un arc ou le fait qu'un état est final. Pour spécifier un arc, on donne l'état de départ, l'état d'arrivée et le symbole, séparés par un ou plusieurs espaces. L'état initial est par convention l'état de départ du premier arc donné. Les états finals sont donnés avec juste l'état seul sur une ligne.
import pywrapfst as fst
import os
from IPython.display import Image,display
# Création de l'alphabet
alpha = fst.SymbolTable()
alpha.add_symbol('<eps>')
alpha.add_symbol('a')
alpha.add_symbol('b')
alpha.add_symbol('c')
print(alpha)
# Pour créer un nouvel automate, un objet fst.Compiler
comp = fst.Compiler(acceptor = True, isymbols = alpha, osymbols = alpha,
keep_isymbols = True, keep_osymbols = True)
# on écrit les chaînes définissant quatre arcs. 0 est l'état initial
comp.write("0 1 a")
comp.write("0 1 b")
comp.write("1 1 b")
comp.write("1 2 c")
# 2 est final
comp.write("2")
# on créer l'automate
auto = comp.compile()
# on peut afficher l'automate au format textuel
print(auto)
print(type(auto))
print(auto.num_states())
<SymbolTable '<unspecified>' at 0x7fbc2554a5b0> 0 1 a a 0 1 b b 1 1 b b 1 2 c c 2 <class 'pywrapfst.MutableFst'> 3
# Pour afficher une représentation graphique, il faut passer par un fichier
auto.draw('nomfichier.dot', portrait=True, acceptor=True)
# Cela crée un fichier au format graphviz dot (description de graphes)
# Affichons le contenu de ce fichier textuel
fil = open('nomfichier.dot','r')
str = fil.read()
print(str)
digraph FST {
rankdir = LR;
size = "8.5,11";
center = 1;
orientation = Portrait;
ranksep = "0.4";
nodesep = "0.25";
0 [label = "0", shape = circle, style = bold, fontsize = 14]
0 -> 1 [label = "a", fontsize = 14];
0 -> 1 [label = "b", fontsize = 14];
1 [label = "1", shape = circle, style = solid, fontsize = 14]
1 -> 1 [label = "b", fontsize = 14];
1 -> 2 [label = "c", fontsize = 14];
2 [label = "2", shape = doublecircle, style = solid, fontsize = 14]
}
# Il faut ensuite transformer cette description en image
# avec une commande shell. Ici, image png. D'autres formats sont possibles
# (pdf, png, ps, jpg, gif)
os.system('/usr/bin/dot -Tpng nomfichier.dot > nomfichier.png')
# Affichons le contenu du fichier
display(Image(filename='nomfichier.png'))
# Note : dans l'image, l'état initial est en gras.
Création d'un automate avec des méthodes¶
On peut créer un automate en ajoutant des arcs et des états et en spécifiant l'état initial et les états finals
# Création d'un automate vide
auto2 = comp.compile()
print(auto2.num_states())
0
st1 = auto2.add_state()
st2 = auto2.add_state()
auto2.add_arc(st1,fst.Arc(alpha.find('a'),alpha.find('a'),0,st2))
print('nombre d états : ',auto2.num_states())
auto2.set_start(st1)
auto2.set_final(st2)
print(auto2)
nombre d états : 2 0 1 a a 1
Méthodes destructives et fonctions¶
Certaines opérations d'automates sont implémentées sous forme de méthodes des objets automates. Généralement, ces méthodes sont destructives, elles modifient l'automate sur lequel elles sont appelées. L'automate modifié est le résultat de l'opération.
D'autres opérations sont données sous forme de fonctions non destructives qui créent un nouvel automate résultat de l'opération.
# Exemple de méthode destructive : concat
print('auto avant concaténation', auto)
print('-------------')
print('auto2 avant concaténation', auto2)
auto.concat(auto2)
print('auto après concaténation\n', auto)
print('-------------')
print('auto2 après concaténation\n', auto2)
auto avant concaténation 0 1 a a 0 1 b b 1 1 b b 1 2 c c 2 ------------- auto2 avant concaténation 0 1 a a 1 auto après concaténation 0 1 a a 0 1 b b 1 1 b b 1 2 c c 2 3 <eps> <eps> 3 4 a a 4 ------------- auto2 après concaténation 0 1 a a 1
# autre exemple de méthode : closure (étoile)
print('auto2 avant closure\n', auto2)
auto2.closure()
print('auto2 après closure\n', auto2)
auto2 avant closure 0 1 a a 1 auto2 après closure 2 0 <eps> <eps> 2 0 1 a a 1 0 <eps> <eps> 1
Exemples de fonctions¶
Parmi les fonctions offertes par le module pywrapfst, il y a l'intersection, la différence et la déterminisation. Mais ces opérations ne peuvent pas s'appliquer à n'importe quel automate. L'intersection et la différence nécessitent d'avoir deux automates déterministes, la déterminisation nécessite d'avoir un automate sans epsilon-transition.
On peut élmiminer les epsilon-transitions avec la méthode rmepsilon.
# exemple de fonction non destructive
# auto3 : a*
comp.write("0 0 a")
comp.write("0")
auto3 = comp.compile()
# auto4 : (aa|ab)+
comp.write("0 1 a")
comp.write("1 2 a")
comp.write("1 2 b")
comp.write("2 1 a")
comp.write("2")
auto4 = comp.compile()
auto5 = fst.intersect(auto3,auto4)
print('auto5\n',auto5)
auto6 = fst.difference(auto3,auto4)
print('auto6\n',auto6)
auto5 0 1 a a 1 2 a a 2 1 a a 2 auto6 0 1 a a 0 1 2 a a 1 2 1 a a
Optimisation d'un automate¶
Pour optimiser un automate, il faut enchaîner dans l'ordre les opérations suivantes :
- rmepsilon (méthode, destructive)
- determinize (fonction, non destructive)
- minimize (méthode, destructive) On peut écrire une fonction qui réalise cet enchaînement.
Méthodes destructive et préservation des opérandes¶
Si l'on veut préserver un opérande d'une méthode destructive, il faut faire une copie de l'objet (méthode copy) avant d'appeler la méthode sur la copie. La copie est modifiée, mais pas l'objet d'origine.
Fonctions utilisées dans l'exemple des dates¶
Pour implémenter en Python un automate des dates correctes, nous définissons quatre fonctions auxiliaires. La première sert à créer un automate pour un langage fini donné en extension. Cet automate comprend un état initial, un état final et pour chaque chaîne, un chemin distinct allant de l'état initial à l'état final.
Les deux fonctions suivante réalisent respectivement la disjonction et la concaténation de plusieurs automates en faisant les copies nécessaires pour ne pas modifier ces automates et en faisant les optimisations sur le résultat.
La dernière fonction automatisent l'affichage de la forme graphique d'un automate.
def compile_ens_fini(comp,lst):
comp.compile()
res = comp.compile()
res.add_state()
res.set_start(0)
res.add_state()
res.set_final(1)
for st in lst:
if len(st) == 1:
res.add_arc(0,fst.Arc(alpha.find(st[0]),alpha.find(st[0]),0,1))
elif len(st) == 0:
res.set_final(0)
else:
n = res.add_state()
res.add_arc(0,fst.Arc(alpha.find(st[0]),alpha.find(st[0]),0,n))
for ch in st[1:-1]:
prev = n
n = res.add_state()
sym = alpha.find(ch)
res.add_arc(prev,fst.Arc(sym,sym,0,n))
res.add_arc(n,fst.Arc(alpha.find(st[-1]),alpha.find(st[-1]),0,1))
res = fst.determinize(res)
res.minimize()
return res
def my_concat(lst):
res = lst[0].copy()
for auto in lst[1:]:
res.concat(auto)
res.rmepsilon()
res = fst.determinize(res)
res.minimize()
return res
def my_union(lst):
res = lst[0].copy()
for auto in lst[1:]:
res.union(auto)
res.rmepsilon()
res = fst.determinize(res)
res.minimize()
return res
def display_auto(auto):
auto.draw('tmp_auto.dot', portrait=True, acceptor=True)
os.system('/usr/bin/dot -Tpng tmp_auto.dot > tmp_auto.png')
display(Image(filename='tmp_auto.png',width=500))