Thèse de Lamia TOUNSI

Référence

Tounsi Lamia (2007). Sous-automates à nombre fini d'états. Application à la compression de dictionnaires électroniques. Thèse de doctorat d'informatique, Université François Rabelais Tours.

Jury : B. Bouchou, J.-M. Champarnaud, É. Laporte, B. Levrat, D. Maurel.

Cette thèse a été financée par le Conseil régional de la Région Centre.

Télécharger la thèse / To download the thesis

Résumé

Les automates acycliques à nombre finis d'états se sont très largement répandus en traitement automatique des langues pour la représentation et le stockage de gros volumes de données, comme des dictionnaires électroniques.

Dans ce travail, nous nous intéressons à l'étude de la structure interne de tels automates; plus précisément, nous souhaitons détecter des structures présentes à l'intérieur d'un automate à nombre fini d'états, que nous appelons sous-automates. Ainsi, nous proposons un algorithme pour calculer l'ensemble des sous-automates associés à un automate donné.

Cette étude ouvre les portes à des applications diverses telles que la décomposition des automates, la recherche de sous-automates identiques, la factorisation des sous-automates redondants et peut aussi contribuer à une compression de ces données.

La seconde partie du travail est consacrée à l'application de notre algorithme pour la compression et l'indexation des automates représentant des dictionnaires. Aussi, nous proposons un algorithme de compression qui permet de réduire l'espace mémoire nécessaire au stockage des automates et de conserver un accès efficace aux données. Dans ce contexte, nous avons été amené à développer diverses applications utilisant, d'une part, l'automate des suffixes initialement dédié pour l'indexation de texte, pour indexer les sous-automates, et, d'autre part, des heuristiques permettant de sélectionner les sous-structures les plus intéressantes à factoriser; celles qui maximisent le gain de mémoire et réduisent la taille de l'automate initial.

Mots-clés

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.

Keywords

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