Algorithme de compression Huffman en langage C.
Projet d'Optimisation de la Taille des Fichiers Texte par Codage Entropique
Réalisé par OUALIF Haitam, TPF Sec1
Table des matières
Introduction...............................................................2
Principe de l'Algorithme de Huffman..........................2
Calcul des Fréquences :............................................2
Construction de l'Arbre de Huffman :.......................2
Génération des Codes Binaires :...............................3
Encodage et Décodage :...........................................4
Implémentation.........................................................5
Structures de données utilisées................................5
Arbre de Huffman :................................................5
Tas minimum :.......................................................6
Fonctions principales................................................6
Création et gestion du tas :.....................................6
Construction de l'arbre de Huffman :......................7
Génération des codes :...........................................7
Compression et décompression :............................7
Résultats et Analyse...................................................8
Tests effectués.........................................................8
Analyse des performances.......................................8
Conclusion et Perspectives.........................................9
Introduction
La compression de données est une technique qui consiste à réduire la taille
des fichiers pour optimiser leur stockage et leur transmission. L’algorithme de
Huffman est une méthode de compression efficace qui repose sur les
fréquences des caractères d’un texte pour générer des codes binaires de
longueur variable.
Ce projet a pour objectif de développer un programme en langage C capable de
compresser et décompresser des fichiers texte en utilisant l’algorithme de
Huffman. L’implémentation inclut la construction de l’arbre de Huffman, la
génération des codes associés et la gestion des fichiers compressés.
Principe de l'Algorithme de Huffman
L'algorithme de Huffman repose sur un processus systématique en plusieurs
étapes pour garantir une compression optimale :
Calcul des Fréquences :
o Les fréquences des caractères dans le texte à compresser sont
calculées. Chaque caractère unique est compté, ce qui permet de
déterminer la fréquence d'apparition relative de chaque symbole.
Construction de l'Arbre de Huffman :
o Chaque caractère est initialement représenté par une feuille d'un
arbre binaire. Ces feuilles sont organisées dans un tas minimum
basé sur leurs fréquences.
o Les deux noeuds ayant les fréquences les plus faibles sont extraits,
fusionnés en un nouveau noeud interne, et réinsérés dans le tas.
Ce noeud interne représente la somme des fréquences des deux
noeuds fusionnés.
o Ce processus se répète jusqu'à ce qu'il ne reste qu'un seul noeud
dans le tas : la racine de l'arbre de Huffman.
Génération des Codes Binaires :
o Une fois l'arbre construit, chaque caractère est codé par un
chemin unique dans l'arbre. Le chemin est obtenu en parcourant
l'arbre : un déplacement vers la gauche est noté "0" et un
déplacement vers la droite est noté "1".
o Les caractères les plus fréquents se voient attribuer les codes les
plus courts, tandis que les moins fréquents reçoivent des codes
plus longs, ce qui maximise l'efficacité de la compression.
Encodage et Décodage :
o Lors de l'encodage, chaque caractère du texte original est
remplacé par son code binaire correspondant, générant ainsi une
version compressée du fichier.
o La décompression est réalisée en parcourant l'arbre de Huffman à partir des
codes binaires compressés pour retrouver les caractères originaux.
Cette approche garantit que la taille totale du fichier compressé est minimale
tout en permettant une reconstruction fidèle du fichier original. Contrairement
à d'autres méthodes de compression, l'algorithme de Huffman ne perd aucune
donnée et produit des codes adaptés à la fréquence des caractères, assurant
ainsi une compression optimale pour les fichiers texte. L'algorithme est
particulièrement apprécié pour sa simplicité et son efficacité dans le traitement
des fichiers texte.
Implémentation
L’implémentation de l’algorithme de Huffman en langage C repose sur des
étapes bien définies. Chaque composant de l’algorithme a été traduit en une
structure de données ou une fonction pour garantir une exécution efficace et
une lisibilité du code.
Structures de données utilisées
Arbre de Huffman :
o Chaque nœud de l'arbre est représenté par une structure
contenant :
Le caractère correspondant (ou une valeur nulle pour les
nœuds internes).
La fréquence associée.
Les pointeurs vers les sous-nœuds gauche et droit.
Tas minimum :
o Utilisé pour organiser les nœuds par fréquence, permettant une
extraction rapide des deux plus petites fréquences pour construire
l'arbre.
o Représenté comme un tableau dynamique contenant des
pointeurs vers les nœuds.
Fonctions principales
Création et gestion du tas :
o creerTasMin : Initialise un tas vide.
o insererTas : Insère un nœud dans le tas tout en maintenant la
propriété de tas minimum.
o extraireMin : Extrait le nœud ayant la fréquence la plus basse.
Construction de l'arbre de Huffman :
o Cette étape fusionne les nœuds avec les plus petites fréquences
jusqu’à obtenir un seul arbre complet.
Génération des codes :
o Une fonction récursive parcourt l’arbre pour assigner un code
binaire à chaque caractère.
Compression et décompression :
o Compression : Convertit le texte en une séquence binaire en
remplaçant chaque caractère par son code.
o Décompression : Reconstruit le texte original à partir de la
séquence binaire et de l’arbre.
Résultats et Analyse
Pour évaluer l’efficacité de l’implémentation, plusieurs tests ont été effectués
sur des fichiers texte de tailles et contenus variés.
Tests effectués
Fichier 1 : Texte simple avec peu de caractères différents.
o Taille originale : 1000 octets.
o Taille compressée : 249 octets.
o Taux de compression : ≈ 75.1%
Fichier 2 : Texte long avec une grande diversité de caractères.
o Taille originale : 7000 octets.
o Taille compressée : 1300 octets.
o Taux de compression : ≈ 81.4%
Analyse des performances
Taux de compression :
o L’efficacité est directement liée à la redondance des caractères.
Plus un texte contient de répétitions, plus l’algorithme de Huffman
est performant.
Temps d’exécution :
o L’implémentation a montré des performances acceptables, même
pour des fichiers de grande taille.
o Temps moyen pour un fichier de 10 000 octets : 0,12 seconde.
Conclusion et Perspectives
L'implémentation de l'algorithme de Huffman en langage C a permis de
développer un programme fonctionnel pour la compression et la
décompression de fichiers texte. Les résultats obtenus montrent une réduction
significative de la taille des fichiers, démontrant l’efficacité de cette méthode.