Codage de Huffman

1 Présentation de l’algorithme de Huffman

1.1            Un système de codage répandu

La compression de données informatiques consiste à réduire la taille de l'information pour le stockage de cette information et son transport.

• Les données informatiques qui doivent rester identiques à leur original (textes, programmes informatiques, …) utilisent la compression sans perte (RLE, LZW, Huffman).
• Les données dont la qualité se limite aux perceptions humaines (images, vidéos, sons, …) utilisent la compression avec pertes (JPEG, ondelettes, fractales, MPEG, …).

• But : réduire le nombres de bits utilisés pour le codage des caractères fréquents dans un texte et d’augmenter ce nombre pour des caractères plus rares.

Cet algorithme permet de compresser aussi bien des images que des textes, on parle de compression statistique ou codage entropique (probabilités d’apparition d’un caractère). On obtient une compression satisfaisante (50% en moyenne) et un temps de compression assez rapide. En revanche il faut transmettre la bibliothèque en même temps, et il arrive que la taille du fichier soit plus grande que celle du fichier non compressé. De plus il est très sensible à la perte d’un bit, toutes les valeurs qui suivront ce bit seront fausses lors de la décompression.

1.2 Utilisation de la répétition des caractères, l’entropie

Le codage de Huffman est un codage entropique qui a la propriété d'être optimal car il donne la plus petite moyenne de longueur de code de toutes les techniques de codage statistique. De plus, il est instantané ce qui signifie qu'aucun code n'est le préfixe d'un autre. Cette propriété s'assure de l'unicité de décodage de chaque code.

Le codage entropique exploite les propriétés statistiques des coefficients quantifiés pour diminuer le débit de transmission en utilisant des mots courts pour représenter les évènements les plus probables et des mots plus longs pour les occurrences rares.

L'information moyenne apportée par symbole est par définition l' entropie :

L'entropie caractérise la source S. Son unité est le bit/symbole.

Ses principales propriétés sont les suivantes :

·        résulte directement de la définition.

• Pour une source de K symboles,.

·        La limite est obtenue pour une source équiprobable de symboles :

En clair : plus un caractère est présent, plus sa représentation binaire est courte. Petit rappel, un caractère est généralement représenté par 7 ou 8 bits. Le codage de Huffman modifie cette représentation et l'adapte au mieux en fonction du fichier à compresser.

1.3        L’arbre de Huffman(d’un tableau d’occurrence à l’élaboration de l’arbre)

L’algorithme d’Huffman date de 1952 et a été inventé par D.A. Huffman Les symboles sont tout d'abord classés dans l'ordre décroissant de probabilité d'occurrence. L'algorithme couple ensuite le symbole de plus faible probabilité avec le symbole ou le couple de symboles voisins. Les symboles sont de nouveaux reclassés dans l'ordre de probabilité d'occurrence décroissant et l'algorithme continue jusqu'à l'obtention d'une probabilité totale unitaire.

1. faire la liste des symboles et les trier par probabilité décroissante ; ces symboles constituent les nœuds d'origine de l'arbre de Huffman
2. prendre les deux nœuds de plus faible probabilité, les combiner en un nœud dont la probabilité est égale à la somme des deux probabilités et marquer les noeuds fusionnés par 0 pour le premier et 1 pour le second (par ordre de probabilités décroissantes)
3. répéter l'étape 2 jusqu'à ce qu'il ne reste qu'un seul nœud (de probabilité 1) qui devient la racine de l'arbre binaire ainsi constitué
4. relire chaque mot de code depuis la racine pour déterminer sa valeur

Création de l’arbre

Ceci définit une injection de l'ensemble des feuilles de l'arbre dans l'ensemble des séquences binaires.

2     L’algorithme

2.1  Lecture du fichier et création d’un tableau recensant les occurrences des lettres

D'abord, on lit entièrement le fichier à compresser. On construit en parallèle une table d'occurrence pour chaque caractère. Au début de la lecture, toutes les occurrences sont nulles. Si, par exemple le premier caractère lu est un " S ", son occurrence devient 1, s'il réapparaît, elle devient 2, etc.; et ce pour tous les caractères du fichier. A la fin de la lecture du fichier, on sait combien de fois chaque caractère a été répété.

Il faut en suite bien sûr réorganiser cette table afin qu'elle soit utilisable. On doit la classer dans un ordre décroissant. Pour cela, on peut utiliser un deuxième tableau dont la première cellule contiendra le caractère le plus utilisé, la deuxième le second, etc.... :

                                                      table d'occurrence

2.2  Création de l’arbre

On construit ensuite ce que l'on appelle l'arbre de Huffman. Dans la table d'occurrence, on prend les deux derniers caractères et on les rassemble pour en faire un nœud. On somme l'occurrence de ces deux caractères et on obtient l'occurrence de ce nœud. On peut ainsi le repositionner dans la table comme un caractère normal. On recommence en prenant les 2 derniers caractères de la table. On les rassemble pour en faire un nœud qu'on replace, etc.…Au bout de quelques itérations, un des deux derniers caractères de la table sera un autre nœud. Peu importe, on le considère comme un caractère normal. C'est ainsi que l'on obtient toutes les ramifications, et au final l'arbre complet, lorsqu'il ne reste plus qu'un seul nœud dans la table.

2.3  Ensuite on parcourt l’arbre pour coder les lettres

Pour déterminer le code de Huffman de chaque lettres, c’est à dire la séquence binaire qui substituera le code ASCII, on parcourt tout l’arbre et à chaque lettre on lui attribue son chemin. On peut remarquer que de cette manière on a pas besoin de dire quand la séquence binaire d’une lettre est terminée parce qu’il est impossible de descendre plus en aval de l’arbre lorsqu’on est arrivé à une feuille.

Bijection entre le code et les feuilles dans un cas simple

2.4  Ecriture du fichier codé.

Il se décompose en deux parties. D’abord une entête qui rassemble le dictionnaire et toutes les informations utiles à la décompression. Il est suivit de la suite de bits composé de séquences binaires

2.5  Décompression

La décompression permet l’utilisation directe de l’arbre de Huffman. En effet il est nettement plus rapide de parcourir l’arbre en partant de la racine que depuis les feuilles. D’abord on réceptionne la clé de codage afin d’élaborer l’arbre. Ensuite, on réceptionne bit par bit le code compressé, et on recherche dans l’arbre si ça correspond à une séquence binaire. Si tel est le cas on écrit le caractère reconnu et ainsi de suite. 

3 La source

3.1 Présentation générale du code source

3.1.1 Codage du lancement du programme : la fonction main() de principal.c

            Le fonctionnement général du programme est optimisé pour une utilisation réelle, on s’est inspiré des commandes sous console unix. On appelle le programme par huff et on choisit de compresser (resp décompresser) grâce au paramètre comp (resp uncomp) suivit du fichier en question.

            Tout ceci est relativement simple et rien ne vaut une lecture du main() du fichier principal.c où l’on reconnaît les deux fonctions (à effets de bord pur) compression et decompression.

3.1.2        La répartition de la source organisée par le fichier d’en tête

            Par soucie de lisibilité du code, la source se décompose en plusieurs fichiers. Les programmes compression et de décompressions sont mis dans des fichiers du même nom et l’ensemble des autres fonctions sont réparties dans les autres.

Toutes les fonctions, les structures et les nouveaux types de données sont définis dans un fichier d’en tête appelé bibliotheque.h. On arrive au final à :

3.2 Le compresseur

3.2.1 Réception du fichier à compresser

            On place le fichier à compresser dans un tableau buffer[] après avoir compter le nombre de caractère qu’il contient.

            Le code ASCII comporte 256 caractères donc on créé deux tableaux de 257 éléments dont les cases sont couplées par le même indice. Le tableau dejavu[] dont les caractères sont initialement à NULL réceptionne les différents caractères par ordre d’apparition et le tableau occurrence comptabilise le nombre de fois où ils apparaissent. Si la nouvelle lettre considérée est déjà apparue, on incrémente occurrence, sinon on crée une nouvelle lettre dont l’occurrence est mise à 1. Ainsi on élimine toutes les cases en trop (occurrence[i]==0) et on peut alors remplir tout ce dont on a besoin pour effectuer l’algorithme d’Huffman. On s’empressera alors de libérer la mémoire occupée par ces tableaux devenus inutiles.

3.2.2 Initialisation de tous les objets pour créer l’arbre et le codage

            La figure suivante résume tout ce que l’on créé lorsque l’on remplit les deux tableaux en invoquant la méthode tabcodage = remplissage (tabcodage, tabtravail, nbcar); qui elle même utilise toutes les fonctions de ajout_case. Tout ceci n’est que de l’initialisation alors rien ne vaut mieux qu’un coup d’œil au code.

3.2.3 Elaboration physique de l’arbre

            On procède par fusion successive jusqu'à ce qu’il ne reste qu’un seul nœud dans le tableau tabcodage[]. La fonction utilisée est CaracterePtr  fusion (CaracterePtr * tabtravail, int place). Cette opération créé un nouveau nœud, additionne les occurrences et relie ce nœud (père) aux deux nœuds fils. A chaque fusion effectuée on doit replacer le nouveau nœud dans le tableau, grâce à la fonction de tri optimisé CaracterePtr * tri_tab (CaracterePtr * tabtravail, int place),  et ceci jusqu’à la racine que nous initialiseront à la fin par racine=tabcodage[0] ; On a accès aux feuilles et au nœud par un tableau pour nous permettre de jouer sur les poids.

3.2.4 Codage des lettres

            Pour coder les lettres, il y a bien des façons de le faire. On les avait d’abord codée en même tant que nous faisions le fusions des nœuds, mais finalement on a codé les lettres selon le principe suivant.

            Le principe général est de parcourir l’arbre de la feuille extrême gauche à celle de droite. A chaque fois que l’on rencontre une feuille, on écrit dans tabcodage[] le code correspondant. Ensuite on remonte dan l’arbre (grâce aux adresses des nœuds contenues dans tabarbre[] ), on tourne à droite dans le premier nœud rencontré où l’on avait tourné à gauche et on redescend toujours le plus à gauche possible.

3.2.5 Ecriture du fichier codé

            Le fichier .huff commence par une entête nécessaire à la décompression. L’entête nous fournit d’abord le nombre de caractères différent mais surtout le moyen de recréer l’arbre avec facilité. Pour ceci nous avons utilisé un format très malin dans le but de limiter la place de cette partie.

         Ensuite nous écrivons le code sous un format binaire de chaque lettres, les uns après les autres.

3.3 Décompresseur

3.3.1 Réception de l’entête et élaboration de l’arbre

            La décompression se fait grâce à la fonction void decompression (BitFilePtr bfp, char *name_file); qui utilise la structure suivante pour effectuer l’algorithme de decompression.

3.3.2 Décodage

Le principe général du décodage est très simple. On prend la suite de bits par octet que l’on met dans un tableau tampon. Ensuite, pour chaque séquence binaire on cherche dans l’arbre si le code correspond à une feuille. Si tel est les cas, on écrit ce caractère, sinon on lit la séquence avec un bit de plus et on fait la même opération et ainsi de suite. On aurait pu chercher dans un tableau si la séquence binaire est celle d’une lettre, mais la cherche dans l’arbre à partir de la racine est nettement plus rapide.