La thèse de Dominique Revuz


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