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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
public class Huffman
{
// Nom du fichier à compresser.
public String fichier;
// Tableau <clé,valeur>.
public CléCodage[] tab;
// Arbres d'Huffman.
public LinkedList arbres;
// Codes binaires.
public Hashtable codesBinaires;
// Données.
public LinkedList buffer;
public Huffman(String fichier)
{
this.fichier = fichier;
tab = new CléCodage[256];
arbres = new LinkedList();
buffer = new LinkedList();
for(int i = 0; i < tab.length; ++i)
tab[i] = new CléCodage(i,0);
}
// Lit le fichier et construit l'arbre d'Huffman.
public void arbreCodage()
{
try
{
DataInputStream fic = new DataInputStream(new FileInputStream(fichier));
while(fic.available() != 0)
{
int octet = fic.readUnsignedByte();
++tab[octet].frequence;
buffer.add(octet);
System.out.print((char)octet);//Affichage du mot a coder
}
fic.close();
}
catch(IOException ex){}
for(int i = 0; i < tab.length; ++i)
if(tab[i].frequence != 0)
arbres.add(new Arbre(tab[i],null,null));
codesBinaires = new Hashtable(arbres.size());
Collections.sort(arbres);
while(arbres.size() > 1)
{
Arbre a1 = (Arbre)arbres.get(0);
Arbre a2 = (Arbre)arbres.get(1);
arbres.remove(0);
arbres.remove(0);
Arbre nouveau = null;
int somme = a1.elem.frequence + a2.elem.frequence;
if(a1.elem.frequence <= a2.elem.frequence)
nouveau = new Arbre(new CléCodage(-1,somme),a1,a2);
else
nouveau = new Arbre(new CléCodage(-1,somme),a2,a1);
arbres.add(nouveau);
Collections.sort(arbres);
}
Arbre arbre = (Arbre)arbres.get(0);
System.out.println();
coder(arbre,"");
}
// Remplit le tableau des codes binaires.
public void coder(Arbre arbre, String code)
{
if(arbre.gauche != null)
coder(arbre.gauche,code + "0");
if(arbre.elem.cle != -1)
{
codesBinaires.put(arbre.elem.cle,code);
System.out.println((char)arbre.elem.cle + " : " + code);//Affichage du code de chaque lettre du mot.
}
if(arbre.droit != null)
coder(arbre.droit,code + "1");
}
// Compresse le fichier et écrit dans le fichier sortie.
public void compresseFichier(String sortie)
{
LinkedList tampon = new LinkedList();
for(int i = 0; i < buffer.size(); ++i)
{
int octet = (Integer)buffer.get(i);
String s = (String)codesBinaires.get(octet);
for(int j = 0; j < s.length(); ++j)
tampon.add("" + s.charAt(j));
}
try
{
DataOutputStream out = new DataOutputStream(new FileOutputStream(sortie));
String s2="";
for(int k = 0; k < tampon.size(); ++k){
System.out.print(tampon.get(k));//Affichage du mot codé
s2+=tampon.get(k);
}
byte msg[]= new byte[1000];
msg = s2.getBytes();
out.write(msg);
}
catch(IOException ex){}
}
public static void main(String[] args)
{
Huffman h = new Huffman("C:\\Recherche\\toto.txt");
h.arbreCodage();
h.compresseFichier("C:\\Recherche\\titi.txt");
System.out.println();
}
} |
