CODAGE DE HUFFMAN

ANTOINE ThomasBENMEZIANE Mélina

ERHEL MathieuKELLER Florence

MANGIN YannROLLOT Jordan

Atelier « Maths en Jeans »Année scolaire 2007-2008

Lycée Louis Lapicque - Épinal

Le codage de Huffman est un processus qui permet de compresser des données informatiques afin de libérer de la place dans la mémoire d'un ordinateur. Or tout fichier informatique (qu'il s'agisse d'un fichier texte, d'une image ou d'une musique) est formé d'une suite de caractères. Chacun de ces caractères étant lui-même codé par une suite de 0 et de 1. L'idée du codage de Huffman est de repérer les caractères les plus fréquents et de leur attribuer des codes courts (c'est-à-dire nécessitant moins de 0 et de 1) alors que les caractères les moins fréquents auront des codes longs. Pour déterminer le code de chaque caractère on utilise un arbre binaire. Cet arbre est également utilisé pour le décodage.

Nous avons aussi fait des recherches sur un autre procédé appelé transformation de Burrows Wheeler. Pour cela il faut construire deux tableaux (une permutation permet de passer de l'un à l'autre). On peut alors procéder à des regroupements de lettres de façon à transformer le texte initial. L'application du codage de Huffman sur ce texte transformé permet alors (en général) une compression encore meilleure.

Enfin, nous avons essayé de mettre en œuvre le codage de Huffman en rédigeant un programme en langage C permettant de construire l'arbre binaire nécessaire au codage du fichier. Si notre programme ne fournit pas le codage final, il permet tout de même de connaître la taille du codage final et de la comparer avec la taille du codage initial.

2

Table des matières

Introduction ...................................................................................................................................................... 5

1 Exemple de codage de Huffman .................................................................................................................... 6 1.1 Quelques définitions informatiques ....................................................................................................... 6

1.1.1 Codage d'un caractère .................................................................................................................... 6 1.1.2 Extensions du codage ASCII ......................................................................................................... 7 1.1.3 Bits ................................................................................................................................................ 7 1.1.4 Poids .............................................................................................................................................. 8 1.1.5 Taux de compression ..................................................................................................................... 8

1.2 Notion d'arbre ........................................................................................................................................ 8 1.2.1 Définitions : nœuds, branche, racine, feuilles ................................................................................ 8 1.2.2 Arbre binaire .................................................................................................................................. 9

1.3 Description de l'algorithme du codage de Huffman ............................................................................... 9 1.4 Exemple ............................................................................................................................................... 10

1.4.1 Construction du tableau ............................................................................................................... 10 1.4.2 Construction de l'arbre ................................................................................................................. 10 1.4.3 Taux de compression ................................................................................................................... 12

1.5 Décodage ............................................................................................................................................. 13

2 Transformation de Burrows Wheeler ........................................................................................................... 14 2.1 Un premier tableau .............................................................................................................................. 14

2.1.1 Principe ........................................................................................................................................ 14 2.1.2 Exemple ....................................................................................................................................... 14

2.2 Un second tableau ................................................................................................................................ 15 2.2.1 Principe ........................................................................................................................................ 15 2.2.2 Exemple ....................................................................................................................................... 15 2.2.3 Comment passer d'un tableau à l'autre ......................................................................................... 16

2.3 Texte transformé .................................................................................................................................. 17 2.3.1 Codage du texte transformé ......................................................................................................... 17 2.3.2 Comment retrouver le texte initial? .............................................................................................. 18

3 Définitions complémentaires ....................................................................................................................... 19 3.1 Étage et position .................................................................................................................................. 19

3.1.1 Définitions ................................................................................................................................... 19 3.1.2 Passage de position à étage .......................................................................................................... 20

3.2 Notion de pointeur ............................................................................................................................... 20 3.2.1 Définition ..................................................................................................................................... 20 3.2.2 Application à la représentation informatique d'un arbre ............................................................... 21

4 Programmation en C du codage de Huffman ............................................................................................... 23 4.1 Différentes étapes du programme ........................................................................................................ 23

4.1.1 Fonction principale ...................................................................................................................... 23 4.1.2 Principe général ........................................................................................................................... 23

4.2 Lecture du fichier initial ...................................................................................................................... 24 4.2.1 Tableau des effectifs de chaque caractère .................................................................................... 24

3

4.2.2 Lecture du tableau des effectifs ................................................................................................... 25 4.3 Construction de l'arbre ......................................................................................................................... 25

4.3.1 Obtention de deux minimums ...................................................................................................... 25 4.3.2 Nombre de caractères distincts .................................................................................................... 26 4.3.3 Création de l'arbre ........................................................................................................................ 27 4.3.4 Affichage de l'arbre ...................................................................................................................... 29

4.4 Étage et position .................................................................................................................................. 29 4.4.1 Écriture des positions ................................................................................................................... 30 4.4.2 Calcul de l'étage en fonction de la position .................................................................................. 30

4.5 Calcul du taux de compression ............................................................................................................ 30 4.5.1 Obtention de la taille du fichier compressé .................................................................................. 30 4.5.2 Préambule d'un fichier compressé ................................................................................................ 31

4.6 Exemple ............................................................................................................................................... 31

5 Annexe ......................................................................................................................................................... 34 5.1 Fichier main.c ...................................................................................................................................... 34 5.2 Fichiers Jordan ..................................................................................................................................... 34

5.2.1 Fichier Jordan.h ........................................................................................................................... 34 5.2.2 Fichier Jordan.c ........................................................................................................................... 35

5.3 Fichiers Thomas .................................................................................................................................. 35 5.3.1 Fichier Thomas.h ......................................................................................................................... 35 5.3.2 Fichier Thomas.c ......................................................................................................................... 36

5.4 Fichiers creation_arbre ........................................................................................................................ 37 5.4.1 Fichier creation_arbre.h ............................................................................................................... 37 5.4.2 Fichier creation_arbre.c ............................................................................................................... 37

Conclusion ...................................................................................................................................................... 40

4

Introduction

Cet écrit est la synthèse des recherches effectuées dans le cadre de l'atelier « Maths en Jeans » au lycée Louis Lapicque d'Épinal durant l'année scolaire 2007-2008.

Cette expérience a commencé en septembre 2007 lors d'une réunion avec Monsieur Stéphane Gaussent, chercheur à l'institut Élie Cartan de Nancy. Il nous a exposé les différents sujets que l'on pourrait traiter. À la suite de cela, nous avons choisi de travailler sur le codage de Huffman. Ce sujet nous plaisait car l'informatique nous intéresse.

Le codage de Huffman est un algorithme informatique permettant de compresser des données (quelles que soient ces données). Il est en particulier utilisé pour une compression en « mp3 » (format d'un fichier son), « jpeg » (format d'une image) ou « mpeg » (format d'une vidéo).

Notre groupe est séparé en deux équipes de trois personnes : d'une part Florence Keller, Jordan Rollot et Thomas Antoine et d'autre part Mélina Benmeziane, Yann Mangin et Mathieu Erhel. Les deux groupes ont commencé par écrire des arbres à la main, puis le premier groupe s'est orienté vers une approche informatique du sujet (début du chapitre 1, chapitres 3 et 4) tandis que l'autre a travaillé sur le sujet de façon plus théorique et en étudiant une variante du codage de Huffman (chapitres 1 et 2). Nous avons travaillé chacun de notre côté jusqu'au premier entraînement avant le congrès de Paris. Le jour de l'exposé à Paris qui a eu lieu à la fin du mois de mars 2008, tout le groupe était plus ou moins tendu, c'était la première fois que l'on exposait nos travaux dans un amphithéâtre devant une cinquantaine de personnes. Malgré cela tout le monde en garde un très bon souvenir, car cette expérience peut nous aider lors d'un oral à l'école (par exemple).

Les mois d'avril et de mai 2008 ont été consacré à la rédaction de ce rapport. Chacune des deux équipes a travaillé de son côté, puis nous avons effectué une synthèse.

5

Chapitre 1

Exemple de codage de Huffman

1.1 Quelques définitions informatiques

1.1.1 Codage d'un caractère

Tout fichier informatique est constitué de caractères. Un caractère est une lettre (majuscule ou minuscule), un chiffre, un signe de ponctuation ou un symbole non imprimable (par exemple un retour à la ligne, une tabulation, un signal sonore émis par l'ordinateur...). Cet ensemble de caractères est appelé code ASCII et correspond à la liste ci-dessous :

On remarque dans cette liste que chaque caractère est repéré par un numéro. Ainsi de 0 à 31 on a les

6

caractères non imprimables, de 32 à 47 la majorité des signes de ponctuation, de 48 à 57 les chiffres, de 58 à 64 d'autres signes de ponctuation, de 65 à 122 les lettres majuscules puis minuscules. Enfin de 123 à 127 se trouvent différents symboles.

1.1.2 Extensions du codage ASCII

On constate également dans la liste précédente l'absence de caractères accentués. C'est pourquoi, les ordinateurs actuels utilisent un jeu étendu du code ASCII. En fait, ils en utilisent même plusieurs. Par exemple, sous le système d'exploitation WINDOWS™, il y a en a au moins deux : le premier est utilisé lorsqu'on travaille sous MS-DOS™, le second lorsqu'on travaille dans l'environnement graphique WINDOWS™. Voici le tableau de tous les caractères qui correspond au code ASCII (parties rose et bleu foncé) étendu soit dans sa version DOS soit dans sa version WINDOWS (jeu de caractères dit « CP1252 » ou « ANSI »):

Par exemple, le caractère « é » est numéroté 233 sous WINDOWS mais le même caractère correspond à « Ù » sous DOS!

1.1.3 Bits

On appelle bit la plus petite unité de stockage en informatique. Il s'agit d'un 0 ou d'un 1. Chaque caractère (ou plus précisément chaque numéro de caractère selon la table utilisée) est codé à l'aide de bits.

7

Avec un bit, on peut coder deux numéros: 0 ou 1. Avec deux bits, on peut coder quatre numéros : 00, 01, 10 et 11. Plus généralement avec n bits on peut coder 2n numéros. Or une table étendue comporte 256 caractères (de 0 à 255), on comprend donc pourquoi un caractère est codé sur 8 bits. On parle alors d'un octet.

1.1.4 Poids

Chaque caractère pesant un poids constant de 8 bits, tout l'intérêt d'un algorithme de compression est de faire en sorte que certains caractères pèsent moins que 8 bits de sorte que le fichier final pèse moins que le fichier initial.

Par exemple un fichier contenant uniquement les mots « lycée lapicque » contient 14 caractères et pèse donc 112 bits.

1.1.5 Taux de compression

On appelle taux de compression le rapport suivant:

taux decompression= poids du fichier finalpoids du fichier initial

Bien entendu le taux de compression est un nombre entre 0 et 1. Plus il est proche de 0 et meilleure est la compression.

1.2 Notion d'arbre

1.2.1 Définitions : nœuds, branche, racine, feuilles

Considérons un ensemble de diverses informations (cela peut être des caractères, des effectifs et même ces deux informations à la fois). Chacune de ces informations est appelée nœud.

Entre les différents nœuds, existent des relations appelées branches et symbolisées par des flèches et telles que chaque nœud est relié à l'ensemble des autres nœuds de l'arbre par au moins une branche.

Il existe un nœud particulier appelé racine : c'est le nœud initial d'où partent toutes les branches. Il existe également des nœuds appelés feuilles : ce sont les nœuds où arrive une branche sans que d'autres branches partent de ces nœuds. Ce sont les nœuds qui « terminent » l'arbre.

8

1.2.2 Arbre binaire

Sur le schéma ci-dessous, on a représenté un arbre. En rouge se trouve le nœud racine, en vert les feuilles, les autre nœuds sont laissés en bleu.

On constatera que de chacun des nœuds partent deux branches (on parle d'arbre binaire), exception faite des feuilles d'où ne part aucune branche. Mais, en pratique, il y a bel et bien deux branches qui partent des feuilles mais elles ne visent aucun nœud (voir le paragraphe sur les pointeurs).

1.3 Description de l'algorithme du codage de Huffman

Il faut compter tout d’abord tous les caractères du fichier à coder et affecter à chacun d’entre eux son « poids » d’apparition. On obtient alors un tableau où chaque case correspond à un caractère et son poids, tout étant rangé dans l'ordre du codage « CP1252 ».

Avec ce tableau, on va construire un arbre. Chacune des cellules du tableau sera une feuille de cet arbre. Pour compléter cet arbre, il faut associer les caractères ensemble : on va associer les caractères ayant le plus petit poids pour former un nouveau nœud.

Ainsi, on demande à l'ordinateur de choisir les deux caractères ayant les « poids » les plus faibles. En cas d'égalité entre différents « poids », on choisit en priorité le premier caractère dans l'ordre correspondant au codage « CP1252 ». Après cela, on ajoute un nœud à l'arbre où on mémorise la somme des deux poids des caractères choisis précédemment. On réitère le processus en considérant l'arbre obtenu (ôté des deux caractères précédemment sélectionnés mais avec le nœud supplémentaire). Ensuite, on refait ainsi pour tous les caractères suivants jusqu'au dernier.

9

Une fois que tous les caractères sont associés les uns aux autres on a un arbre qui se finit avec 1 seul nœud qui contient le nombre de lettres à coder.

Une fois l'arbre terminé on va associer un bit aux branches de l’arbre, c'est-à-dire que l’on va choisir, par convention, que les branches de gauche correspondent à 0 et que les branches de droite correspondent à 1.

1.4 Exemple

1.4.1 Construction du tableau

Prenons un exemple. Cherchons à coder la phrase : « Recherche chat châtain ».

Pour simplifier, on ne tient pas compte des espaces, de l'accent circonflexe ni bien sûr des guillemets. Ainsi, on cherche à coder la phrase :

recherchechatchatain

● On repère la lettre la plus utilisée : le c apparaît 4 fois, de même que h.● Puis les lettres a et e apparaissent 3 fois.● Ensuite les lettres t, r apparaissent 2 fois.● Pour finir les lettres i et n apparaissent 1 fois.

On obtient donc le tableau suivant :

caractère a c e h i n r t

poids 3 4 3 4 1 1 2 2

1.4.2 Construction de l'arbre

Ce tableau nous permet de construire les feuilles de l'arbre:

On détermine ensuite les deux lettres de poids le plus faible : ici les lettres i et n sont de poids 1. On représente deux branches qui se rejoignent et qui relient les deux lettres les moins fréquemment utilisées:

10

a 3 c 4 e 3 h 4 i 1 n 1 r 2 t 2

a 3 c 4 e 3 h 4 i 1 n 1 r 2 t 2

2

On réitère le processus en constatant que les deux caractères de poids minimum sont r et t :

Les deux poids minimums sont ceux du nœud a et de poids 2 :

Les deux minimums sont ensuite les nœuds dont les caractères sont e et c :

Les deux minimums sont alors les nœuds de poids 4 :

On relie ensuite les nœuds de poids 5 et 7 pour obtenir un nœud de poids 12. On arrive ainsi nœud final en

11

a 3 c 4 e 3 h 4 i 1 n 1 r 2 t 2

2 4

a 3

c 4 e 3 h 4 i 1 n 1 r 2 t 2

2 4

5

a 3

c 4e 3 h 4 i 1 n 1 r 2 t 2

2 4

5

7

a 3

c 4e 3

h 4

i 1 n 1

r 2 t 2 2

4 5

7

8

reliant ces deux derniers nœuds :

Ensuite , par convention, on place un 0 à gauche de chaque branche et un 1 à droite de chaque branche :

Ce qui va nous permettre de coder les lettres à l’aide de 0 et 1. Ainsi le codage de r donne 100, celui de e donne 001 et ainsi de suite. Le codage de recherchechatchatain donne :

0101101110011001011100110111001010111110010101110110001001

1.4.3 Taux de compression

12

a 3 c 4e 3

h 4

i 1 n 1

r 2 t 2 2

4 5 7

8 12

20

a 3 c 4e 3

h 4

i 1 n 1

r 2 t 2 2

4 5 7

8 12

20

0

0

0

0

0

0

0

1

1

11

1

1

1

La phrase recherchechatchatain contient 20 caractères (voir le nœud racine!), chacun étant codé sur 8 bits, un fichier contenant cette page pèse 160 bits. Si on compte le nombre de bits obtenus après compression on en a 58. Ainsi le taux de compression est :

taux decompression= 58160=0,3625

1.5 Décodage

On a vu que l'on obtient le codage suivant :

0101101110011001011100110111001010111110010101110110001001

On se pose naturellement la question suivante : Comment à partir du codage qui est là, retrouver la phrase de départ ?

En fait, il suffit de prendre le code en entier et de « l'enfiler » directement par la racine. Reprenons l'exemple précédent :

Le code est : 0101101110011001011100110111001010111110010101110110001001

Avec cela on ne sait pas si le code de la lettre est en 3,4,5 ou même 6 bits mais ce n'est pas un problème. On regarde bit par bit et on se dirige ainsi dans toutes les branches de l'arbre :

● Le premier bit est 0, donc on se dirige vers la gauche, le second est 1, donc on se dirige vers la droite. Ensuite, le bit est 0 donc on se dirige vers la gauche. On arrive alors à une feuille de l'arbre : celle qui correspond au caractère r.

● De même 110 correspond à e et ainsi de suite...

13

Chapitre 2

Transformation de Burrows Wheeler

2.1 Un premier tableau

2.1.1 Principe

Dans ce chapitre, on note T la phrase à coder. On utilise un tableau formé de 3 colonnes : La première colonne est constituée de la suite des lettres de la phrase de départ, cette suite sera nommée Ti et la première lettre sera appelée T1, puis la deuxième T2 et ainsi de suite...

Dans la deuxième colonne on indique un numéro correspondant à l’apparition dans T de chaque lettre. Dans la troisième colonne, on écrit la suite S correspondant aux lettres précédentes. Chaque Si sera égal aux lettres écrites avant le Ti correspondant.

2.1.2 Exemple

Reprenons la phrase recherchechatchatain. On obtient alors le tableau suivant :

Ti i Si

r 1 ∅

e 2 r

c 3 er

h 4 cer

e 5 hcer

r 6 ehcer

c 7 rehcer

h 8 crehcer

e 9 hcrehcer

14

c 10 ehcrehcer

h 11 cehcrehcer

a 12 hcehcrehcer

t 13 ahcehcrehcer

c 14 tahcehcrehcer

h 15 ctahcehcrehcer

a 16 hctahcehcrehcer

t 17 ahctahcehcrehcer

a 18 tahctahcehcrehcer

i 19 atahctahcehcrehcer

n 20 iatahctahcehcrehcer

2.2 Un second tableau

2.2.1 Principe

Ensuite à l’aide du premier tableau nous allons construire un autre tableau toujours constitué de 3 colonnes.

Dans la première colonne que l’on appellera Sj, on va classer les Si dans l’ordre alphabétique. Puis on met en face dans la deuxième colonne nommée j, l’ordre d’apparition des Sj. Enfin dans la dernière colonne on inscrira la lettre correspondante au Sj notée tj.

2.2.2 Exemple

Sj j tj

∅ 1 r

ahcehcrehcer 2 t

ahctahcehcrehcer 3 t

atahctahcehcrehcer 4 i

cehcrehcer 5 h

cer 6 h

crehcer 7 h

ctahcehcrehcer 8 h

ehcer 9 r

ehcrehcer 10 c

15

er 11 c

hcehcrehcer 12 a

hcer 13 e

hcrehcer 14 e

hctahcehcrehcer 15 a

iatahctahcehcrehcer 16 n

r 17 e

rehcer 18 c

tahcehcrehcer 19 c

tahctahcehcrehcer 20 a

2.2.3 Comment passer d'un tableau à l'autre

On pourra noter qu’il n’y a aucune perte entre ces deux tableaux, on peut retrouver un des deux tableaux à partir du deuxième. Pour cela on compare l’emplacement des j et des i :

T S t s

i Si sj j

1 ∅ ∅ 1

2 r r 17

3 er er 11

4 cer cer 6

5 hcer hcer 13

6 ehcer ehcer 9

7 rehcer rehcer 18

8 crehcer crehcer 7

9 hcrehcer hcrehcer 14

10 ehcrehcer ehcrehcer 10

11 cehcrehcer cehcrehcer 5

12 hcehcrehcer hcehcrehcer 12

13 ahcehcrehcer ahcehcrehcer 2

14 tahcehcrehcer tahcehcrehcer 19

15 ctahcehcrehcer ctahcehcrehcer 8

16 hctahcehcrehcer hctahcehcrehcer 15

17 ahctahcehcrehcer ahctahcehcrehcer 3

18 tahctahcehcrehcer tahctahcehcrehcer 20

19 atahctahcehcrehcer atahctahcehcrehcer 4

16

20 iatahctahcehcrehcer iatahctahcehcrehcer 16

Il est donc question entre les deux premiers tableaux d’une permutation σ de 20 éléments. On a représenté cette permutation (de j vers i) dans le tableau ci-dessous :

j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

i 1 13 17 19 11 4 8 15 6 10 3 12 5 9 16 20 2 7 14 18

2.3 Texte transformé

2.3.1 Codage du texte transformé

Notre second tableau permet d'obtenir un nouveau texte. Il suffit de reprendre tous les tj :

rttihhhhrccaeeanecca

On peut alors coder ce texte par le codage de Huffman. Mieux, on peut le coder en utilisant de nouveaux caractères : « double t » noté t2, « quadruple h » noté h4 et ainsi de suite :

rt2ih4rc2ae2anec2a

Ainsi le caractère r apparaît deux fois, le caractère t2 une fois, le caractère i une fois, le caractère h4 une fois, le caractère c2 deux fois, le caractère a trois fois, le caractère e2 apparaît une fois, le caractère n une fois et le caractère e une fois également. On obtient ainsi l'arbre suivant :

On a donc le codage suivant :

0100010101001101001111000111000111000010001111

17

n 1

r 2 c2 2

40 1

2

0 1

t2 1 h4 1e2 1

0 1

40 1

2

1

a 3

0

i 1

02

e 1

1

58

0 1

130 1

On obtient ici un résultat de 46 bits, ce qui nous fait alors un gain de 12 bits par rapport au codage de Huffman sur le texte initial et de 114 bits sur le texte sans compression.

2.3.2 Comment retrouver le texte initial?

Cependant, cela n'est qu'une théorie car la création du second tableau nécessite la permutation σ . Or, il faut a priori mémoriser toute cette permutation pour pouvoir à partir du texte transformé retrouver le texte initial.

En fait, on nous a expliqué qu'il n'était pas nécessaire de mémoriser l'ensemble de la permutation mais nous n'avons pas eu le temps d'étudier cette propriété de la transformation de Burrows-Wheeler.

18

Chapitre 3

Définitions complémentaires

3.1 Étage et position

3.1.1 Définitions

On cherche à numéroter les nœuds d'un arbre. On appelle un tel numéro la position du nœud. On part du nœud le plus bas (appelé racine) à qui on affecte la position n = 1 et ensuite, pour le nœud suivant à gauche, on multiplie n par 2 (ainsi le nœud situé en haut gauche de la racine a pour position n = 2). Pour le nœud se situant à droite de la racine, on multiplie n par 2 et on ajoute 1 (ainsi le nœud situé en haut gauche de la racine a pour position n = 3). On réitère le procédé ainsi jusqu'aux feuilles :

Les numéros des nœuds se situant à l’extrême gauche s'écrivent tous sous la forme 2p. Les autres nœuds étant plus vers la droite, ont une position comprise entre 2p et 2p+1 – 1. On dit alors que ces nœuds sont situés à l'étage p.

19

a 3 c 4e 3

h 4

i 1 n 1

r 2 t 2 2

4 5 7

8 12

20

0

0

0

0

0

0

0

1

1

11

1

1

1

1

2

4 5

10 11

3

6

12 13

7

14 15

24 25

Étage 0

Étage 1

Étage 2

Étage 3

Étage 4

Or p représente le nombre de bits nécessaires pour coder le nœud. Donc connaissant l'étage associé à chaque feuille (en fonction de sa position dans l'arbre), on peut déterminer le nombre de bits nécessaires pour coder un caractère.

3.1.2 Passage de position à étage

Cherchons à calculer l'étage p connaissant la position i du nœud : Pour savoir comment on passe de la position d’un nœud à l’étage où il se trouve dans l’arbre, il suffit d'utiliser les logarithmes. Étant en première, nous ne connaissons pas les logarithmes, mais on nous a dit deux choses:

● la fonction ln est croissante sur ]0; ∞ [● Pour tous réels a>0 et b>0 on a : ln ab = b ln a

On a vu que 2p ≤ i < 2p+1 donc :

ln 2p ≤ ln i < ln 2p+1 (car la fonction ln est croissante)p ln 2 ≤ ln i < (p+1) ln 2 (d'après la seconde propriété)

p ≤ ln iln 2

< p+1 (comme on divise par ln 2, il faut que celui-ci soit positif, or

d'après la calculatrice, ln 2 est égal à environ 0,69)

De l'inégalité ln iln 2

< p+1, on déduit ln iln 2

-1 < p et donc :

ln iln 2

-1 < p ≤ ln iln 2

On en déduit que p = E lniln 2 (où E désigne la fonction partie entière).

3.2 Notion de pointeur

3.2.1 Définition

Un pointeur est une variable contenant l'adresse d'une autre variable. Par exemple, quand on crée un entier a codé sur quatre octets, l’ordinateur attribue quatre octets dans sa mémoire pour stocker cet entier. Le pointeur relatif à a est le numéro du premier octet où se trouve a.

Par exemple on peut coder :

int a;

Si on souhaite obtenir la valeur de a et, par exemple, décider que la valeur de a est 1, on écrira :

20

a = 1;

On peut aussi avoir besoin du pointeur sur a. On écrira alors &a.

En fait, on manipule au moins aussi souvent des pointeurs sur les objets que les objets eux-mêmes. Pour déclarer un pointeur (par exemple sur un entier) on écrira :

int *b;

Alors *b désigne l'entier pointé par b et b est le pointeur, c'est-à-dire l'adresse de *b.

Le programme ci-dessous montre comment on manipule les pointeurs :

#include <stdio.h>

int main(int argc, char* argv[]){

int a; // a est un entiera = 1; // initialisé à 1printf("Valeur de a : %i\n",a);printf("Adresse de a : %p\n",&a);

int *b; // b est un pointeur

b = &a; // qui pointe sur a

printf("Valeur de b : %i\n",*b);printf("Adresse de b : %p\n",b);return 0;

}

3.2.2 Application à la représentation informatique d'un arbre

Dans un arbre binaire il y a un ensemble de nœuds. Chaque nœud est constitué de données et de deux branches vers d'autres nœuds. Chacune de ces branches est en fait un pointeur vers un nœud. On a donc créer l'objet tree de la façon suivante : un caractère de type uchar, un poids (il est nommé weight de type long), une position (de type long) et enfin deux pointeurs *left et *rightsur des objets de type tree.

typedef struct tree {uchar c;long weight;long pos;struct tree *left, *right;

} tree;

Il suffit donc de connaître l'adresse du nœud racine pour pouvoir remonter à n'importe quel nœud ou n'importe quelle feuille. Remarquons enfin que les feuilles sont des nœuds particuliers puisqu'il n'en émane aucune branche. Ici on aura simplement deux pointeurs qui pointent sur une adresse particulière : l'adresse NULL. On écrira donc, s'il s'agit d'une feuille de l'arbre a :

21

a.left = NULL;a.right = NULL;

Si bien sur a est un pointeur sur un arbre on aura :

(*a).left = NULL;(*a).right = NULL;

22

Chapitre 4

Programmation en C du codage de Huffman

4.1 Différentes étapes du programme

4.1.1 Fonction principale

Le point d'entrée d'un programme écrit en C est la fonction « main » qui appelle toute les autres fonctions. Voici cette fonction :

int main(int argc, char *argv[]){

FILE* source = fopen("exemple.txt", "r+");long* eff = Jordan(source);tree* arbre = creer_arbre(eff);afficher_arbre(arbre);printf("\n\nTaux   de   compression   :   %lf\n",   (   ((double) 

taille(arbre)) / (8*ftell(source)) ) );fclose(source);system("PAUSE");return EXIT_SUCCESS;

}

Cette fonction renvoie au système un entier (int) qui permet de savoir si le programme s'est déroulé correctement (par return EXIT_SUCCESS;) ou pas.

4.1.2 Principe général

La première chose effectuée est l'ouverture du fichier exemple.txt et sa mise à disposition au programme sous la forme de l'objet source de type FILE*.

23

Cet objet source est ensuite envoyé à la fonction Jordan. Cette fonction renvoie le tableau des effectifs de chaque lettre. Il s'agit du tableau d'entiers (de type long) nommé eff.

À partir du tableau eff, on crée l'arbre dans la fonction creer_arbre. Ainsi cette fonction renvoie un arbre (de type tree*) nommé arbre. On l'affiche (fonction afficher_arbre).

L'étape suivante consiste à calculer le taux de compression et à l'afficher. Pour cela on utilise la fonction taille (qui utilise comme paramètre l'arbre arbre) et qui permet d'obtenir le poids du fichier final. On utilise également ma fonction ftell qui utilise l'objet source et qui permet d'obtenir le poids du fichier initial.

En dernier lieu, on ferme l'objet source qui correspond au fichier à compresser et on renvoie au système EXIT_SUCCESS.

4.2 Lecture du fichier initial

4.2.1 Tableau des effectifs de chaque caractère

La première chose à faire est de lire le fichier à compresser de façon à déterminer l'effectif associé à chaque caractère.

C'est ce que fait la fonction Jordan : à partir du FILE* nommé source, elle renvoie un tableau de MAX = 256 entiers nommé eff.

Voici le listing de la fonction Jordan :

long* Jordan(FILE* source) {

long* eff = malloc(MAX * sizeof(long));char c;uchar u;long i;

for (i=0; i < MAX; eff[i++]=0);

if (source == NULL) printf("fichier source introuvable\n");else {

while(( c= fgetc(source) ) != EOF) eff [u = c]++;}return eff;

}

Cette fonction crée le tableau eff qui contient 256 entiers de type long numérotés de 0 à 255. Ce tableau est dans un premier temps initialisé : pour tout entier i plus petit que MAX, toutes les cellules du tableau sont mises à 0.

Si aucun fichier n’est trouvé, on imprime "fichier source introuvable\n"(le caractère \n est un caractère spécial : il s'agit du retour à la ligne).

24

Sinon, tant que le caractère lu dans le fichier est différent du caractère de fin de fichier (caractère EOF), on ajoute 1 à la valeur située dans le tableau eff dont l'indice u représente le caractère c.

4.2.2 Lecture du tableau des effectifs

Pour vérifier le bon fonctionnement de la fonction Jordan, il nous a été utile d'imprimer le tableau eff obtenu. C'est ce que fait la fonction afficher_eff dont voici le listing :

void afficher_eff(long* eff){

long i

for (i = 0; i < MAX; i++) {if   (eff[i]   !=   0)   printf   ("caratere   %c,   \t   code   %ld,   \t 

effectif %ld\n",i,i,eff[i]);}

}

Pour un entier i plus petit que MAX, toutes les cases du tableau sont lues. Si la case lue correspond à un effectif non nul alors on imprime "caratere   %c,   \t   code   %ld,   \t   effectif %ld\n",i,i,eff[i], c'est-à-dire qu'on imprime le caractère (par exemple A, puis son codage sous DOS, par exemple 65, et enfin l'effectif correspond dans le fichier à compresser).

4.3 Construction de l'arbre

4.3.1 Obtention de deux minimums

Une des première fonctions que nous avons du programmer est la fonction Thomas qui à partir du tableau d'entiers t dont la longueur taille est passée en paramètre, permet d'obtenir les deux minima (strictement positifs) contenus dans le tableau t. Cette fonction renvoie un tableau nommé resultat constitué de deux entiers qui sont les 2 minima recherchés. Voici le listing de cette fonction :

long* Thomas(long* t, long taille){

long* resultat = malloc(2*sizeof(long)); long i, i1 = 0, i2 = 0, min1, min2;

for (i = 0; i < taille; i++) {if (t[i] > 0) break;}min1 = t[resultat[0] = i]; // min1 est le premier entier non nul du 

tableau

25

for (i = 0; i < taille; i++) {if (t[i] > 0 && t[i] < min1) min1 = t[resultat[0] = i];}

for (i = 0; i < taille; i++) {if (t[i] > 0 && i != resultat[0]) break;}min2 = t[resultat[1] = i]; // min2 est le second entier non nul du 

tableau

for (i = 0; i < taille; i++) {if (i == resultat[0]) continue;if (t[i] > 0 && t[i] < min2) min2 = t[resultat[1] = i];

}

return resultat;}

Elle crée une boucle pour trouver le premier entier positif non nul dans le tableau t, car si t[i] n'est pas strictement supérieur à 0, l'ordinateur lit la case suivante du tableau. Une fois qu'un indice i tel que t[i] est strictement positif est obtenu, on sort de la boucle par l'instruction break. On assigne alors à resultat[0] l'entier i obtenu et à min1 l'effectif correspondant.

L'analyse du tableau reprend : si la valeur de l'effectif d'indice i est strictement supérieure à 0 et inférieur à min1 alors min1 est remplacé par cet effectif et resultat[0] est remplacé par i.

Une troisième boucle est nécessaire pour déterminer un indice i tel que t[i] est strictement positif sans que i soit égal à resultat[0]. Dès qu'un tel i est obtenu, on sort de la boucle et on assigne à resultat[1] cet entier i et à min2 l'effectif correspondant.

Enfin la quatrième et dernière boucle permet de modifier min2 s'il ne correspond pas au second minimum : pour cela, pour un indice i distinct de resultat[0], on modifie min2 et resultat[1] si l'effectif lu est strictement positif est strictement inférieur à min2.

4.3.2 Nombre de caractères distincts

La fonction nbcarac compte le nombre de caractères différents dans le fichier en renvoyant un entier nommé resultat. Pour cela elle parcourt le tableau des effectifs eff entré en paramètre et ajoute 1 à resultat dès qu'un caractère est marqué comme présent dans le tableau des effectifs (c'est-à-dire dès que eff[i] est strictement supérieur à 0).

long nbcarac(long* eff){

long resultat = 0, i = 0;for (i = 0; i < MAX; i++) {

if (eff[i] > 0) resultat++;}return resultat;

}

26

4.3.3 Création de l'arbre

La fonction creer_arbre permet la construction de l'arbre. Cette fonction utilise le tableau des effectifs eff créé précédemment et renvoie un pointeur sur un arbre, c'est-à-dire un objet du type tree*. On utilise l'entier n qui est le nombre de caractère différents dans le fichier ainsi que tho qui est un tableau de deux entiers : ces deux entiers sont les deux indices où se trouvent les deux effectifs minimums recherchés dans le tableau tab qui contient la liste de tous les effectifs. Enfin, tableau_arbre est un tableau de 2n-1 nœuds. On utilisera ce tableau pour renvoyer l'adresse du dernier nœud qui sera le nœud racine.

Voici le listing de cette fonction :

tree* creer_arbre(long* eff){

long n = nbcarac(eff);long i = 0, j = 0, k = 0, min1, min2;long* tho = (long*) malloc( 2*sizeof(long));tree* tableau_arbre = (tree*) malloc((2*n­1)*sizeof(tree));long* tab = (long*) malloc( (2*n­1)*sizeof(long));

// I N I T I A L I S A T I O N    

for(i = 0; i < n; i++){for (j = k; j < MAX; j++) if (eff[j] != 0) break;k = j + 1;tableau_arbre[i].weight = eff[j];tableau_arbre[i].pos = 0;tableau_arbre[i].c = (uchar) j;tableau_arbre[i].left = tableau_arbre[i].right = NULL;}for(i = n; i < 2*n­1 ; i++){tableau_arbre[i].weight = tableau_arbre[i].pos = 0;tableau_arbre[i].c = 0;tableau_arbre[i].left = tableau_arbre[i].right = NULL;}

// C R E A T I O N    A R B R E

for (i = n; i < 2*n­1; i++) {for (j = 0; j < 2*n­1; j++) tab[j] = 

tableau_arbre[ j ].weight;tho = Thomas(tab,2*n­1);tableau_arbre[ i ].weight = 

tableau_arbre[ tho[0] ].weight+tableau_arbre[ tho[1] ].weight;tableau_arbre[ i ].left  = &(tableau_arbre[ tho[0] ]);tableau_arbre[ i ].right = &(tableau_arbre[ tho[1] ]); tableau_arbre[ tho[0] ].weight = 

­tableau_arbre[ tho[0] ].weight;tableau_arbre[ tho[1] ].weight = 

­tableau_arbre[ tho[1] ].weight;}

27

// R E E C R I T U R E   D E S   E F F E C T I F S   E N   P O S I T I F

for (j = 0; j < 2*n­1; j++) {if (tableau_arbre[ j ].weight < 0) tableau_arbre[ j ].weight = 

­tableau_arbre[ j ].weight;}

// E C R I T U R E   D E S   P O S I T I O N S   

completer_position( &( tableau_arbre[2*n­2] ) , 1);

return &( tableau_arbre[2*n­2] );}

Comme on le voit il y a plusieurs étapes dans cette fonction :

● Initialisation.● Création de l'arbre● Réécriture des effectifs en « positif ».● Écriture des positions.

Commençons par l'initialisation : il s'agit de remplir les n premières cellules (numérotées de 0 à n-1) de tableau_arbre par l'effectif de chaque caractère en assignant eff[j] à tableau_arbre[i].weight et le caractère présent dans le tableau (j) est assigné sous sa forme non signée à tableau_arbre[i].c. Dans l'initialisation les positions sont mises à 0 et les pointeurs mis à NULL.À partir de la case n, on met 0 comme caractère, comme effectif et comme position. De même tous les pointeurs sont mis à NULL.

Passons à la seconde étape : les n premières cellules étant complétées lors de l'initialisation, il reste à compléter les n-1 suivantes lors de la création de l'arbre. Pour cela on utilise un entier i qui va de n à 2n-2.A chaque passage dans cette boucle, le tableau tab est reconstruit (on verra que les n poids des caractères sont modifiés à chaque étape) .On détermine ensuite (par la fonction Thomas) les deux indices de tab où se trouvent les minima. Ces deux indices, tho[0] et tho[1] permettent d'affecter à la case i un poids qui est la somme des deux poids minimaux par la ligne suivante :

tableau_arbre[ i ].weight = tableau_arbre[ tho[0] ].weight+tableau_arbre[ tho[1] ].weight;

On affecte également les deux pointeurs aux cellules qui correspondent à tho[0] et tho[1].

Il reste ensuite à préciser que les cellules correspondantes à tho[0] et tho[1] ne doivent plus être prises en compte : pour cela on multiplie les effectifs correspondants par -1 (la fonction Thomas ne cherche que les minimums positifs). Par exemple pour la cellule correspondante à tho[0] :

tableau_arbre[ tho[0] ].weight = ­tableau_arbre[ tho[0] ].weight;

La troisième étape consiste à multiplier les effectifs négatifs par -1 de sorte qu'ils soient à nouveau tous positifs. Il suffit de faire varier un entier j de 0 à 2n-2 et de tester le signe de tableau_arbre[ j ].weight pour éventuellement le multiplier par -1.

28

La dernière étape consiste à écrire la position de chaque nœud : cela s'effectue dans une autre fonction, la fonction completer_position. Son fonctionnement est détaillé dans le paragraphe 4.4.1.

Enfin, on renvoie l'adresse de la dernière cellule du tableau tableau_arbre qui est l'adresse du nœud racine.

4.3.4 Affichage de l'arbre

Cette fonction utilise comme paramètre le pointeur arbre sur un arbre et ne renvoie aucune valeur. Elle sert à afficher à l'écran l'arbre en question. Pour cela, on affiche "A F F I C H A G E   A R B R E ", puis on appelle la fonction afficher_arbre_rec. Voici le listing de cette fonction :

void afficher_arbre(tree* arbre){

printf("A F F I C H A G E    A R B R E \n");afficher_arbre_rec(arbre);printf("\n");

}

La fonction afficher_arbre_rec commence par donner le numéro du nœud racine avec l'effectif correspondant. Dans la suite de la fonction on trouve le test suivant :

● si le pointeur de gauche et le pointeur de droite pointent sur NULL alors il affiche le caractère, car le nœud observé est en réalité une feuille

● si le pointeur de gauche ne pointe pas sur NULL alors elle recommence pour le pointeur de gauche (c'est-à-dire que tout se passe comme si le nouveau nœud racine était le nœud gauche).

● si le pointeur de droite ne pointe pas sur NULL alors elle recommence pour le pointeur de droite (c'est-à-dire que tout se passe comme si le nouveau nœud racine était le nœud droit).

Voici le listing de cette fonction :

void afficher_arbre_rec(tree* arbre){

printf("\n\nNoeud numero %ld.\nEffectif %ld\t",(*arbre).pos,(*arbre).weight);

if ((*arbre).left  == NULL && (*arbre).right  == NULL ) printf("Caractere %c",(*arbre).c);

if ( (*arbre).left  != NULL ) afficher_arbre_rec((*arbre).left);if ( (*arbre).right != NULL ) afficher_arbre_rec(arbre­>right);

}

4.4 Étage et position

29

4.4.1 Écriture des positions

La fonction completer_position écrit les positions des nœuds dans l’arbre. Elle prend en paramètre un entier i (qui correspond à la position de la racine, à savoir 1) et l'arbre à compléter. Voici le listing de cette fonction :

void completer_position(tree* arbre, long i){

(*arbre).pos = i;if ( (*arbre).left  != NULL ) completer_position(arbre­>left, 

2*i );if ( (*arbre).right != NULL ) completer_position(arbre­>right, 

2*i+1 );}

La première fois que la fonction est appelée, la position de la racine de l'arbre est égale à 1. Ensuite :● si le pointeur de gauche est différent de NULL alors la position suivante est doublée et elle est

affectée au nœud situé à gauche.● si le pointeur de droite est différent de NULL alors la position suivante est doublée et ajoutée à 1 et

elle est affectée au nœud situé à droite.

4.4.2 Calcul de l'étage en fonction de la position

Soit i la position d’un nœud dans l’arbre. La fonction etage nous permet de calculer l'étage p en fonction de i en utilisant les logarithmes. On y voit ainsi l'application du résultat trouvé dans la démonstration du paragraphe 3.1.2. :

p = E lniln 2

Dans le listing ci-dessous, log correspond à ln, floor à la fonction partie entière :

long etage(long i){

return ((long) floor( log(i)/log(2) ) );}

4.5 Calcul du taux de compression

4.5.1 Obtention de la taille du fichier compressé

30

Pour obtenir la taille du fichier compressé, on utilise la fonction taille qui utilise comme paramètre un pointeur sur un arbre et renvoie un entier. Cette fonction est très simple. Voici son listing :

long taille(tree* arbre){

return taille_rec(arbre,1);}

Comme on le voit tout se passe dans la fonction taille_rec qui fonctionne de la manière suivante : la première fois qu'elle est appelée, l'entier i est égal à 1 et on teste le nœud (initialement le nœud racine) pour savoir s'il s'agit d'une feuille. Si ce n'est pas le cas on calcule la somme de la taille correspondant à la branche gauche et à la branche droite grâce à :

taille_rec((*arbre).left, 2*i ) + taille_rec(arbre­>right, 2*i+1 )

Comme la branche gauche est affectée de 2*i et la branche droite de 2*i+1, à chaque appel de la fonction taille_rec, on donne la position du nœud. Dès que l'on est sur une feuille on calcule etage(i) (c'est-à-dire le nombre de bits nécessaires pour écrire le caractère correspondant à la feuille) multiplié par (*arbre).weight (c'est-à-dire le nombre de fois où le caractère est présent dans le fichier initial). Comme on a ajouté les différents tailles, on calcule bien le poids (en bits) du fichier final,

long taille_rec(tree* arbre, long i){

if ( (*arbre).left  != NULL || (*arbre).right != NULL) return(taille_rec((*arbre).left, 2*i ) + taille_rec(arbre­>right, 

2*i+1 ));if ( (*arbre).left  == NULL && (*arbre).right == NULL ) 

return((*arbre).weight * etage(i));}

4.5.2 Préambule d'un fichier compressé

En fait un fichier compressé doit contenir, en plus du codage brut (par exemple 0101101110011001011100110111001010111110010101110110001001), un préambule qui décrit pour chaque caractère le codage associé.

Si on reprend l'exemple recherchechatchatain on a :

Caractère Codage

r 010

e 110

c 111

h 00

a 101

31

t 011

i 1000

n 1001

Ce préambule doit donc contenir les huit caractères (un caractère pèse 8 bits) et tous les codages soit :

3+3+3+2+3+3+4+4 = 25 bits

Ainsi ce préambule contient au minimum 8×8 + 25 = 89 bits à ajouter aux 58 du codage brut. Bien entendu, cela modifie le taux obtenu. On peut penser que l'on obtiendrait un taux réel de :

taux decompression=8958160 =0,9187

4.6 Exemple

Utilisons notre programme pour tester la phrase recherchechatchatain. Comme on l'a vu précédemment, on utilise le fichier exemple :

Ce fichier contient 20 caractères, soit une taille initiale de 20 octets comme le confirme la copie d'écran suivante :

32

Lançons notre programme! On obtient alors :

33

On constate que les positions obtenues par notre programme sont bien les mêmes que celles obtenues au chapitre 1. Ainsi le taux de compression théorique est bien de 0,3625 comme annoncé!

34

Chapitre 5

Annexe

5.1 Fichier main.c

int main(int argc, char *argv[]){

FILE* source = fopen("exemple.txt", "r+");long* eff = Jordan(source);tree* arbre = creer_arbre(eff);afficher_arbre(arbre);printf("\n\nTaux de compression : %lf\n", ( ((double) 

taille(arbre)) / (8*ftell(source)) ) );fclose(source);system("PAUSE");return EXIT_SUCCESS;

}

5.2 Fichiers Jordan

5.2.1 Fichier Jordan.h

#ifndef _Jordan#define _Jordan

#define MAX 256

typedef unsigned char uchar;

long* Jordan(FILE*);

void affiche_eff(long*);

#endif

35

5.2.2 Fichier Jordan.c

#include <stdio.h>#include <stdlib.h>#include "Jordan.h"#include "Thomas.h"

long* Jordan(FILE* source) {

long* eff = malloc(MAX * sizeof(long));char c;uchar u;long i;

for (i=0; i < MAX; eff[i++]=0);

if (source == NULL) printf("fichier source introuvable\n");    else {while(( c= fgetc(source) ) != EOF) eff [u = c]++;}return eff;

}

void afficher_eff(long* eff){

long i;

for (i = 0; i < MAX; i++) {if (eff[i] != 0) printf ("caratere %c, \t code %ld, \t effectif 

%ld\n",i,i,eff[i]);}

}

5.3 Fichiers Thomas

5.3.1 Fichier Thomas.h

#ifndef _Thomas#define _Thomas

typedef struct tree {uchar c;long weight;long pos;struct tree *left, *right;

36

} tree;

long* Thomas(long*, long);

long nbcarac(long*);

#endif

5.3.2 Fichier Thomas.c

#include <stdio.h>#include <stdlib.h>#include "Jordan.h"#include "Thomas.h"

long* Thomas(long* t, long taille){

long* resultat = malloc(2*sizeof(long)); long i, i1 = 0, i2 = 0, min1, min2;

for (i = 0; i < taille; i++) {if (t[i] > 0) break;

}min1 = t[resultat[0] = i];           // min1 est le premier entier 

non nul du tableau

for (i = 0; i < taille; i++) {if (t[i] > 0 && t[i] < min1) min1 = t[resultat[0] = i];

}

for (i = 0; i < taille; i++) {if (t[i] > 0 && i != resultat[0]) break;

}min2 = t[resultat[1] = i];           // min2 est le second entier 

non nul du tableau

for (i = 0; i < taille; i++) {if (i == resultat[0]) continue;if (t[i] > 0 && t[i] < min2) min2 = t[resultat[1] = i];

}

return resultat;}

long nbcarac(long* eff){

long resultat = 0, i = 0;for (i = 0; i < MAX; i++) { 

if (eff[i] > 0) resultat++;}return resultat;

37

}

5.4 Fichiers creation_arbre

5.4.1 Fichier creation_arbre.h

#ifndef _creation_arbre#define _creation_arbre

tree* creer_arbre(long*);

void afficher_arbre(tree*);

void afficher_arbre_rec(tree*);

void completer_position(tree*, long);

long etage(long);

long taille(tree*);

long taille_rec(tree*, long);

#endif

5.4.2 Fichier creation_arbre.c

#include <stdio.h>#include <stdlib.h>#include "Jordan.h"#include "Thomas.h"#include "creation_arbre.h"#include <math.h>

tree* creer_arbre(long* eff){

long n = nbcarac(eff);long i = 0, j = 0, k = 0, min1, min2;long* tho = (long*) malloc( 2*sizeof(long));tree* tableau_arbre = (tree*) malloc((2*n­1)*sizeof(tree));long* tab = (long*) malloc( (2*n­1)*sizeof(long));

// I N I T I A L I S A T I O N    

for(i = 0; i < n; i++){

38

for (j = k; j < MAX; j++) if (eff[j] != 0) break;k = j + 1;tableau_arbre[i].weight = eff[j];tableau_arbre[i].pos = 0;tableau_arbre[i].c = (uchar) j;tableau_arbre[i].left = tableau_arbre[i].right = NULL;}for(i = n; i < 2*n­1 ; i++){

tableau_arbre[i].weight = tableau_arbre[i].pos = 0;tableau_arbre[i].c = 0;tableau_arbre[i].left = tableau_arbre[i].right = NULL;

}

// C R E A T I O N    A R B R E

for (i = n; i < 2*n­1; i++) {for (j = 0; j < 2*n­1; j++) tab[j] = 

tableau_arbre[ j ].weight;tho = Thomas(tab,2*n­1);tableau_arbre[ i ].weight = 

tableau_arbre[ tho[0] ].weight+tableau_arbre[ tho[1] ].weight;tableau_arbre[ i ].left  = &(tableau_arbre[ tho[0] ]);tableau_arbre[ i ].right = &(tableau_arbre[ tho[1] ]); tableau_arbre[ tho[0] ].weight = 

­tableau_arbre[ tho[0] ].weight;tableau_arbre[ tho[1] ].weight = 

­tableau_arbre[ tho[1] ].weight;   }

// R E E C R I T U R E   D E S   E F F E C T I F S   E N   P O S I T I F 

for (j = 0; j < 2*n­1; j++) {if (tableau_arbre[ j ].weight < 0) tableau_arbre[ j ].weight = 

­tableau_arbre[ j ].weight;}

// E C R I T U R E   D E S   P O S I T I O N S   

completer_position( &( tableau_arbre[2*n­2] ) , 1);

return &( tableau_arbre[2*n­2] );}

void completer_position(tree* arbre, long i){

(*arbre).pos = i;if ( (*arbre).left  != NULL ) completer_position(arbre­>left, 

2*i );if ( (*arbre).right != NULL ) completer_position(arbre­>right, 

2*i+1 );}

void afficher_arbre(tree* arbre){

printf("A F F I C H A G E    A R B R E \n");

39

afficher_arbre_rec(arbre);printf("\n");

}

void afficher_arbre_rec(tree* arbre){

printf("\n\nNoeud numero %ld.\nEffectif %ld\t",(*arbre).pos,(*arbre).weight);

if ((*arbre).left  == NULL && (*arbre).right  == NULL ) printf("Caractere %c\t code %ld",(*arbre).c,(*arbre).c);

if ( (*arbre).left  != NULL ) afficher_arbre_rec((*arbre).left);if ( (*arbre).right != NULL ) afficher_arbre_rec(arbre­>right);

}

long etage(long i){

return ((long) floor( log(i)/log(2) ) );}

long taille(tree* arbre){

return taille_rec(arbre,1);    }

long taille_rec(tree* arbre, long i){

if ( (*arbre).left  != NULL || (*arbre).right != NULL) return(taille_rec((*arbre).left, 2*i ) + taille_rec(arbre­>right, 

2*i+1 ));if ( (*arbre).left  == NULL && (*arbre).right  == NULL ) 

return((*arbre).weight * etage(i));}

40

Conclusion

L'atelier Math en Jeans nous a apporté certains avantages pour la suite de nos études et comme améliorations personnelles. Ainsi, nous avons développé notre esprit d'équipe dans ce travail, en nous répartissant les tâches équitablement et en s'entraidant. De plus, lors de notre voyage à Paris nous avons pu améliorer notre oral, grâce à la présentation de nos recherches devant un public et nous avons également progressé dans nos aptitudes de rédaction en rédigeant ce rapport.

On peut également noter que notre sujet nous a aidé pour nos cours de mathématiques grâce à l'apprentissage des arbres, que nous avons utilisé cette année dans le chapitre des probabilités. Il y a aussi les logarithmes qui nous seront utiles l'année prochaine.

Nous avons découvert la programmation qui fut dure à comprendre mais nous espérons que cela nous servira pour l'examen pratique de mathématique du baccalauréat.

41