907 -- Algorithmique du texte : exemples et applications.

Plans scanés

• 2012-2013 Plan démo de rentrée de l'année 2012-2013, Plan scanné de l'année 2012-2013
• 2013-2014 Plan scanné de l'année 2013-2014
• 2014-2015 Plan scanné de l'année 2014-2015
• 2015-2016 Plan scanné de l'année 2015-2016
• 2018-2019 Plan scanné de l'année 2018-2019

Autre plan : Basile et Kévin (2012)

Intro définition texte.

I - Recherche de Motifs [Beauquier]

1. But et algorithme naïf
   • Cadre de la recherche de motif
   • Algo naïf
2. Algorithmes de Morris-Pratt
   • Amélioration Knuth-Morris-Pratt
   • Automate des occurences (DEV)
3. Algorithme d'Horspool-Boyer-Moore
4. Bilan et applications
   • Tableau comparatif des complexités [Cormen + Beauquier]
   • Applications
     • à l'analyse lexicale.
     • à la recherche dans un éditeur de texte.

II - Comparaisons entre mots

1. Distances [Croch]
   • préfixe, suffixe, sous-mot, édition, Hamming
2. Alignements
   • Application génétique
3. Plus longue sous-suite commune (DEV)

III - Recherche approchée

1. Avec Joker [Crochemore]
2. Avec $k$ différences (DEV)
3. Application correction orthographique ?

IV - Compression

1. Codage de Huffman [Incerti]
   • Application à la compression d'images

Développements

• Plus longue sous-séquence commune
• Automate des occurrences
• Arbres binaires de recherche optimaux
• Analyse LR(0)

Autres développements

• Automate des occurrences [Beauquier, Crochemore]
• Plus longue sous-séquence commune [Cormen]
• Recherche avec $k$-différences [Cormen, Crochemore]
• Algorithmes de recherche de motifs :
  • Morris-Prat [Beauquier]
  • Knuth-Morris-Pratt [Beauquier, Knuth]
  • Automate des occurrences [Beauquier, Crochemore]
  • Algorithme de Rabin-Karp [Cormen]
• Algorithmes de programmation dynamique :
  • Recherche avec $k$-différences [Cormen, Crochemore]
  • Plus longue sous-séquence commune [Cormen]
  • Calcul de la distance d'édition [Papadimitriou]
• Tri des suffixes [Crochemore]
• Méthode de compression Ziv-Lempel77 [Incerti]
• ... éventuellement de la compilation (analyse lexicale et syntaxique)

Commentaires

Par "texte", on entend "information" : programme, document, ADN...

• Comparaison de deux séquences (comparaison d'un mot avec une entrée d'un dictionnaire puis correction etc., comparaison d'ADN)
• Recherche d'une chaîne dans une autre (dans un logiciel de traitement de texte, un moteur de recherche sur l'Internet
• Stockage de texte : compression via les arbres de Huffman

Extrait du site [1] concernant cette leçon.

Références

• Crochemore et al.
• Beaquier Berstel Chrétienne
• Cormen et al.
• Papadimitriou
• E. Incerti : Compression d'images