Discussion :

[Spacy_green]

salut tout le monde
Dans le cadre d'un mini-projet à l'école, je dois faire l'implémentation de l'algorithme de Huffman pour la compression des fichiers. Dans l'énoncé on me demande de définir un type Bit en vue d'écrire des fonctions entrées/sortie bit à bit dans un fichier.

Mais je n'arrive pas à comprendre comment celà serait possible sachant que l'unité de traitement de l'information est l'octet (vous me corrigez svp si je me trompe)

Merci bcp d'avance

[Goundy]

Tu prend un unsigned char (taille = 1octet = 8 bits), et donc pour encoder tes caractères à chaque fois tu met le bit qu'il faut mettre à 1 à 1, et quand tu t'aperçois que tout les bits ont été utilisés tu l'écris dans le fichier, ensuite tu remet la variable à 0 et ainsi de suite ...

[Spacy_green]

Oui c'est ce que j'ai l'intention de faire, mais il faut répondre à l'énoncée et définir un type Bit avec lequel je devrais travailler (le prof veut que ce soit ainsi ), comment faire pour le définir??

[Goundy]

Code :

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

typedef unsigned char BIT;

[Spacy_green]

mais là c'est défini sur 8 bit et non un seul

[Emmanuel Delahaye]

Dans le cadre d'un mini-projet à l'école, je dois faire l'implémentation de l'algorithme de Huffman pour la compression des fichiers. Dans l'énoncé on me demande de définir un type Bit en vue d'écrire des fonctions entrées/sortie bit à bit dans un fichier.

Mais je n'arrive pas à comprendre comment celà serait possible sachant que l'unité de traitement de l'information est l'octet (vous me corrigez svp si je me trompe)

Oui. Il faut donc définir un mécanisme qui d'un coté pemet d'entrer des données caractérisée par une taille (nombre de bits : 1 à 8) et une séquence de bits.

Par exemple :

Code :

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

1
2
3
'e' : {01, 2}
...
'x' : {010100, 6}

telle que l'arbre de Huffman les a définies, et la structure 'octet' nécessaire au fichier. D'ès qu'un paquet de 8 bits est complet, il est écrit.
Le dernier paquet de 8 est envoyé tel quel (les données non utilies à 0, par exemple).

Le type 'Bit' est donc probablement un genre de

Code :

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

1
2
3
4
5
6
 
struct Bit_data
{
   unsigned bits;
   unsigned number;
};

et il faut une fonction d'écriture, avec un contexte (pour savoir où on en est de l'émission)

Code :

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

1
2
3
4
5
6
7
8
9
 
struct Bit
{
   FILE *fp;
   unsigned lastbit;
   unsigned data;
};
 
Bit_put (struct Bit *this, struct Bit_data*p_data);

et des fonctions d'init et de fin pour démarrer proprement :

Code :

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

1
2
3
 
Bit_init (struct Bit *this, char *fname);
Bit_end (struct Bit *this);

Rien que cette partie pourrait faile l'objet d'un petit TAD...

http://emmanuel-delahaye.developpez.com/tad.htm

[Spacy_green]

Je vois un peu.. il faut dire que ça n'a pas l'air aussi simple que je le croyais

Il faut aussi que je définisse une structure fic_bin qui representera un fichier ouvert et permettera de mémoriser les bits dont on aura demandé la lecture ou l'écriture mais en nombre inférieur à 8 ..

Quelqu'un purrait m'aider en m'expliquant plus clairement le rôle de cette structure ?? (moi je crois que ça ressemblerait à la structure FILE mais je ne sais pas..)

[Emmanuel Delahaye]

Je vois un peu.. il faut dire que ça n'a pas l'air aussi simple que je le croyais

Mais non, c'est très simple.

Il faut aussi que je définisse une structure fic_bin qui representera un fichier ouvert et permettera de mémoriser les bits dont on aura demandé la lecture ou l'écriture mais en nombre inférieur à 8 ..

C'est déjà ce que j'ai défini comme struct Bin (j'avais fait une erreur de copié collé).

[Spacy_green]

Code :

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

1
2
3
4
5
6
7
 
struct Bit
{
   FILE *fp;
   unsigned lastbit;
   unsigned data;
};

Est ce que vous pouvez m'expliquer s'il vous plait à quoi servent les champs de la structure au juste? je parle de "unsigned lastbit" et "unsigned data" Car là je suis un peu perdue

[Emmanuel Delahaye]

Code :

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

1
2
3
4
5
6
7
 
struct Bit
{
   FILE *fp;
   unsigned lastbit;
   unsigned data;
};

Est ce que vous pouvez m'expliquer s'il vous plait à quoi servent les champs de la structure au juste? je parle de "unsigned lastbit" et "unsigned data"

data c'est l'ensemble des bits de donnée 'à écrire'.
lastbit, c'est la position du prochain bit écrire. Une sorte de 'tableau de bits'...

Par exemple :

intialisation :

Code :

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

1
2
lastbit = 0;
data = 0;

ecrire un bit :

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
 
if (bit)
{
   data |= (1u << lastbit);
}
lastbit++;
if (lastbit == 8)
{
   /* ecrire dans le fichier */
   fputc(data, fp);
 
   /* effacer le 'tableau de bits' */
   lastbit = 0;
   data = 0;
}

Quand la boucle d'analyse est terminée emettre ce qu'il manque... :

Code :

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

1
2
3
4
5
6
7
8
9
 
if (lastbit != 0)
{
   /* ecrire dans le fichier */
   fputc(data, fp);
 
   /* fermer le fichier */
   fclose(fp);
}

C'est le principe. C'est peut être à l'envers pour des histoire de MSB en tête ou LSB en tête...

[Spacy_green]

Merci beaucoup Emmanuel, je commence à comprendre un peu. Je vais tenter avec cette solution