907 -- Algorithmique du texte : exemples et applications.

De AgregmathKL
Aller à : navigation, rechercher

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.

Plans scanés


Développements


Plan Basile et Kévin (2012)

Le plan

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 Possibles

Proposés

Possibles

  • 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 :
  • Tri des suffixes [Crochemore]
  • Méthode de compression Ziv-Lempel77 [Incerti]
  • ... éventuellement de la compilation (analyse lexicale et syntaxique)

Références

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