Huffman : les prémices de la compression

Aujourd’hui, et comme je le fais très rarement, je vais vous parler du bahut et de ce qu’on a pu y faire.

Cette année, étant étudiant dans une école d’ingénieur et apprenant pour la première année le C, nous avons eut le droit à un petit projet en C – justement – à rendre pour fin mai. Par groupe de 3, on a pu travailler sur un sujet que l’on appelle “Maths-Info” puisqu’il traite des maths et…

Bref, j’avais choisi avec mon groupe, la compression Huffman. Sujet plus “info” que “maths”, ca sonnait plus intéressant.

En fait, Huffman est un est éminent professeur d’informatique qui a écrit une méthode pour réduire la place prise par n’importe quel fichier en créant un “arbre binaire”.

Explication du principe :

Bon pour faire, simple, vous prenez un fichier txt. Il est composé de centaines de caractère. Chaque caractère (char) prend 1 octet. Et bien nous allons attribuer à chaque caractère présent dans le texte un “code Huffman”. En fait, nous allons d’abords regarder le fichier et retenir les caractères utilisés : lettre de l’alphabet, chiffres, symboles… (tout ce qui peut être taper au clavier en fait). Pour chaque caractère nous allons compter son occurrence dans le texte. Pour n’importe quel texte francais, je peux vous dire que le ‘e’ ou le ‘a’ fera partie des plus présents. Ayant chacun leur occurence (a=>182 par ex), nous allons créer un arbre. Chaque feuille de cette arbre est un caractère et son occurence (utilisation de structures dans le programme). Nous allons relier les 2 feuilles dont l’occurence est la plus faible et créer un arbre père dont le caractère représentatif sera quelconque et dont l’occurence sera l’addition de ces deux fils. On le range de nouveau dans le groupe de feuille présent et on recommence récursivement jusqu’a ce qu’il reste qu’un père, la racine de l’arbre :

Ensuite, on va attribuer un code à chaque lettre se trouvant tout en bas de l’arbre. On attribue 0 a gauche et 1 à droite et on descend. Ce qui donnera, par ex, à la lettre a : 010 (pour le cas de l’arbre ci-dessus). Ensuite vient une partie assez compliqué du code, il faut créer un fichier (qui sera le fichier compressé) contenant l’arbre (utile pour la décompression) et le code. En fait on écrit d’abords l’arbre en en-tête du fichier archive, puis on lit le fichier texte source caractère par caractère et on écrit le code correspondant. Cependant on ne l’écrit pas comme ca, il faut écrire octet par octet pour gagner de la place, donc on va faire un buffer de 8 bits et on va rentrer les codes huffman dedans, des qu’on atteint les 8 bits (1 octet) on écrit dans le fichier.

Bref, pour la décompression, il faut lire l’en-tête pour recréer l’arbre et lire octet par octet de la gauche vers la droite et descendre petit à petit en fonction des 0 et 1, dans l’arbre afin de tomber sur la lettre.

Pas très simple à comprendre comme ca, mais ce n’est pas une technique si compliquée en fait. C’est d’ailleurs vraiment très bien pensé car il n’y aucune chance de ne pas compressé.

Huffman est utilisé dans quasi tous les algorithmes de compression (zip, rar, jpeg) en tant que 2e compression (je ne connais pas les autres).

Intéressant en tout cas, malheureusement notre code compressait, mais ce n’était pas encore ca pour la décompression.

Je mettrais rapidement le code sur internet, si ca intéresse certains pour des projets, pour s’entrainer, pour apprendre… Par contre, je le mettrais tel quel.

Advertisements

6 thoughts on “Huffman : les prémices de la compression”

  1. Bonne petite explication 🙂 Je viens justement de passer un partiel la dessus ^^ (Et c’était mon dernier partiel, alors maintenant, reprise des activités bloguesques 🙂 )

    Like

  2. Pour les autres compressions il existe le Z777 (qui couplé avec Huffman forme le deflate, l’algo des zips), ou le RLE, qui est de loin le plus simpl(ist?)e des algos de compression.

    A part ça si tu n’oses pas divulguer ton code sur le net demande le notre, il fut jugé “d’une grande qualité” et il compresse et décompresse lui! (avec les optimisations qui vont bien)
    :mrgreen:
    Voila c’était juste pour que t’oublies pas qu’on est les meilleurs 😆

    Like

  3. ah, vas-y fait ton malin Henri ! (j’ai eut 14 en info… quand meme ^^)
    je mettrais mon code apres un petit nettoyage, d’ailleurs je le mettrais la semaine prochaine, mais t’a qu’a m’envoyer le tien, je le mettrais aussi

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s