informatique (MP2I/MPI) · Chapitre 18 · Application directe du cours
Problème — lzw complet, et son test
Algorithmique des textes · niveau 3 (difficile)
Énoncé
- Écrire le compresseur lzw.
- Écrire le décompresseur, cas particulier compris.
- Prouver que le décodeur ne reçoit jamais un code arbitrairement inconnu : quand il en reçoit un, c'est toujours le suivant de son dictionnaire.
- Écrire le test qui aurait attrapé un décompresseur sans le cas particulier.
Corrigé de la question 1
1. Le compresseur.
(* Compresse s. Les codes 1..|alphabet| sont les caracteres seuls.
Precondition : tout caractere de s figure dans alphabet.
Complexite : Theta(|s|) appels a la table de hachage. *)
let compresser alphabet s =
let dico = Hashtbl.create 512 in
String.iteri (fun i c -> Hashtbl.replace dico (String.make 1 c) (i + 1)) alphabet;
let suivant = ref (String.length alphabet + 1) in
let sortie = ref [] and w = ref "" in
(* INVARIANT : w est le plus long prefixe du reste deja present au dictionnaire. *)
String.iter (fun c ->
let wc = !w ^ String.make 1 c in
if Hashtbl.mem dico wc then w := wc (* on peut allonger *)
else begin
sortie := Hashtbl.find dico !w :: !sortie; (* on emet le PLUS LONG connu *)
Hashtbl.add dico wc !suivant; incr suivant;(* et on apprend wc *)
w := String.make 1 c
end) s;
if !w <> "" then sortie := Hashtbl.find dico !w :: !sortie;
List.rev !sortieQuestion 2 : comment l'IA t'aide
2. Écrire le décompresseur, cas particulier compris.
Élève
Mon décompresseur traduit chaque code par le dictionnaire, puis apprend la séquence précédente suivie d'une lettre. Mais sur un texte comme , il reçoit un code qui n'est pas encore dans son dictionnaire.
IA
C'est le cas particulier. Le décodeur apprend avec un tour de retard sur le codeur : quand le codeur émet un code qu'il vient tout juste de créer, que sait-on de la chaîne correspondante, par rapport à la séquence émise juste avant ?
Élève
Le codeur a créé cette entrée au tour précédent : c'est la séquence précédente suivie d'une lettre. Mais je ne connais pas cette lettre, puisque c'est justement ce code que je n'arrive pas à décoder.
IA
Cette lettre est, par construction, la première de la séquence que tu cherches. Or cette séquence commence elle-même par la séquence précédente : quelle est donc sa première lettre ?
L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.
Continue cet exercice avec l'IA
Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.
Continuer avec l'IA — gratuit, sans inscriptionGratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.