These: Lamia Tounsi, Sous-automates et dictionnaires

[Thierry Hamon]

Date: Thu, 06 Dec 2007 18:00:30 +0100
From: Denis Maurel <denis.maurel at univ-tours.fr>
Message-Id: <20071206171430.634C21C0009D at mwinf2114.orange.fr>


Bonjour,
J'ai le plaisir de vous inviter a la soutenance de ma these de
doctorat intitulee : "Sous-automates a nombre fini
d'etats. Application a la compression de dictionnaires
electroniques". La soutenance se deroulera le Mercredi 12 Decembre
2007 a 14h au Laboratoire d'Informatique de Polytech'Tours en salle
Lovelace.


La soutenance sera suivie d'un pot auquel vous etes invites.

Resume :

Les automates acycliques a nombre finis d'etats se sont tres largement
repandus en traitement automatique des langues pour la representation
et le stockage de gros volumes de donnees, comme des dictionnaires
electroniques.
Dans ce travail, nous nous interessons a l'etude de la structure
interne de tels automates; plus precisement, nous souhaitons detecter
des structures presentes a l'interieur d'un automate a nombre fini
d'etats, que nous appelons sous-automates. Ainsi, nous proposons un
algorithme en pour calculer l'ensemble des sous-automates associes a
un automate donne. Cette etude ouvre les portes a des applications
diverses telles que la decomposition des automates, la recherche de
sous-automates identiques, la factorisation des sous-automates
redondants et peut aussi contribuer a une compression de ces donnees.

La seconde partie du travail est consacree a l'application de notre
algorithme pour la compression et l'indexation des automates
representant des dictionnaires. Aussi, nous proposons un algorithme de
compression qui permet de reduire l'espace memoire necessaire au
stockage des automates et de conserver un acces efficace aux donnees.
Dans ce contexte, nous avons ete amene a developper diverses
applications utilisant, d'une part, l'automate des suffixes
initialement dedie pour l'indexation de texte, pour indexer les
sous-automates, et, d'autre part, des heuristiques permettant de
selectionner les sous-structures les plus interessantes a factoriser;
celles qui maximisent le gain de memoire et reduisent la taille de
l'automate initial.

Mots cles : Automate, Sous-automate, Indexation, DAWG, Compression,
Factorisation, Dictionnaire, Graphe, Algorithme Glouton.



Abstract :

Acyclic finite state automata are widely used in Natural Language
Processing in order to represent and store huge data such as
dictionaries. This work deals with the study of internal structure of
acyclic automaton; more precisely, we are interested in finding
structures inside a finite state automaton, which we call
sub-automata.  Thus, we propose an algorithm to compute all
subautomata of a given automaton. This study can be used in
applications whose aim is to decompose a very large FSA into smaller
ones, to discover frequently occurring data and to reduce memory
consumption.

The second part of our work is devoted to the application of our
algorithm for compression and indexing of automata that represent
electronic dictionaries. Also, we propose a compression algorithm to
reduce the memory required to store the automata and to preserve an
effective access to data. The main propositions are, on the one hand,
the application of the direct acyclic word graph, initially dedicated
for indexing text, to index the subautomata, and, on the other hand,
heuristic to select the most interesting substructure to
factorize. The best candidates to be factorized are those which
increase memory storage efficiency and reduce the size of the initial
automaton.

Key words : Automaton, Subautomaton, Indexing, DAWG, Compression,
Factorization, Dictionary, Graph, Greedy Algorithm.

Membre du Jury :
Beatrice BOUCHOU, Maitre de Conference, Universite de Tours.
Jean Marc CHAMPARNAUD , Professeur, Universite de Rouen.
Eric LAPORTE, Professeur, Universite Marne-la-Vallee.
Bernard LEVRAT, Professeur, Universite d'Angers.
Denis MAUREL, Professeur, Universite de Tours.



Cordialement,


Lamia Tounsi

Universite François Rabelais Tours
Laboratoire d'Informatique, Polytech'Tours,
64, Av Jean Portalis, 37200 Tours, France.
E-mail:  lamia.tounsi at univ-tours.fr
Phone:  +33. 2.47.36.14.35
Fax:      +33. 2.47.36.14.22


-------------------------------------------------------------------------
Message diffuse par la liste Langage Naturel <LN at cines.fr>
Informations, abonnement : http://www.atala.org/article.php3?id_article=48
English version       : 
Archives                 : http://listserv.linguistlist.org/archives/ln.html
                                http://liste.cines.fr/info/ln

La liste LN est parrainee par l'ATALA (Association pour le Traitement
Automatique des Langues)
Information et adhesion  : http://www.atala.org/
-------------------------------------------------------------------------