La thèse de Dominique Revuz
- 1 Introduction
- 1.1 NOTATIONS, DéFINITIONS
- 1.2 LES DICTIONNAIRES DU LADL
- 1.2.1 DELAS
- 1.2.2 DELAF
- 1.2.3 DELAC et DELACF
- 1.2.4 DELAP et DELAPF
- 1.2.5 Le Lexique-grammaire.
- 1.2.6 Autres dictionnaires.
- 2 Les approches classiques.
- 2.1 LISTES, LISTES SéQUENTIELLES
- Intérêt pratique
- Désavantages
- 2.2 ARBRES.
- 2.2.1 Arbres binaires de recherche.
- Intérêts.
- Désavantage.
- 2.2.2 Les arbres AVL.
- 2.2.3 Arbres 2-3.
- Intérêt.
- Désavantage.
- 2.2.4 Arbres lexicographiques généralisés (ALG).
- Intérêt.
- Désavantage.
- 2.2.5 Conclusion sur les arbres.
- 2.3 HACHAGE
- Intérêt.
- Désavantages.
- 2.4 MéTHODES AVEC BRUIT
- 2.4.1 Le codage surimposé
- Intérêt.
- Désavantages
- 2.5 MéTHODES AVEC SILENCE
- 2.6 CONCLUSION.
- 3 Les automates
- 3.1 NOTATION, DéFINITIONS.
- Reconnaissance d'un mot et langage reconnu :
- 3.2 LA MINIMISATION DES AUTOMATES.
- 3.3 LA REPRéSENTATION PAR AUTOMATES
- 3.3.1 Mise en oeuvre des automates
- Représentation par listes des transitions d'un état.
- Les représentations par tableaux.
- Des compromis espace / vitesse.
- Etats suppléants.
- Un unique tableau de Transitions.
- 3.3.2 Algorithme de construction.
- 3.3.3 Algorithme de pseudo-minimisation.
- 3.3.4 Algorithme de minimisation.
- 3.3.5 Algorithmes de suppression et d'insertion.
- La fonction Insérer.
- La fonction Supprimer.
- Minimisation.
- 3.4 LA REPRéSENTATION DE LEXIQUES PAR AUTOMATES ACYCLIQUES.
- 3.5 REPRéSENTATION DES MOTS COMPOSéS.
- 3.6 UNE REPRéSENTATION POUR LE DELAF (AVEC CODES).
- 3.6.1 Automate à Multi terminaux.
- 3.6.2 Automate à Multi initiaux.
- 3.7 REPRéSENTATION COUPLéE AUTOMATES/ALG. UN NOUVEAU HACHAGE.
- 4 Les transducteurs.
- 4.1 GéNéRALITéS.
- 4.2 NON EXISTENCE DE TRANSDUCTEURS MINIMAUX.
- 4.3 UTILISATION COUPLEE D'UN AUTOMATE ET D'UN TRANSDUCTEUR.
- 4.4 AUTOMATES, TRANSDUCTEURS, ALG, ET HACHAGE.
- 4.4.1 Transducteur de hachage
- 4.4.2 Mise en oeuvre du transducteur de hachage
- 4.5 UN OUTIL COMPLET POUR LES DICTIONNAIRES COMPLEXES.
- 5 Transducteurs de compression.
- 5.2.1 DéFINITIONS
- 5.1 CODAGE, DéCODAGE.
- 5.2 COMPRESSEUR à CODAGE NAïF DES TRANSITIONS.
- 5.3 COMPRESSEUR AVEC UN CODE DE HUFFMAN.
- 5.4 COMPRESSEUR à DELAI 1 UTILISANT LA FRéQUENCE DES MOTS.
- 5.4.1 Construction du dictionnaire des fréquences.
- 5.5 CODAGE ADAPTATIF.
- 5.6 COMPRESSEUR à DéLAI DE DéCODAGE SUPéRIEUR à 1.
- 5.7 CONCLUSIONS SUR LA COMPRESSION.
- 6 Algorithmes.
- 6.1 ALGORITHME DE MINIMISATION DES AUTOMATES ACYCLIQUES.
- 6.1.1 Le tri lexicographique.
- 6.1.2 Algorithme pour séparer une séquence de mots.
- 6.1.3 L'algorithme final.
- 7 Conclusions.
- 8 Bibliographie.
- 9 Annexes