Sous-automates à nombre fini d'états : application à la compression de dictionnaires électroniques
Institution:
ToursDisciplines:
Directors:
Abstract EN:
This work deals with the study of internal structure of acyclic automaton. 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 factorize must increase memory storage efficiency and reduce the size of the initial automaton.
Abstract FR:
Dans ce travail, nous nous intéressons à l'étude de la structure interne des automates à nombre fini d'états, ainsi nous proposons un algorithme pour calculer l'ensemble des sous-automates associés à un automate donné. Cette étude ouvre les portes à diverses applications telles que la décomposition des automates, la recherche et la factorisation de sous-automates identiques 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 électroniques. Aussi, nous proposons un algorithme de compression de ces automates. Dans ce contexte, nous avons développé 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.