Discussion :

[Rydley]

Bonjour à tous,

Je débute en java et je dois, dans le cadre d'un projet, coder l'algorithme de codage de Huffman. J'ai écrit un programme qui n'a pas l'air de fonctionner correctement. En effet, si je prend par exemple le codage du mot java, j'obtiens le mot binaire suivant : 0111011 avec pour table de codage :

j: 0
v: 10
a: 11.

Or la lettre "a" apparait 2 fois dans le mot java, elle devrait donc avoir le code le plus cours, il y a donc une erreur dans la construction de mon arbre de codage et je ne vois pas ou peut être l'erreur. Voici mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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();
	}
}

J'aimerais donc savoir si quelqu'un voit d'où provient mon erreur.
Voila d'avance merci

[bilred]

Bonjour,

Si tu peux m'expliquer comment, implémenter la structure d'arbre en java avec les LinkedList et Hashtable.

Merci d'avance.

[magikk]

je suis incapable de t'aider,mais je ne dirai qu'une chose:pas mal pour un débutant.Pour moi débuter un langage c'est plutot:comment fonctionne une boucle , etc..
Bon courage

[devyan]

Salut,

Tes poids ne serainet-ils pas simplement "à l'envers" puisque a>11 et que tu désires a>0