907 -- Algorithmique du texte : exemples et applications.

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.

Plan Basile et Kévin (2012)

Le plan

Intro définition texte.

I - Recherche de Motifs

1. But et algorithme naïf
2. Algorithmes de Morris-Pratt
   • Amélioration Knuth-Morris-Pratt
   • Automate des occurences (DEV)
3. Algorithme d'Horspool-Boyer-Moore
4. Bilan

II - Comparaisons entre mots

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

III - Recherche approchée

1. Avec Joker
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

• Automate des occurrences (Beauquier, Crochemore)
• Plus longue sous-suite commune (Cormen)
• Recherche avec $k$-différences (Cormen, Crochemore)

---

• Morris-Prat (Beauquier)
• Knuth-Morris-Pratt (Beauquier, Knuth)
• Tri des suffixes (Crochemore)
• Algorithme de Rabin-Karp
• Calcul de la distance d'édition par programmation dynamique (Papadimitriou)
• 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.