907 -- Algorithmique du texte : exemples et applications. : Différence entre versions
De AgregmathKL
m (pré-création pareil pour me motiver) |
|||
Ligne 8 : | Ligne 8 : | ||
= Plan Basile et Kévin (2012) = | = Plan Basile et Kévin (2012) = | ||
== Le plan == | == Le plan == | ||
+ | Intro définition texte. | ||
+ | === I - Recherche de Motifs === | ||
+ | # But et algorithme naïf | ||
+ | # Algorithmes de Morris-Pratt et Knuth-Morris-Pratt | ||
+ | #* Automate des occurences (DEV) | ||
+ | # Algorithme d'Horspool-Boyer-Moore | ||
+ | # Bilan | ||
+ | |||
+ | === II - Comparaisons entre mots === | ||
+ | # Distances | ||
+ | #* préfixe, suffixe, sous-mot, édition, Hamming | ||
+ | # Plus longue sous-suite commune (DEV) | ||
+ | #* Application génétique | ||
+ | |||
+ | === III - Recherche approchée === | ||
+ | # Avec Joker | ||
+ | # Avec <math>k</math> différences (DEV) | ||
+ | # Application correction orthographique ? | ||
+ | |||
+ | === IV - Compression === | ||
+ | # Codage de Huffman [Incerti] | ||
+ | #* Application à la compression d'images | ||
== Développements Possibles == | == Développements Possibles == | ||
Ligne 13 : | Ligne 35 : | ||
* Knuth-Morris-Pratt | * Knuth-Morris-Pratt | ||
** Algorithme en lui-même | ** Algorithme en lui-même | ||
− | ** Automate des | + | ** Automate des occurences |
* Plus longue sous-suite commune (Cormen) | * Plus longue sous-suite commune (Cormen) | ||
* Tri des suffixes (Crochemore) | * Tri des suffixes (Crochemore) |
Version du 10 décembre 2011 à 15:41
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
- But et algorithme naïf
- Algorithmes de Morris-Pratt et Knuth-Morris-Pratt
- Automate des occurences (DEV)
- Algorithme d'Horspool-Boyer-Moore
- Bilan
II - Comparaisons entre mots
- Distances
- 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
- Morris-Prat (Beauquier)
- Knuth-Morris-Pratt
- Algorithme en lui-même
- Automate des occurences
- Plus longue sous-suite commune (Cormen)
- Tri des suffixes (Crochemore)
- Algorithme de Rabin-Karp
- Calcul de la distance d'édition
- Recherche avec différences
- Méthode de compression Ziv-Lempel77
- ... éventuellement de la compilation (analyse lexicale et syntaxique)
Références
- Crochemore et al.
- Beaquier Berstel Chrétienne