907 -- Algorithmique du texte : exemples et applications. : Différence entre versions
De AgregmathKL
m |
m |
||
| Ligne 10 : | Ligne 10 : | ||
Intro définition texte. | Intro définition texte. | ||
=== I - Recherche de Motifs [Beauquier]=== | === I - Recherche de Motifs [Beauquier]=== | ||
| − | # But et algorithme naïf | + | # But et algorithme naïf |
| + | #* Cadre de la recherche de motif | ||
| + | #* Algo 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) | ||
# Algorithme d'Horspool-Boyer-Moore | # Algorithme d'Horspool-Boyer-Moore | ||
| − | # Bilan | + | # Bilan et applications |
| + | #* Tableau comparatif des complexités | ||
| + | #* Applications | ||
| + | #** à l'analyse lexicale. | ||
| + | #** à la recherche dans un éditeur de texte. | ||
=== II - Comparaisons entre mots === | === II - Comparaisons entre mots === | ||
# Distances [Croch] | # Distances [Croch] | ||
#* préfixe, suffixe, sous-mot, édition, Hamming | #* préfixe, suffixe, sous-mot, édition, Hamming | ||
| + | # Alignements | ||
| + | #* Application génétique | ||
# Plus longue sous-suite commune (DEV) | # Plus longue sous-suite commune (DEV) | ||
| − | |||
=== III - Recherche approchée === | === III - Recherche approchée === | ||
| − | # Avec Joker | + | # Avec Joker [Crochemore] |
# Avec <math>k</math> différences (DEV) | # Avec <math>k</math> différences (DEV) | ||
# Application correction orthographique ? | # Application correction orthographique ? | ||
| Ligne 33 : | Ligne 40 : | ||
== Développements Possibles == | == Développements Possibles == | ||
| + | === Proposés === | ||
* [[Automate des occurrences]] [Beauquier, Crochemore] | * [[Automate des occurrences]] [Beauquier, Crochemore] | ||
* Plus longue sous-suite commune [Cormen] | * Plus longue sous-suite commune [Cormen] | ||
* Recherche avec <math>k</math>-différences [Cormen, Crochemore] | * Recherche avec <math>k</math>-différences [Cormen, Crochemore] | ||
| − | + | === Possibles === | |
| − | + | * Algorithmes de recherche de motifs : | |
| − | * Morris-Prat [Beauquier] | + | ** Morris-Prat [Beauquier] |
| − | * Knuth-Morris-Pratt [Beauquier, Knuth] | + | ** Knuth-Morris-Pratt [Beauquier, Knuth] |
| + | ** [[Automate des occurrences]] [Beauquier, Crochemore] | ||
| + | ** Algorithme de Rabin-Karp [Cormen] | ||
| + | * Algorithmes de programmation dynamique : | ||
| + | ** Recherche avec <math>k</math>-différences [Cormen, Crochemore] | ||
| + | ** Plus longue sous-suite commune [Cormen] | ||
| + | ** Calcul de la distance d'édition [Papadimitriou] | ||
* Tri des suffixes [Crochemore] | * Tri des suffixes [Crochemore] | ||
| − | |||
| − | |||
* Méthode de compression Ziv-Lempel77 [Incerti] | * Méthode de compression Ziv-Lempel77 [Incerti] | ||
* ... éventuellement de la compilation (analyse lexicale et syntaxique) | * ... éventuellement de la compilation (analyse lexicale et syntaxique) | ||
Version du 11 décembre 2011 à 17:48
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
- Cadre de la recherche de motif
- Algo naïf
- Algorithmes de Morris-Pratt
- Amélioration Knuth-Morris-Pratt
- Automate des occurences (DEV)
- Algorithme d'Horspool-Boyer-Moore
- Bilan et applications
- Tableau comparatif des complexités
- Applications
- à l'analyse lexicale.
- à la recherche dans un éditeur de texte.
II - Comparaisons entre mots
- Distances [Croch]
- préfixe, suffixe, sous-mot, édition, Hamming
- Alignements
- Application génétique
- Plus longue sous-suite commune (DEV)
III - Recherche approchée
- Avec Joker [Crochemore]
- Avec
différences (DEV) - Application correction orthographique ?
IV - Compression
- Codage de Huffman [Incerti]
- Application à la compression d'images
Développements Possibles
Proposés
- Automate des occurrences [Beauquier, Crochemore]
- Plus longue sous-suite commune [Cormen]
- Recherche avec -différences [Cormen, Crochemore]
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 :
- Recherche avec -différences [Cormen, Crochemore]
- Plus longue sous-suite commune [Cormen]
- Calcul de la distance d'édition [Papadimitriou]
- Recherche avec
- 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
