MP2I — 2022-2023 Perre Le Scornet Modue Agorthmque
TP 22 : Agorthme de Human —
compéments
Ce TP vent en compément du TP 22 sur ’agorthme de Human. Notamment, on va essayer de are de
ce TP queque chose d’utsabe dans a vrae ve (oué oué).
On reprend es mêmes types et notatons qu’au TP 22, notamment :
type arbre_code = OCam
| F of char
| N of arbre_code * arbre_code
Exercice 1 – Lecture de fchier non compressé octet par octet
En OCam, est possbe de re et d’écrre un ficher non pas en tant que ficher texte, mas en e
manpuant drectement octet par octet. Or, quand on utse a oncton open_in : string ->
in_channel pour ouvrr un ficher, e ficher est ouvert dans un mode partcuer appeé mode
texte : dans ce mode, certans octets du ficher seront fitrés ou tratés de manère partcuère.
Ans, quand on utse input_line : in_channel -> string pour re une gne du ficher, on
saute es octets correspondants à un retour à a gne (qu dépendent égaement de ’édteur qu a
été utsé pour créer e ficher !). Pour réger ce probème, on utsera a oncton :
val open_in_bin : string -> in_channel OCam
qu est dsponbe dans a bbothèque standard Stdlib. On utsera aors a oncton input_byte
: in_channel -> int qu t un caractère du ficher en entrée, t un octet et e renvoe sous a
orme d’un enter entre 0 et 255. Lorsque ’on est arrvé à a fin du ficher en entrée, un appe à
input_byte èvera ’excepton End_of_file.
▶ Question 1 Écrre une oncton tableau_occurences : string -> int array qu prend
en entrée e nom d’un ficher (ou e chemn vers un ficher) et renvoe e tabeau du nombre
d’occurences de chaque caractère, stocké dans un tabeau de tae 256. On n’oubera pas de ermer
es fichers ouverts à ’ade de close_in : in_channel -> unit.
Voà ! On peut mantenant “charger” un ficher et cacuer son arbre de Human en réutsant
es autres onctons écrtes pendant e TP22.
Exercice 2 – Sérialisation de l’arbre de Human
S ’on veut utser ’agorthme de Human dans a vrae ve, on dot séraser ’arbre de Human
assocé, c’est-à-dre e représenter sous a orme d’une chaîne de caractères pour a stocker dans
e ficher compressé. On va utser a oncton suvante :
(N (g, d)) = 0 ⋅ (g) ⋅ (d)
(F c) = 1 ⋅ c
avec 0 ’octet nu (autrement dt, 00000000) et 1 ’octet représentant 1 en non sgné (autrement
dt, 00000001).
▶ Question 1 Séraser à a man ’arbre suvant :
N (N (F 12, N (F 7, F 8)), F 40) OCam
▶ Question 2 Déséraser a sute d’octets suvante :
0 0 1 17 1 18 0 1 1 0 1 30 1 20
1
MP2I — 2022-2023 Perre Le Scornet Modue Agorthmque
▶ Question 3 Détermner e nombre d’octets occupé par a sérasaton d’un arbre représentant
’encodage de a totaté des 256 caractères.
On peut mantenant re et écrre des arbres de Human dans des fichers. Pour a ecture, on
utsera toujours des fichers représentés par des in_channel. Pour écrre dans un ficher, on ut-
sera a oncton output_byte : out_channel -> int -> unit te que output_byte c k écrt
’octet k ∈ J0, 255K dans e ficher représenté par c, et a oncton open_out_bin : string ->
out_channel qu permet d’ouvrr un ficher en écrture (toujours dans un mode permettant
d’écrre n’mporte que octet, contrarement à open_out).
Remarque 1
Quand on exécute open_out sur un nom de ficher, est créé s’ n’exste pas et écrase e
contenu du ficher précédent s’ exste déjà.
▶ Question 4 Écrre es onctons suvantes, réasant a sérasaton et dé-sérasaton d’un
arbre de Human :
val output_arbre : out_channel -> arbre_code -> unit OCam
val input_arbre : in_channel -> arbre_code
Un ficher compressé contendra donc d’abord a sérasaton de ’arbre de Human utsé pus
e texte encodé.
Exercice 3 – Écriture du fchier compressé bit par bit
L’agorthme de Human utse un codage bnare de ongueur varabe : cea mpque notam-
ment que ’on va devor écrre bt par bt dans e ficher, aors qu’on ne dspose que d’une oncton
permettant d’écrre un octet. Pour évter cet écue, on va devor are des chox : s e texte encodé
content bts, on va ’écrre en ⌈ ⌉ octets et éventueement rempr es 0 à 7 bts restants du
8
derner octet par des bts nus. Par exempe, pour e codage suvant :
'a' 'b' 'c'
0 100 101
L’encodage du mot "abbaca" est aors 010010001010 qu sera encodée en es octets
0100100010100000, c’est-à-dre 72 et 160.
Pour passer d’un lux de bts à un ficher ben écrt octet par octet, on va utser un objet nter-
médare sur eque on va enfier es bts au ur et à mesure de ’encodage, et qu va écrre un octet
dès que 8 bts y ont été ajouté. On va utser e type suvant :
type out_channel_bits = { OCam
o_fichier : out_channel;
mutable o_accumulateur : int;
mutable o_bits_accumules : int
}
Le premer champ correspond au ficher où écrre. Le second content ’octet actueement
construt sous a orme d’un enter. Le derner champ correspond au nombre de bts attendant
d’être écrts. On aura donc :
o_accumulateur ∈ J0, 2o_bits_accumules − 1K
2
MP2I — 2022-2023 Perre Le Scornet Modue Agorthmque
▶ Question 1 Écrre une oncton open_out_bits : string -> out_channel_bits qu prend
en entrée un nom / chemn de ficher et ntase un enregstrement de type out_channel_bits
pour écrre dans ce ficher.
▶ Question 2 Écrre une oncton output_bit : out_channel_bits -> bool -> unit qu
prend en entrée un ficher de type out_channel_bits et un bt de type bool, et trate ’écrture de
ce bt en mettant à jour ’accumuateur et e nombre de bts accumués, et en écrvant eectve-
ment ’octet accumué s e nombre de bts accumués attent 8.
Le souc de cette représentaton est que es bts nus de rempssage du derner octet peuvent
rendre e code ambgu (c’est e cas de ’exempe précédent : est-ce que es 0 finaux sont des 'a' ou
juste des 0 ajoutés) ? Pour réger ce probème, on ajoute un octet suppémentare au ficher qu
content e nombre de bts nus ajoutés pour compéter e derner octet du texte encodé.
Par exempe, en reprenant ’octet précédent, au eu d’écrre 0100100010100000 pour encoder a
chaîne de caractères "abbaca", on écrra putôt es octets 010010001010000000000100, e derner
octet ndquant que ’avant-derner octet content 4 bts nus de rempssage.
▶ Question 3 Écrre une oncton close_out_bits : out_channel_bits -> unit qu écrt
éventueement es derners bts accumués en n’oubant pas es bts nus, écrt ’octet fina nd-
quant e nombre de bts nus ajoutés et erme e ficher. On pourra utser a oncton close_out
: out_channel -> unit qu est équvaente à close_in pour es lux de sorte.
Exercice 4 – Lecture du fchier compressé bit par bit
Pour re un ficher compressé, on a déjà codé a moté des onctons nécessares : a oncton
input_arbre : in_channel -> arbre_code permet de re octet par octet notre ficher pour en
dédure son arbre de Human. On a quand même beson d’un type smare à out_channel_bits
permettant de re un ficher bt par bt :
type in_channel_bits = { OCam
i_fichier : in_channel;
mutable i_accumulateur : int;
mutable i_bits_accumules : int;
i_taille : int
}
— i_fichier est e lux d’entrée créé à partr d’un ficher,
— i_accumulateur content ’octet en tran d’être u (à chaque octet u dans e ficher, est
ntasé à cet octet, pus décroît jusqu’à attendre 0 au ur et à mesure que ’on t des
bts),
— i_bits_accumules content e nombre de bts restant à re dans i_accumulateur,
— i_taille content a tae du ficher, en nombre d’octets.
Les onctons suvantes permettent d’ouvrr et ermer un ficher en utsant ce type :
3
MP2I — 2022-2023 Perre Le Scornet Modue Agorthmque
let open_in_bits fn = OCam
let fichier = open_in_bin fn in
{
i_fichier = fichier;
i_accumulateur = 0;
i_bits_accumules = 0;
i_taille = in_channel_length fichier
(* voilà à quoi sert [in_channel_length], que les utilisateurs de
↪ VSCode / Codium doivent avoir déjà vu... *)
}
let close_in_bits f = close_in f.i_fichier
▶ Question 1 Écrre a oncton input_bit : in_channel_bits -> bool qu permet de re
un bt du lux en entrée. On aura beson de a oncton pos_in : in_channel -> int qu renvoe
a poston actuee du lux d’entrée dans e ficher, ce qu permet de gérer e cas du derner octet du
ficher.
Exercice 5 – Compression et décompression d’un octet
On peut mantenant écrre es onctons de compresson et décompresson que ’on a déjà écrt sur
es chaînes de caractères dans e TP 22, mas cette os-c en manpuant drectement es fichers
octet par octet.
▶ Question 1 Écrre a oncton de type :
compresse_byte : out_channel_bits -> tableau_code -> int -> unit OCam
qu prend en entrée e lux de sorte sur eque écrre, un tabeau de codes (comme ceu cacué
par a oncton creer_tableau du TP 22), un octet représenté par enter entre 0 et 255 et écrt a
sére de bts correspondante à cet octet dans e lux de sorte.
▶ Question 2 Écrre une oncton de type :
decompresse_byte : in_channel_bits -> arbre_code -> int OCam
qu décode un octet du texte encodé dsponbe dans e lux d’entrée ourn grâce à ’arbre de
Human égaement ourn en entrée, et e renvoe.
Exercice 6 – On met tout ensemble
Manque pus que deux onctons, ’une pour compresser un ficher et ’autre pour e décompres-
ser !
▶ Question 1 Écrre une oncton compresse_fichier : string -> string -> unit qu
prend en entrée un nom / chemn de ficher d’entrée, un nom / chemn de ficher de sorte et
compresse e premer en nscrvant e résutat dans e second.
▶ Question 2 Écrre de même une oncton decompresse_fichier : string -> string ->
unit qu eectue a décompresson.
Le code suvant, pacé à a fin de votre ficher, devrat vous permettre de comper un exécutabe
compressant ou décompressant un ficher ourn en argument :
4
MP2I — 2022-2023 Perre Le Scornet Modue Agorthmque
let main () = OCam
let error_and_exit () =
let invocation = [Link].(0) in
[Link] "Usage : \n";
[Link] "%s compress <input-file> <compressed-output-file>\n"
↪ invocation;
[Link] "%s decompress <compressed-file> <output-file>\n"
↪ invocation;
exit 1 in
if [Link] [Link] < 4 then error_and_exit ();
let commande = [Link].(1) in
let nom_in = [Link].(2) in
let nom_out = [Link].(3) in
if commande = "compress" then compresse_fichier nom_in nom_out
else if commande = "decompress" then decompresse_fichier nom_in nom_out
else error_and_exit ()
let () = main ()