Rapport projet Huffman

Introduction :


Le codage de Huffman est utilisé dans la compression de données c'est à dire la réduction de la taille des fichiers binaires.
Ce codage a été inventé au début des années 50 par David Huffman. Originellement, il était utilisé pour compresser les fichiers textes mais il s'est depuis généralisé à tout type de fichiers (image, vidéo …).


1. Qu’est ce que le codage de Huffman :


Le code ASCII permet de coder 256 caractères différents, chaque caractère est codé sur 8 bits. L'objectif du codage de Huffman est de réduire le nombre de bits utilisés pour coder certains caractères afin de réduire la taille du fichier.
Il faut tout d'abord calculer les fréquences d'apparition des différents caractères. Ainsi, les caractères les plus fréquents seront codés sur moins de bits que les caractères avec les plus petites fréquences d'apparition.
Le codage de Huffman va donc permettre de réduire la taille du fichier codé.


Testons sur un exemple :
Si on considère un fichier texte qui contient 500 fois la lettre e et 5 fois la lettre z.
En ASCII, le codage occuperait : 8*500+5*8=4040 bits.
Maintenant, supposons qu'une fois le codage de Huffman est réalisé, la lettre e sera codé par « 0 » et la lettre z par « 1010001101 ».
Donc en utilisant le codage de Huffman, le codage occuperait : 1*500+10*5=550 bits.
On constate effectivement que la taille du fichier codé est beaucoup plus petite en utilisant le codage de Huffman et cela même si l'un des caractères peut être codé avec plus de 8 bits.


2. Huffman Classique:
La version classique du codage d’Huffman consiste à lire une première fois le fichier à compresser. Les fréquences d’apparition de chaque lettre sont enregistrées dans un tableau. Puis l’arbre d’encodage est construit à partir de ce tableau. La construction se fait de façon à ce que les lettres apparaissant le moins se retrouve en bas de l’arbre et celles qui apparaissent le plus sr retrouvent plus haut dans l’arbre.


3. Huffman adaptatif:
La version adaptative permet de construire l’arbre et le tableau de fréquences “à la volée”. On lit le fichier au fur et à mesure et en même temps, on mets l’arbre et le tableau de fréquences à jour.Ce qui constitue un avantage pour cette version.


4. Arbre et arbre de Huffman:
Pour représenter un arbre de Huffman, on utilise un arbre binaire.
Un arbre binaire est constitué d’une racine, de noeuds internes et de feuilles. Chaque noeud interne possède au maximum deux fils et chaque feuille possède un unique père. Les branches permettent de relier un père à ses fils.
Dans le cas de l'arbre de Huffman, les caractères se trouvent uniquement sur des feuilles. Les caractères avec le moins d'occurrences se trouvent en bas de l’arbre et les caractères plus fréquents se trouvent à des niveaux plus élevés. Une feuille est caractérisée par son poids et le poids d’un noeud correspond à la somme des poids de ses fils. Ici, les branches portent 1 ou 0 qui correspond à un morceau de code binaire. Le code binaire d’un caractères correspond donc à tous les bits rencontrés sur les branches pour atteindre le caractère mis côte à côte.
Particularité de l’arbre de Huffman: L’arbre est construit à la volée. Il est donc en modification permanente et la structure de l’arbre est amenée à changer sans cesse.




5. Comment construire un arbre de Huffman adaptatif:


L’arbre de Huffman doit respecter 2 règles :
-les caractère possédant une plus grande fréquence d’apparition sont codé sur moins de bits et sont donc plus hauts.
-respecter l’ordre de Gallager.
La version adaptative permet de créer cet arbre pendant le codage (ou décodage), et non après avoir parcouru le texte une première fois.
Chaque feuille est caractérisée par un poid qui correspond au nombre d'occurrence du caractère inscrit dans celle-ci.
Chaque noeud octroie un bit à ses fils. Pour la suite on décide que le fils gauche prendra le bit 0 et le fils droit le bit 1. Chaque noeud possède un poids qui est égale à la somme des poids de ses fils.
L’arbre doit aussi respecter l’ordre de Gallager, celui-ci dit qu’il faut que les poids des noeuds et des feuilles soit rangés dans un ordre décroissant de haut en bas (ie : le poid d’un noeud est supérieur ou égal à celui de ses fils) de et de gauche à droite (sur un même niveau).

L’arbre, lorsqu’il est vide, possède un(e) noeud/feuille de poid 0 et représente le caractère inconnu. Lorsque l’on va parcourir le texte il suffira de déterminer l’absence ou la présence du caractère que l’on rencontre. S’il est présent dans l’arbre on incrémente la feuille associée et on met à jour l’arbre, sinon le caractère inconnu devient un noeud dont le fils gauche est le caractère rencontré et le fils droit est le caractère inconnu. Il faut ensuite mettre l’arbre à jour.


Lorsqu’on parle de mettre à jour l’arbre, on sous entend le modifier afin qu’il respecte l’ordre de Gallager. L’ordre de Gallager ordonne de façon décroissante les poids de notre arbre, on obtient ainsi une file dont le premier terme est le caractère dont le poid est le plus élevé et dont le dernier terme est le caractère inconnu. La mise à jour est simple lorsqu’une feuille ou un noeud est incrémenté et qu’il (elle) perturbe l’ordre de Gallager, on l’échange avec le premier terme de la file (constitué par l’ordre de Gallager) dont le poid est équivalent à notre noeud/feuille AVANT l’incrémentation. On remonte ainsi l’arbre afin qu’il soit à jour.


6. Encodage et décodage


On va commencer par l’encodage.
Lors de celui-ci nous lisons le fichier à encoder caractère par caractère. Lorsque l’on rencontre un caractère qui n’est pas présent dans l’arbre (c’est le cas du premier par exemple…), on écrit le code binaire correspondant au caractère inconnu suivi du code ASCII du caractère rencontré dans un second fichier, appelé fichier encodé. On finit bien sûr par mettre à jour l’arbre (respect de l’ordre de Gallager).
Dans le cas où le caractère rencontré est déjà dans l’arbre : on met à jour l’arbre en incrémentant le poid de la feuille associée.


Passons maintenant au décodage.
De la même façon que pour l’encodage, nous devons lire le fichier encodé bit par bit.
A partir de là nous distinguons deux cas :
→  les bits lus correspondent au code du caractère inconnu
→  les bits lus correspondent à un caractère présent dans l’arbre.


Nous rappelons que l’arbre est “vide”, car dans un soucis d’optimisation, il est créé à la volé.


Lorsque les bits correspondent au code du caractère inconnu, nous lisons les 8 bits qui suivent, correspondant au code ASCII du caractère rencontré. Nous l’écrivons ainsi dans un fichier, appelé fichier décodé.
Dans le deuxième cas on écrit le caractère, reconnu dans l’arbre, dans le fichier encodé.


Après cela, nous devons mettre à jour l’arbre avec le caractère rencontré.




On va illustrer nos propos grâce à un exemple simple :


Nous allons encoder et décoder le message “ABBACD”.
Notons, pour commencer, les codes ASCII des quatres caractères :
A → 0000 1010
B → 0000 1011
C → 0000 1100
D → 0000 1101


Initialement :
notre fichier encodé est vide :   FE = “ ”
notre arbre est constitué du caractère inconnu uniquement (ARBRE 1)


Nous rencontrons le caractère A, qui n’est pas présent dans l’arbre, on écrit alors le code du caractère inconnu suivi du code ASCII de A (que l’on écrira en rouge ici) dans notre fichier encodé :  FE = “000001010”


L’arbre possède maintenant 2 caractères : le caractère inconnu , et le caractère A.


ARBRE 2




Nous rencontrons le caractère B, qui n’est pas présent dans l’arbre, on écrit donc le code du caractère inconnu suivi du code ASCII de B dans notre fichier encodé : FE = “000001010100001011”


ARBRE 3


Nous rencontrons de nouveau le caractère B, qui cette fois est présent dans l’arbre. Nous écrivons donc son code binaire dans l’arbre.
FE = “00000101010000101110”


ARBRE 4


Nous rencontrons le caractère A, présent dans l’arbre. Nous écrivons son code binaire dans l’arbre.
FE = “0000010101000010111010”


ARBRE 5


Nous rencontrons le caractère C, qui n’est pas présent dans l’arbre, on écrit le code binaire du caractère inconnu suivi du code ASCII de C dans le fichier encodé : FE = “00000101010000101110101100001100”




ARBRE 6


Nous rencontrons le caractère D, qui n’est pas présent dans l’arbre, on écrit le code binaire du caractère inconnu suivi du code ASCII de D dans le fichier encodé : FE = “0000010101000010111010110000110001100001101”


ARBRE 7


7.Structures de données utilisées:
Arbre: Nous allons utiliser une structure arbre.


typedef struct arbre{


    int type ;
    int val ;
    char etiq ;


    struct arbre*fg ;
    struct arbre*fd ;


}t_arbre, *tpa ;


Cette structure est constituée d’un premier champ type qui devra contenir un 0 ou un 1, selon l’élément représenté. S’il s’agit d’une feuille type vaudra 1 et s’il s’agit d’un noeud il sera à 0.
Le champ val ne sera utilisé que s’il s’agit d’une feuille. On y placera la valeur d’une feuille.
Le champ etiq ne sera utilisé que s’il s’agit d’un noeud. On y placera l’étiquette du noeud.
Les deux derniers champs sont des pointeurs sur des structures arbres qui représentent les fils droit et gauche.


Afin de manipuler ces arbres nous allons avoir besoin de plusieurs fonctions abstraites sur les arbres:

(Ces fonctions ont été vues en tp d’algorithmique)
tpa cree_feuille (int val): créer un élément de type de type feuille et lui affecter la valeur val.
int est_feuille(tpa arbre): Renvoie un booléen qui nous dit si l’élément examiné est une feuille ou non.
int val_feuille(tpa arbre): Renvoie la valeur d’une feuille.
tpa cree_noeud (char etiq, tpa fg, tpa fd): Créer un noeud et lui affecter un fils droit et un fils gauche.
tpa arbre_fg(tpa noeud): Renvoie le fils gauche d’un noeud.
tpa arbre_fd(tpa noeud): Renvoie le fils droit d’un noeud.
char arbre_etiq(tpa noeud): Renvoie l’étiquette d’un noeud.


(Idées de modifications des fonctions existantes ou de nouvelles fonctions):
ajouter le poids, l’ordre en paramètres des ADT déjà existantes?
ADT pour modifier le poids et l’ordre après la mise à jour.
ADT pour permuter des éléments si la mise à jour le demande.


Nous allons également manipuler des tableaux:
Un tableau de 256 cases contenant les 256 caractères du code ASCII avec leur fréquences d’apparition et des pointeurs vers la feuille qui contient le caractère.
Un tableau afin de permettre la mise à jour de l’ordre de Gallager.
8. Compilation séparée: