Un algorithme de compression

**babar56** · 06/04/2006, 13h08

Bonjour,

Ci-dessous un programme que nous avons recopié en cours. On lui donne un fichier en paramètre dans le main, et il renvoit un fichier compressé. Le taux de compression est médiocre mais sur le principe, ça fonctionne (je l'ai testé).

Cependant je ne comprends absolument pas l'idée générale du programme, l'algorithme quoi. Il est parfaitement obscure ! C'est un peu long, j'espère que ça ne pose pas problème.

La première partie, je la comprends :

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
#include <stdio.h>
 
int scanbin (char *ch)
{
	int i, k=0;
 
	for (i=strlen(ch)-1; i>=0; i--)
		k+=(ch[i]=='0')?0:1<<i;
 
	return k;
}
 
void initialisation (int tab[], int taille)
{
	int i;
 
	for (i=0; i<taille; i++)
		tab[i]=0;
}
 
struct arbre
{
	unsigned char c;
	int nboccur, parent, droite, gauche;
};
 
 
main(int argc, char *argv[])
{
	int stat[256];
	int ntot=0, i, j=0, k=0, index, pac[256], m, lg[256], mask, a=0, b=0, nbout=0, nbtot=0, l=0;
 
	char fname[40], code[32], fnameout[40];
 
	unsigned char c;
 
	struct arbre *deb;
 
	FILE *in, *out;
 
	initialisation( stat, 256);
 
	printf ("\nEntrez le nom du fichier : ");
	scanf ("%s",fname);
 
	printf ("\nEntrez le nom du fichier de sortie: ");
	scanf ("%s",fnameout);
 
	if ((in=fopen (fname,"rb"))==NULL)
		{
		printf ("Erreur ouverture %s",fname);
		exit(1);
		}
 
	while(1)
	{
		c=fgetc(in);
 
		if (feof(in))
			break;
 
		nbtot++;	
		stat[c]++;	
 
	}
 
	for (i=0; i<256; i++)
		if( stat[i] )
			j++;
 
	deb= (struct arbre*) malloc (j*2*sizeof(struct arbre));
 
	for (i=0; i<2*j; i++)
	{
		deb[i].nboccur=0;
		deb[i].parent=0;
		deb[i].droite=0;
		deb[i].gauche=0;
	}
 
	for (i=0; i<256; i++)
		if (stat[i])
		{
			deb[k].c=i;
			deb[k].nboccur=stat[i];  
			k++;	
		}
 
	k=0;

A partir de là je ne comprends plus rien :

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
 
	while (k<j)
	{
		int occ=nbtot;
 
		for( i=0; i<j+k; i++)
			if (!deb[i].parent)
				if (deb[i].nboccur<occ)
				{
					index=i;
					occ=deb[i].nboccur;
				}
 
		deb[index].parent=k+j;
		deb[k+j].gauche=index;
		deb[k+j].nboccur+=deb[index].nboccur;
 
		occ=nbtot;
 
		for( i=0; i<j+k; i++)
			if (!deb[i].parent)
				if (deb[i].nboccur<occ)
				{
					index=i;
					occ=deb[i].nboccur;
				}
 
		deb[index].parent=k+j;
		deb[k+j].droite=index;
		deb[k+j].nboccur+=deb[index].nboccur;
 
		k++;
	}
 
	int nbs=j+k;
 
	for (i=0; i<j; i++)
	{
		m=i;
 
		for (k=0; k<32; k++)
			code[k]=0;
 
		int r=0;
 
		while(1)
		{
			k=deb[m].parent;
 
			if(!k)
				break;
 
			if (deb[k].droite==m)
				code[r]='0';
			else
				code[r]='1';
 
			m=k;
			r++;
		}
 
		pac[ deb[i].c ]=scanbin(code);
		lg[ deb[i].c ]=strlen(code);
	}
 
	out=fopen (fnameout,"wb");
	if (out==NULL)
		exit(1);
 
	fwrite(&nbtot, sizeof(int), 1, out);
	fwrite(&nbs, sizeof(int), 1, out);
	fwrite(deb, sizeof(struct arbre), k, out);
 
	nbout=0;
 
	fseek(in, 0, SEEK_SET);
	a=0; b=0;
 
	while(1)
	{
		c=fgetc(in);
		mask=1<<(lg[c]-1);
 
		while(mask)
		{
			if ( pac[c]&mask )
				a+=1;
 
			a<<=1;
			mask>>=1;
			b++;
 
			if(b==32)
			{
				fwrite( &a, sizeof(int), 1, out);
				b=0;
				a=0;
			}
		}
 
		nbout++;
 
		if(nbout==nbtot)
			break;
	}
	fclose(in);
	fclose(out);
}

**Emmanuel Delahaye** · 06/04/2006, 13h20

Envoyé par babar56

Ci-dessous un programme que nous avons recopié en cours.

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
 
Project   : Forums
Compiler  : GNU GCC Compiler (called directly)
Directory : D:\dev\ed02\cb\
--------------------------------------------------------------------------------
Switching to target: default
Compiling: main.c
main.c:10: warning: no previous prototype for 'scanbin'
main.c: In function `scanbin':
main.c:13: error: implicit declaration of function `strlen'
main.c:13: warning: nested extern declaration of `strlen'
<internal>:0: warning: redundant redeclaration of 'strlen'
main.c: At top level:
main.c:20: warning: no previous prototype for 'initialisation'
main.c:35: warning: return type defaults to `int'
main.c: In function `main_':
main.c:58: error: implicit declaration of function `exit'
main.c:58: warning: nested extern declaration of `exit'
<internal>:0: warning: redundant redeclaration of 'exit'
main.c:77: error: implicit declaration of function `malloc'
main.c:77: warning: nested extern declaration of `malloc'
<internal>:0: warning: redundant redeclaration of 'malloc'
main.c:158: warning: nested extern declaration of `strlen'
<internal>:0: warning: redundant redeclaration of 'strlen'
main.c:163: warning: nested extern declaration of `exit'
<internal>:0: warning: redundant redeclaration of 'exit'
main.c:167: warning: passing arg 3 of `fwrite' as unsigned due to prototype
main.c:37: warning: unused variable `ntot'
main.c:37: warning: unused variable `l'
Process terminated with status 1 (0 minutes, 4 seconds)
7 errors, 16 warnings

Changer d'école ou de stylo...

Sinon, c'est un encodeur de Huffman. Tu n'as pas vu ça en cours ?

**babar56** · 06/04/2006, 13h30

Mon cher Emmanuel Delahaye, je peux t'assurer que le programme se compile (là, sous mes yeux !). Testé sous Mandriva, avec gcc.

A la ligne 10 on a une syntaxe un peu bizard. Un équivalent serait certainement :

Code :

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

1
2
if(ch[i]!='0')
                  k+=1<<i;

Il est probable que cette erreur ai engendré les erreurs suivantes. Peut-être qu'il faut également rajouter un #include <?> pour la fonction strlen (string length, en tous cas ici elle est reconnu simplement grâce à stdio.h).

**PRomu@ld** · 06/04/2006, 13h38

rajoute juste des options qui te permettent de vérifier que tu compiles du C ... (et du vrai C conforme à une norme)

Je pense notament à -W -Wall -pedantic, pour un début, ça suffit. Voilà ce que ça me donne :

gcc -W -Wall -pedantic test.c
test.c: In function 'scanbin':
test.c:7: warning: implicit declaration of function 'strlen'
test.c:7: warning: incompatible implicit declaration of built-in function 'strlen'
test.c: At top level:
test.c:29: warning: return type defaults to 'int'
test.c: In function 'main':
test.c:52: warning: implicit declaration of function 'exit'
test.c:52: warning: incompatible implicit declaration of built-in function 'exit'
test.c:71: warning: implicit declaration of function 'malloc'
test.c:71: warning: incompatible implicit declaration of built-in function 'malloc'
test.c:124: warning: ISO C90 forbids mixed declarations and code
test.c:133: warning: ISO C90 forbids mixed declarations and code
test.c:152: warning: incompatible implicit declaration of built-in function 'strlen'
test.c:157: warning: incompatible implicit declaration of built-in function 'exit'
test.c:31: warning: unused variable 'l'
test.c:31: warning: unused variable 'ntot'
test.c:197: warning: control reaches end of non-void function
test.c: At top level:
test.c:28: warning: unused parameter 'argc'
test.c:28: warning: unused parameter 'argv'

Je n'ai qu'un petit GCC, et je n'utilise pas toutes les options de compilations d'Emmanuel (bien que ça m'arrive quelques fois), mais considère un warning comme une erreur (en tout cas c'est ce que je fais)

**babar56** · 06/04/2006, 14h32

Envoyé par Emmanuel Delahaye

Sinon, c'est un encodeur de Huffman. Tu n'as pas vu ça en cours ?

Malheureusement, mon cours sur "l'encodeur de Huffman", je l'ai recopié dans son intégralité dans le premier post

**PRomu@ld** · 06/04/2006, 14h40

Tu n'a pas eu d'explication de plus ?

Si on parle bien de la même chose, huffman est un algo assez utilisé dont le principe est le suivant :

- tu calcules la fréquence de tes caractères du message (ou fichier) à compresser et tu les classes par ordre de fréquence d'apparittion.

La compression se fait lorsque tu écris ton fichier. On utilise moins de bits pour écrire les caractères qui apparaissent le moins souvent ...

Si tu veux plus d'info sur le sujet -> Forum algorithme.

**babar56** · 06/04/2006, 14h48

Tu n'a pas eu d'explication de plus ?

Des explications orales, mais au même moment tous les élèves doivent recopier le code au tableau qui sera rapidement effacé, on ne peut donc pas prendre note de deux choses à la fois.

Ne pourrait-on pas traduire dans les grandes lignes la partie du code que je ne maitrise pas ?

Pour être plus précis : qu'est ce que deb[i].parent ? deb je comprends parfaitement à quoi ça correspondait (je n'ai pas de problème avec les structures) mais je ne vois pas ce qu'est cet entier rataché à parent.

Et puis que fais cette première boucle ? Pourquoi refait-on exactement la même boucle juste en dessous ?

**PRomu@ld** · 06/04/2006, 14h53

Je dirai une chose : il faut que tu travailles un petit peu tout de même ...

Néanmoins ceci :

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
 
while (k<j) 
   { 
      int occ=nbtot; 
 
      for( i=0; i<j+k; i++) 
         if (!deb[i].parent) 
            if (deb[i].nboccur<occ) 
            { 
               index=i; 
               occ=deb[i].nboccur; 
            } 
 
      deb[index].parent=k+j; 
      deb[k+j].gauche=index; 
      deb[k+j].nboccur+=deb[index].nboccur; 
 
      occ=nbtot; 
 
      for( i=0; i<j+k; i++) 
         if (!deb[i].parent) 
            if (deb[i].nboccur<occ) 
            { 
               index=i; 
               occ=deb[i].nboccur; 
            } 
 
      deb[index].parent=k+j; 
      deb[k+j].droite=index; 
      deb[k+j].nboccur+=deb[index].nboccur; 
 
      k++; 
   }

Ceci, si je ne me trompes pas te permet de construire l'arbre de huffman.

Des explications orales, mais au même moment tous les élèves doivent recopier le code au tableau qui sera rapidement effacé, on ne peut donc pas prendre note de deux choses à la fois.

En un mot : travail d'équipe ! Un élève recopie le code et un autre note les explications ...

**babar56** · 06/04/2006, 15h18

Envoyé par PRomu@ld

Je dirai une chose : il faut que tu travailles un petit peu tout de même ...

On a travaillé pendant 2 séances de TP avec le prof (4h donc) pour corriger son code puisqu'à l'origine il n'avait pas déclaré la majeure partie des variables, et on avait toujours des erreurs de segmentation. Ce que je vous montre est l'aboutissement d'un long travail 8) et je suis le seul pour le moment dans la classe à avoir un fichier encodage.c qui se compile et qui fonctionne ...

**PRomu@ld** · 06/04/2006, 16h12

On a travaillé pendant 2 séances de TP avec le prof (4h donc) pour corriger son code

J'espère au moins qu'il ne s'agit pas d'un prof d'informatique ...

**Matthieu Brucher** · 06/04/2006, 17h17

Donc, Huffmann, c'est on compte les occurences des caractères dans un tableau puis on classe.
Ensuite, si mes souvenirs sont bons - je confond parfois avec Shanon Fano qui fait exactement le contraire, à savoir créer l'arbre à partir de la racine -, on "assemble les 2 éléments les plus faibles et le poids du nouvel élément est égal à la somme des 2 fils. On fait comme ça jusqu'au bout.
Après, on code par exemple le passage au fils droite par un bit à '1' et à gauche par un bit à '0'.
MAintenant, pour compresser, on prend un caractère et on met dans la sortie les différents bits qu'il a fallu choisir pour remonter à la racine.
Pour décompresser, une fois qu'on a l'arbre, on prend un bit dans le flux d'entrée et on descend dans l'arbre. Si on est à une feuille, on marque dans la sortie le caractère associé et on reprend depuis la racine.
En gros, c'est ça Huffman.

**babar56** · 06/04/2006, 19h20

Envoyé par PRomu@ld

J'espère au moins qu'il ne s'agit pas d'un prof d'informatique ...

Il paraitrait qu'il a une formation initiale en ondes sismiques.

Miles : concrêtement peux-tu faire le rapprochement avec ce programme ? Par exemple :

Code :

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

1
2
3
4
5
6
7
struct arbre 
{ 
   unsigned char c; 
   int nboccur, parent, droite, gauche; 
}; 
 
struct arbre *deb;

Alors deb[i].c et deb[i].nboccur c'est facile : le caractère et son nombre d'occurences. Qu'est-ce que parent ? Il n'y a que droite et gauche, donc on représente l'arbre sur une seule ligne ? Où est stockée l'informationdont tu parles ici :

on code par exemple le passage au fils droite par un bit à '1' et à gauche par un bit à '0'.

**Skyounet** · 06/04/2006, 20h27

Envoyé par PRomu@ld

La compression se fait lorsque tu écris ton fichier. On utilise moins de bits pour écrire les caractères qui apparaissent le moins souvent ...

C'est le contraire, on utilise beaucoup de bits pour les caracteres qui apparaissent le moins souvent, peu de bits pour ceux qui apparaissent le plus souvent

http://tcharles.developpez.com/Huffman/

**PRomu@ld** · 06/04/2006, 21h02

Oui, c'est incroyable d'écrire le contraire de ce qu'on pense !

**outs** · 08/04/2006, 02h03

Cependant je ne comprends absolument pas l'idée générale du programme, l'algorithme quoi. Il est parfaitement obscure ! C'est un peu long, j'espère que ça ne pose pas problème.

Ben si c'est même le principale problème. Si tu n'a pas compris l'algo surtout utilise une petite description en pseudo-code pour raisonner dessus. Un fois que tu a tout assimilé tu peut t'amuser avec ton code C. Cet algo est ultra-classique il est partout sur le web et dans des bouquins.

**Médinoc** · 08/04/2006, 23h12

<hs>

Envoyé par Emmanuel

error: implicit declaration of function `strlen'

Comment fait-on pour avoir une erreur et non un simple Warning ? C99 ?

</hs>

**granquet** · 08/04/2006, 23h21

<hs continué>
je crois que c'est l'option -Werror
</hs fini>

pour revenir sur le sujet, j'ai appris plain de trucs, c'est genial

**Emmanuel Delahaye** · 09/04/2006, 01h59

Envoyé par Médinoc

<hs>

Envoyé par Emmanuel

error: implicit declaration of function `strlen'

Comment fait-on pour avoir une erreur et non un simple Warning ? C99 ?

</hs>

Je republie mes reglages :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
-O2 -Wchar-subscripts -Wcomment -Wformat=2 -Wimplicit-int
-Werror-implicit-function-declaration -Wmain -Wparentheses
-Wsequence-point -Wreturn-type -Wswitch -Wtrigraphs -Wunused
-Wuninitialized -Wunknown-pragmas  -Wfloat-equal -Wundef
-Wshadow -Wpointer-arith -Wbad-function-cast -Wwrite-strings
-Wconversion -Wsign-compare -Waggregate-return -Wstrict-prototypes
-Wmissing-prototypes -Wmissing-declarations -Wmissing-noreturn
-Wformat -Wmissing-format-attribute -Wno-deprecated-declarations
-Wpacked -Wredundant-decls -Wnested-externs -Winline -Wlong-long
-Wunreachable-code