1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
(***********************************************************************)
(* *)
(* Objective Caml *)
(* *)
(* Pierre Weis, projet Cristal, INRIA Rocquencourt *)
(* *)
(* Copyright 2001 Institut National de Recherche en Informatique et *)
(* en Automatique. All rights reserved. This file is distributed *)
(* only by permission. *)
(* *)
(***********************************************************************)
type table_de_codage =
{ caractre : int list array;
mutable fin : int list };;
let encode entre sortie codage =
Esbit.initialise();
try
while true do
let c = input_char entre in
List.iter (Esbit.crire_bit sortie)
codage.caractre.(int_of_char c)
done
with End_of_file -> (* fin du fichier d'entre *)
List.iter (Esbit.crire_bit sortie) codage.fin;
Esbit.finir sortie;;
type arbre_de_huffman =
| Lettre of char
| Fin
| Noeud of arbre_de_huffman * arbre_de_huffman;;
let dcode entre sortie arbre =
Esbit.initialise();
let rec parcours = function
| Fin -> ()
| Lettre c ->
output_char sortie c; parcours arbre
| Noeud(gauche, droite) ->
if Esbit.lire_bit entre = 0
then parcours gauche
else parcours droite in
parcours arbre;;
let frquences entre =
let fr = Array.make 256 0 in
begin try
while true do
let c = int_of_char(input_char entre) in fr.(c) <- fr.(c) + 1
done
with End_of_file -> ()
end;
fr;;
let construire_arbre frquences =
let prio = ref (Fileprio.ajoute Fileprio.vide 1 Fin) in
let nombre_d'arbres = ref 1 in
for c = 0 to 255 do
if frquences.(c) > 0 then begin
prio := Fileprio.ajoute !prio
frquences.(c) (Lettre(char_of_int c));
incr nombre_d'arbres
end
done;
for n = !nombre_d'arbres downto 2 do
let (frq1, arbre1, prio1) = Fileprio.extraire !prio in
let (frq2, arbre2, prio2) = Fileprio.extraire prio1 in
prio := Fileprio.ajoute prio2
(frq1 + frq2) (Noeud(arbre1,arbre2))
done;
let (_, arbre, _) = Fileprio.extraire !prio in
arbre;;
let arbre_vers_codage arbre =
let codage = { caractre = Array.make 256 []; fin = [] } in
let rec remplir_codage prfixe = function
| Lettre c ->
codage.caractre.(int_of_char c) <- List.rev prfixe
| Fin ->
codage.fin <- List.rev prfixe
| Noeud(arbre1, arbre2) ->
remplir_codage (0 :: prfixe) arbre1;
remplir_codage (1 :: prfixe) arbre2 in
remplir_codage [] arbre;
codage;;
let compresse entre sortie =
let frq = frquences entre in
let arbre = construire_arbre frq in
let codage = arbre_vers_codage arbre in
output_value sortie arbre;
seek_in entre 0;
encode entre sortie codage;;
let dcompresse entre sortie =
let arbre = input_value entre in
dcode entre sortie arbre;;
|
