907 -- Algorithmique du texte : exemples et applications. : Différence entre versions
De AgregmathKL
m |
m |
||
| Ligne 9 : | Ligne 9 : | ||
== Le plan == | == Le plan == | ||
Intro définition texte. | Intro définition texte. | ||
| − | === I - Recherche de Motifs === | + | === I - Recherche de Motifs [Beauquier]=== |
| − | # But et algorithme naïf | + | # But et algorithme naïf |
| − | # Algorithmes de Morris-Pratt | + | # Algorithmes de Morris-Pratt |
#* Amélioration Knuth-Morris-Pratt | #* Amélioration Knuth-Morris-Pratt | ||
#* Automate des occurences (DEV) | #* Automate des occurences (DEV) | ||
| Ligne 18 : | Ligne 18 : | ||
=== II - Comparaisons entre mots === | === II - Comparaisons entre mots === | ||
| − | # Distances | + | # Distances [Croch] |
#* préfixe, suffixe, sous-mot, édition, Hamming | #* préfixe, suffixe, sous-mot, édition, Hamming | ||
# Plus longue sous-suite commune (DEV) | # Plus longue sous-suite commune (DEV) | ||
| Ligne 33 : | Ligne 33 : | ||
== Développements Possibles == | == Développements Possibles == | ||
| − | * Automate des occurrences | + | * [[Automate des occurrences]] [Beauquier, Crochemore] |
| − | * Plus longue sous-suite commune | + | * Plus longue sous-suite commune [Cormen] |
| − | * Recherche avec <math>k</math>-différences | + | * Recherche avec <math>k</math>-différences [Cormen, Crochemore] |
---- | ---- | ||
| − | * Morris-Prat | + | * Morris-Prat [Beauquier] |
| − | * Knuth-Morris-Pratt | + | * Knuth-Morris-Pratt [Beauquier, Knuth] |
| − | * Tri des suffixes | + | * Tri des suffixes [Crochemore] |
* Algorithme de Rabin-Karp | * Algorithme de Rabin-Karp | ||
| − | * Calcul de la distance d'édition par programmation dynamique | + | * Calcul de la distance d'édition par programmation dynamique [Papadimitriou] |
| − | * Méthode de compression Ziv-Lempel77 | + | * Méthode de compression Ziv-Lempel77 [Incerti] |
* ... éventuellement de la compilation (analyse lexicale et syntaxique) | * ... éventuellement de la compilation (analyse lexicale et syntaxique) | ||
| Ligne 51 : | Ligne 51 : | ||
* Beaquier Berstel Chrétienne | * Beaquier Berstel Chrétienne | ||
* Cormen et al. | * Cormen et al. | ||
| + | |||
| + | * Papadimitriou | ||
| + | * E. Incerti : Compression d'images | ||
Version du 11 décembre 2011 à 01:14
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.
Sommaire
Plan Basile et Kévin (2012)
Le plan
Intro définition texte.
I - Recherche de Motifs [Beauquier]
- But et algorithme naïf
- Algorithmes de Morris-Pratt
- Amélioration Knuth-Morris-Pratt
- Automate des occurences (DEV)
- Algorithme d'Horspool-Boyer-Moore
- Bilan
II - Comparaisons entre mots
- Distances [Croch]
- préfixe, suffixe, sous-mot, édition, Hamming
- Plus longue sous-suite commune (DEV)
- Application génétique
III - Recherche approchée
- Avec Joker
- Avec
différences (DEV) - Application correction orthographique ?
IV - Compression
- 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 -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.
- Papadimitriou
- E. Incerti : Compression d'images
