Code source programme de Huffman en langage C

La théorie est maintenant terminée, on va passer aux choses sérieuses. Tous les concepts de la compression de données grâce à l’algorithme ont été définis et expliqués dans l’étude. L’ensemble des fonctions a été assemblé dans le programme final.

Le programme a été développé en 2005 sur Windows XP, il a été modifié en 2013 pour pouvoir s’exécuter correctement sur Windows 7. Les 4 options du programme fonctionnent, l’enchainement de la compression et de la décompression d’un fichier ou d’un répertoire produit un fichier strictement identique au fichier initial.

Lors de la remise à niveau de 2013, j’ai constaté que ce programme qui m’avait semblé parfait à l’époque, pouvait encore être bien amélioré.

Voici quelques une des améliorations possibles :

  • Ajouter un paramètre pour produire les fichiers statistiques. Actuellement les fichiers sont générés à chaque lancement.
  • Supprimer les fichiers intermédiaires une fois la compression terminée.
  • Remplacer les chemins vers les répertoires de travail qui sont écrits directement en dur dans le code source.
  • Toute autre correction qui vous semblera pertinente.

Ou encore mieux des évolutions qui pourraient permettraient presque d’avoir un programme qui ressemble à un vrai :

  • Gérer l’arborescence lors de la compression d’un répertoire
  • Ajouter une interface graphique

Vous pouvez utiliser les commentaires en bas de la page pour soumettre vos modifications, je me ferais un plaisir de les intégrer dans une nouvelle version.

L’en-tête huffman.h contenant les déclarations des fonctions et des structures est disponible ICI.

/* Programme WinHuff – Code source : huffman.c */
/* Projet informatique Ecole d’ingénieurs – Langage C */
 
/* Nicolas – Nicolas */
/* Compression / Décompression de données par l’algorithme de Huffman statique */
/* Version finale – Compresse et décompresse fichiers et répertoires */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <windows.h>
#include "huffman.h" /* Header relatif à ce projet */
 
int main (void)
{
  /* Déclaration des variables */
  int choix; /* Choix de l’utilisateur */
 
  /* Initialisation */
  system("cls"); /* Effacement de l’écran avant de commencer */
  printf("Projet de C – Algorithme de Huffman – Nicolas / Nicolas\n\n");
 
  do {
    choix=menu();
  } while(choix!=5); /* Possibilité de faire plusieurs archives sans relancer le programme */
 
  return EXIT_SUCCESS;
}
 
/*—————————– MENU ———————————*/
int menu (void)
{
  char choix[10];
  int choixnum;
 
  /* Affichage du menu */
  printf(
  "\n"
  "——————————————————————-\n"
  "| Appuyer le numéro correspondant à ce que vous voulez faire : |\n"
  "——————————————————————-\n"
  "| 1 – Compresser un fichier selon la technique de Huffman |\n"
  "| 2 – Decompresser un fichier obtenu par (1) |\n"
  "| 3 – Compresser l’ensemble d’un repertoire |\n"
  "| 4 – Decompresser une archive obtenue par (3) |\n"
  "| 5 – Quitter le programme |\n"
  "——————————————————————-");
  printf("\nChoix : ");
  scanf("%s",choix); /* Saisie du choix au format texte pour tester la validité */
  choixnum = atoi(choix); /*Conversion de la chaine en entier pour les tests */
 
  /* Choix de l’utilisateur */
  switch(choixnum){
  case 1 :
    compression(choixnum);
    printf("Compression du fichier terminée.\n");
    break;
  case 2 :
    decompression(choixnum);
    printf("Décompression du fichier terminée.\n");
    break;
  case 3 :
    compression(choixnum);
    printf("Compression du répertoire terminée.\n");
    break;
  case 4 :
    decompression(choixnum);
    printf("Decompression du répertoire terminée.\n");
    break;
  case 5 :
    printf("\nAu revoir et à bientot\n");
    break;
    default :
    printf("\nLe numéro entré ne figure pas dans la liste. Veuillez le ressaisir.\n");
    break;
  }
  return choixnum;
}
 
/*————————– Compression ———————-*/
void compression(int choix)
{
  /*Déclaration des variables */
  char nomfich[100]; /* Nom du fichier à compresser */
  char nomrep[100]; /* Nom du répertoire à compresser */
  unsigned int carac[MAX]={0}; /* Tableau de 256 élements pour stocker les occurences */
  struct arbre_huff *arbre;
  struct dictionaire dico[MAX]={0,0}; /* Correspondance caractère <-> code */
  unsigned int taille_fich=0; /* Taille du fichier à compresser */
  unsigned short int nbfich=0; /* Nombre de fichiers dans le repertoire */
  short int mark=0; /* 0 si l’archive existe pas, 1 sinon */
  WIN32_FIND_DATA File; /* Pour la gestion du répertoire */
  HANDLE hSearch;
 
  if(choix==1) {
    printf("\nEntrez le nom du fichier à compresser : ");
    fflush(stdin); /* Vidage du buffer de l’entrée standard */
    gets(nomfich);
 
    copier_fichier(nomfich); /* Déplacement du fichier dans un répertoire temporaire */
    compter_occ(carac,nomfich); /* Analyse du fichier et création du fichier frequence.dat */
    creer_freq(carac,nomfich); /* Enregistrement dans le fichier frequence.dat */
    arbre=creer_arbre(carac); /* Création de l’arbre binaire */
    creer_code(arbre,0,0,dico); /* Parcours de l’arbre afin d’atribuer le codage de huffman à chaque caractère */
    ecrire_codage(dico,nomfich); /* Création du fichier codage.dat */
    taille_fich=encodage(dico,nomfich); /* Compression fichier */
    ecrire_fichier(carac,nomfich,0,taille_fich,mark); /* Création de l’archive */
    suppr_arbre(&arbre); /* Libération de l’espace occupé par arbre */
  }
 
  if(choix==3) {
    printf("\nEntrez le nom du répertoire à compresser (sans le \\ a la fin) : ");
    fflush(stdin);
    gets(nomrep);
    strcpy(nomfich,nomrep);
    strcat(nomfich,"\\*");
 
    /* Récupération de chaque fichier */
    if((hSearch=FindFirstFile(nomfich,&File))==INVALID_HANDLE_VALUE) {
      perror("Le répertoire n’existe pas ou il ne contient aucun fichier : ");
      exit(EXIT_FAILURE);
    }
    do{
      /* On verifie qu’il s’agit d’un fichier et pas d’un répertoire */
      if(File.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
      continue;
      nbfich++; /* On compte le nombre de fichiers dans le répertoire */
      strcpy(nomfich,nomrep);
      strcat(nomfich,"\\");
      strcat(nomfich,File.cFileName); /* Fabrication du nom du fichier */
      compter_occ(carac,nomfich); /* Comptage des occurences */
      creer_freq(carac,nomrep); /* Enregistrement dans le fichier frequence.dat */
      arbre=creer_arbre(carac); /* Création de l’arbre binaire */
      creer_code(arbre,0,0,dico); /* Parcours de l’arbre afin d’atribuer le codage de huffman à chaque caractère */
      ecrire_codage(dico,nomrep); /* Création du fichier codage.dat */
    }while(FindNextFile(hSearch,&File)); /* Tant qu’il reste des fichiers dans le répertoire */
 
    strcpy(nomfich,nomrep);
    strcat(nomfich,"\\*");
    if((hSearch=FindFirstFile(nomfich,&File))==INVALID_HANDLE_VALUE) {
      perror("Le répertoire n’existe pas ou il ne contient aucun fichier : ");
      exit(EXIT_FAILURE);
    }
    /* Compression des fichiers les uns à la suite des autres */
    do{
      /* On verifie qu’il s’agit d’un fichier et pas d’un répertoire */
      if(File.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
      continue;
      strcpy(nomfich,nomrep);
      strcat(nomfich,"\\");
      strcat(nomfich,File.cFileName); /* Fabrication du nom du fichier */
      printf("Ajout de %s à l’archive…\n",nomfich);
      taille_fich=encodage(dico,nomfich);
      ecrire_fichier(carac,nomfich,nbfich,taille_fich,mark);
      mark=1;
    }while(FindNextFile(hSearch,&File)); /* Tant qu’il reste des fichiers dans le répertoire */
    suppr_arbre(&arbre); /* Libération de l’espace occupé par l’arbre */
    CloseHandle(hSearch);
  }
}
 
/*——————————–Décompression———————————*/
void decompression(int choix)
{
  char nom_archive[100]; /* Nom de l’archive */
  unsigned int carac[MAX]={0};
  struct arbre_huff *arbre;
  unsigned int taille_fich=0;
  int taille;
  struct dictionaire dico[MAX]={0,0}; /* Correspondance caractère <-> Huffman */
  short int nbfich; /* Nombre de fichiers dans l’archive */
 
  if(choix==2) /* Si l’archive contient un seul fichier */
  {
    printf("\nEntrez le nom du fichier à decompresser : ");
    fflush(stdin);
    gets(nom_archive);
 
    /* On récupère les données nécessaires pour construire l’arbre */
    taille=lire_index(carac,nom_archive,choix,&nbfich,1);
    arbre=creer_arbre(carac); /* Création de l’arbre de Huffman */
    creer_code(arbre,0,0,dico); /* Association symbole <-> caractères */
 
    /* Decodage */
    extraire_nom(nom_archive,arbre,choix,taille,taille_fich,0);
  }
 
  /* Décompression d’un répertoire */
  if(choix==4)
  {
    printf("Entrez le nom du répertoire à décompresser : ");
    fflush(stdin);
    gets(nom_archive);
 
    taille=lire_index(carac,nom_archive,choix,&nbfich,1);
    arbre=creer_arbre(carac);
    creer_code(arbre,0,0,dico);
    extraire_nom(nom_archive,arbre,choix,taille,taille_fich,nbfich);
  }
 
  /* Suppression de l’archive */
  if(remove(nom_archive)!=0)
  {
    perror("Erreur dans la suppression de l’archive ");
    exit(EXIT_FAILURE);
  }
}
 
/*————-Déplacement du fichier à compresser——————-*/
void copier_fichier(char nom[])
{
  FILE *SOURCE, *DEST;
  char *nom_dest; /* Chemin absolu du fichier à compresser */
  char nomfich[90]; /* Nom du fichier à compresser */
  char charlu;
  int i;
 
  /* Récuperation du nom de fichier */
  for(i=strlen(nom);(charlu=nom[i])!=’\\’;i–);
  strcpy(nomfich,&nom[i]);
 
  if( (nom_dest=( (char *)malloc(sizeof(char)* (10+strlen(nomfich))) ) ) ==NULL)
  {
    perror("Erreur dans le malloc de la fonction copier_fichier() ");
    exit(EXIT_FAILURE);
  }
 
  strcpy(nom_dest,"C:\\Temp\\C");
  strcat(nom_dest,nomfich);
 
  /* Ouverture des fichiers */
  if((SOURCE=fopen(nom,"rb"))==NULL)
  {
    perror("Erreur dans l’ouverture du fichier dans la fonction copier_fichier() ");
    exit(EXIT_FAILURE);
  }
  if((DEST=fopen(nom_dest,"wb"))==NULL)
  {
    perror("Erreur dans l’ouverture du fichier dans la fonction copier_fichier(), vérifier que le répertoire C:\\Temp\\C existe. ");
    exit(EXIT_FAILURE);
  }
 
  while(fread(&charlu, sizeof(char), 1, SOURCE))
  fwrite(&charlu,sizeof(char),1,DEST);
 
  free(nom_dest); /* Libération de l’espace mémoire */
  fclose(SOURCE); /* Fermeture des fichiers */
  fclose(DEST);
}
 
/*——————–Compter les occurences———————*/
void compter_occ(unsigned int carac[], char nom[])
{
  FILE *F; /* Fichier à partir duquel seront comptées les occurences */
  int charlu; /* Caractère courant lu dans le fichier */
  unsigned int taille=0; /* Taille du fichier en octets*/
 
  /* Ouverture du fichier */
  if( (F = fopen(nom,"rb")) == NULL )
  {
    perror("Erreur dans l’ouverture du fichier ");
    exit(EXIT_FAILURE);
  }
 
  while((charlu=fgetc(F))!=EOF)
  carac[charlu]++; /* Incrementation de la case correspondante au caractère */
 
  fclose(F);
}
 
/*————————-Création du fichier frequence.dat——————–*/
void creer_freq(unsigned int arbreN[], char nom[])
{
  FILE *FREQ;
  int i;
  char *nomfich;
  char nombre[12]; /* Fréquence convertit en chaine de caractères */
 
  /* Fabrication du nom du fichier */
  if( (nomfich=( (char *)malloc(sizeof(char)* (15+strlen(nom))) ) ) ==NULL)
  {
    perror("Erreur dans le malloc de la fonction creer_freq() ");
    exit(EXIT_FAILURE);
  }
  strcpy(nomfich,nom);
  strcat(nomfich,"-frequence.txt");
 
  /* Création du fichier fréquence.dat */
  if( (FREQ = fopen(nomfich,"w")) == NULL )
  {
    perror("Erreur dans l’ouverture du fichier frequence.dat ");
    exit(EXIT_FAILURE);
  }
 
  /* Ecriture dans le fichier */
  for(i=0;i<MAX;i++)
  {
    fputc(i,FREQ);
    fputc(‘ ‘,FREQ);
    itoa(arbreN[i],nombre,10); /* Conversion en chaine de caractère de l’occurence */
    fputs(nombre,FREQ);
    fputc(‘\n’,FREQ);
  }
  free(nomfich);
  fclose(FREQ);
}
 
/*——————-Création de l’arbre——————–*/
struct arbre_huff * creer_arbre(unsigned int arbreN[])
{
  unsigned int i;
  struct temp_huff tmp;
  struct arbre_huff *arbre;
  unsigned int cpt_max=0;
 
  /* Initialisation */
  tmp.restant=0;
 
  for (i=0;i<MAX;i++)
  {
    /* On enlève les caractères qui ne sont pas dans le fichier */
    if (!arbreN[i])
    continue;
 
    /* Insertion dans l’arbre de chaque caractère */
    if(!(arbre=malloc(sizeof(*arbre))))
    {
      perror("Erreur dans malloc de la fonction creer_arbre ");
      exit(EXIT_FAILURE);
    }
    /* Remplissage des feuilles */
    arbre->c=(char)i;
    arbre->gauche=NULL;
    arbre->droite=NULL;
    arbre->occurence=arbreN[i];
    if((arbre->occurence)>cpt_max) /* On garde en mémoire le nombre d’occurence max */
    cpt_max=arbre->occurence;
    ajouter_temp_huff(&tmp,arbre);
  }
 
  while(tmp.restant>1) /* Tant que l’on a pas la racine de l’arbre */
  {
    if (!(arbre=malloc(sizeof(*arbre))))
    {
      perror("Erreur dans malloc() de la fonction creer_arbre ");
      exit(EXIT_FAILURE);
    }
    arbre->gauche=nouveau_noeud(&tmp);
    arbre->droite=nouveau_noeud(&tmp) ;
    arbre->occurence=arbre->gauche->occurence + arbre->droite->occurence; /* Le nouveau noeud crée à pour poids la somme des deux précédents */
 
    ajouter_temp_huff(&tmp,arbre);
  }
 
  /* On possède maintenant juste la racine de l’arbre */
  arbre=nouveau_noeud(&tmp);
  return arbre;
}
/*———————Ajouter_temp_huf——————————*/
void ajouter_temp_huff(struct temp_huff *tmp, struct arbre_huff *arbre)
{
  int i;
 
  /* Recherche de la position ou inserer */
  for(i=tmp->restant;(tmp->restant>0) && ((tmp->noeud[i-1]->occurence)<(arbre->occurence));)
  {
    tmp->noeud[i]=tmp->noeud[i-1];
    if(!(–i))
    break;
  }
  /* Insertion des noeuds de l’arbre */
  tmp->noeud[i]=arbre;
  tmp->restant++;
}
 
/*————–Recuparation de la valeur ayant la plus faible occurence——–*/
struct arbre_huff * nouveau_noeud(struct temp_huff *tmp)
{
  /* On teste que le fichier n’est pas vide */
  if(tmp->restant==0)
  {
    perror("Le fichier ne contient aucune donnée ");
    exit(EXIT_FAILURE);
  }
  (tmp->restant);
  return tmp->noeud[tmp->restant];
}
 
/*———————-Suppression de l’arbre de Huffman———————*/
/*—– Algorithme de suppression de l’arbre binaire de Huffman —–*/
/* Cette fonction récursive va supprimer un arbre binaire en parcourant */
/* tous les fils et en remontant jusqu'à la racine.                     */
void suppr_arbre(struct arbre_huff **arbre)
{
  if((*arbre)->gauche && (*arbre)->droite)
  {
    suppr_arbre(&(*arbre)->gauche);
    suppr_arbre(&(*arbre)->droite);
    free(*arbre);
    *arbre=NULL;
  }
}
 
/*———————-Creer codage——————–*/
void creer_code(struct arbre_huff *arbre, int code, int niveau, struct dictionaire dico[])
{
  /* Condition d’arret de la fonction récursive : si on est sur une feuille */
  if((arbre->gauche==NULL)&&(arbre->droite==NULL))
  {
    arbre->code=code;
    arbre->bits=niveau;
    /* Création du dictionaire */
    dico[arbre->c].code=code;
    dico[arbre->c].bits=niveau;
    return;
  }
 
  /* On part sur la gauche */
  if(arbre->gauche!=NULL)
  creer_code(arbre->gauche,(code<<1),niveau+1,dico); /* La branche qui part à gauche est celle des 0 */
 
  /* On part sur la droite */
  if(arbre->droite!=NULL)
  creer_code(arbre->droite,(code<<1)+1,niveau+1,dico); /* La branche qui part à droite est celle des 1 */
}
 
/*————————-Enregistrement dans le fichier codage.dat———————- */
void ecrire_codage(struct dictionaire dico[], char nom[])
{
  FILE *CODAGE;
  int i, j;
  int diff;
  char *nomfich;
  char nombre[30]; /* Codage de Huffman convertit en caractère */
 
  /* Fabrication du nom du fichier */
  if( (nomfich=( (char *)malloc(sizeof(char)* (12+strlen(nom))) ) ) ==NULL)
  {
    perror("Erreur dans le malloc de la fonction creer_freq() ");
    exit(EXIT_FAILURE);
  }
  strcpy(nomfich,nom);
  strcat(nomfich,"-codage.txt");
 
  if( (CODAGE=fopen(nomfich,"w"))==NULL)
  {
    perror("Erreur dans l’ouverture du fichier codage.dat ");
    exit(EXIT_FAILURE);
  }
 
  for(i=0;i<MAX;i++)
  {
    if(dico[i].bits==0) /* On ignore les caractères sans codage */
    continue;
 
    itoa(dico[i].code,nombre,2);
    diff=0;
    /* Ajout des 0 devant la chaine */
    if(strlen(nombre)!=dico[i].bits)
    {
      diff=dico[i].bits-strlen(nombre);
      for(j=strlen(nombre);j>=0;j–)
      nombre[j+diff]=nombre[j];
      for(j=0;j<diff;j++)
      nombre[j]=0;
 
    }
    fputc(i,CODAGE);
    fputc(‘ ‘,CODAGE);
    fputs(nombre,CODAGE);
    fputc(‘\n’,CODAGE);
  }
  free(nomfich);
  fclose(CODAGE);
}
 
/*———————Encodage du fichier——————————*/
/* A partir du dictionaire on parcours le fichier à compresser en */
/* remplaçant le caractère par son codage, ce codage est enregistré */
/* dans un buffer. Lorsque le buffer est plein on l’enregistre dans */
/* l’archive. */
unsigned int encodage(struct dictionaire dico[], char nom[])
{
  FILE *F, *FTMP; /* Fichiers source et destination */
  char nomfich[90];
  int i;
  int charlu; /* Caractère courant lu dans le fichier */
  unsigned int buffer; /* Stockage tant qu’on ne peut pas ecrire un octet */
  unsigned char code; /* Codage de huffman du caractère */
  unsigned short int taille_buffer; /* Nombre de bits significatifs du buffer */
  unsigned int taille_fich; /* Taille du fichier à compresser en octets */
 
  /* Récuperation du nom de fichier */
  for(i=strlen(nom);(charlu=nom[i])!=’\\’;i–);
  strcpy(nomfich,"C:\\Temp");
  strcat(nomfich,&nom[i]);
  strcat(nomfich,".tmp");
 
  if( (FTMP=fopen(nomfich,"wb"))==NULL)
  {
    perror("Erreur dans l’ouverture du fichier .tmp ");
    exit(EXIT_FAILURE);
  }
  if((F=fopen(nom,"rb"))==NULL)
  {
    perror("Erreur dans l’ouverture du fichier à compresser ");
    exit(EXIT_FAILURE);
  }
 
  taille_buffer=0;
  buffer=0;
  taille_fich=0;
  while((charlu=fgetc(F))!=EOF)
  {
    buffer=buffer << dico[charlu].bits; /* Décalage du nombre de bits nécessaire au caractère à coder */
    buffer=buffer | dico[charlu].code; /* Masque binaire afin de concatener la valeur */
    taille_buffer=taille_buffer+dico[charlu].bits;
 
    /* Ecriture du buffer dans le fichier losque celui-ci est plein */
    while(taille_buffer>=8)
    {
      taille_buffer=taille_buffer-8; /* Taille après l’enregistrement */
      code=buffer>>taille_buffer; /* On prend le premier caractère à enregister */
      fputc(code,FTMP);
    }
    taille_fich++;
  }
  /* Enregistrement du buffer en cours */
  if(taille_buffer)
  {
    buffer=buffer<<(8-taille_buffer); /* On met les derniers bits à 0 */
    fputc(buffer,FTMP);
  }
 
  fclose(F);
  fclose(FTMP);
  return taille_fich;
}
 
/*———————Création de l’archive———————-*/
void ecrire_fichier(unsigned int carac[], char nom[], unsigned short int nbfich, unsigned int taille, short int mark)
{
  FILE *ARCHIVE, *TMP;
  char *nom_archive;
  char *nom_tmp;
  short int charlu;
  short int i,j;
 
  for(j=strlen(nom);(charlu=nom[j])!=’\\’;j–); /* Récupération du nom du fichier */
  /* Fabrication du nom des fichiers */
  if( (nom_archive=( (char *)malloc(sizeof(char)* (5+strlen(nom))) ) ) ==NULL)
  {
    perror("Erreur dans le malloc de la fonction ecrire_fichier() ");
    exit(EXIT_FAILURE);
  }
  if( (nom_tmp=( (char *)malloc(sizeof(char)* (12+strlen(&nom[j]))) ) ) ==NULL)
  {
    perror("Erreur dans le malloc de la fonction ecrire_fichier() ");
    exit(EXIT_FAILURE);
  }
  strcpy(nom_tmp,"C:\\Temp");
  strcat(nom_tmp,&nom[j]);
  strcat(nom_tmp,".tmp");
  if (!nbfich) /* Nom de l’archive pour un fichier seul */
  strcpy(nom_archive,nom);
  else /* Si il s’agit du répertoire */
  {
    for(i=strlen(nom);nom[i]!=’\\’;i–);
    strncpy(nom_archive,nom,i); /* Copie du nom du répertoire */
    nom_archive[i]=’\0; /* Ajout du \0 final */
  }
  strcat(nom_archive,".zap");
 
  /* Ouverture des fichiers */
  if( (TMP=fopen(nom_tmp,"rb"))==NULL)
  {
    perror("Erreur dans l’ouverture du fichier .tmp ");
    exit(EXIT_FAILURE);
  }
  if((ARCHIVE=fopen(nom_archive,"a+b"))==NULL)
  {
    perror("Erreur dans la création de l’archive ");
    exit(EXIT_FAILURE);
  }
 
  if(mark==0) /* 1 seul fichier ou premier fichier du repertoire */
  {
    fwrite(&nbfich,sizeof(short int),1,ARCHIVE); /* Nombre de fichiers dans l’archive 2 octets */
 
    /* Stockage des informations permettant de reconstituer l’arbre binaire */
    for(i=0;i<MAX;i++)
    {
      if(!carac[i]) /* Si le caractère n’apparait pas dans le fichier */
      continue;
      fwrite(&i,sizeof(char),1,ARCHIVE); /* Ecriture du caractère */
      fwrite(&carac[i],sizeof(int),1,ARCHIVE); /* Nombre d’occurences du caractère */
    }
    fputc(0,ARCHIVE); /* Caractère nul qui sépare l’entête des données */
  }
 
  if(nbfich>=1) /* Si il s’agit d’un répertoire */
  {
    fputs(&nom[j+1],ARCHIVE); /* Enregistrement du nom du fichier */
    fputc(‘\n’,ARCHIVE);
  }
  fwrite(&taille,sizeof(int),1,ARCHIVE); /* Stockage des tailles des fichiers */
 
  /* On recopie le fichier contenu dans tmp à la suite */
  while(!feof(TMP))
  {
    fread(&charlu,sizeof(char),1,TMP);
    fwrite(&charlu,sizeof(char),1,ARCHIVE);
  }
  free(nom_archive);
  free(nom_tmp);
  fclose(ARCHIVE);
  fclose(TMP);
}
 
/*—————–Lecture de l’en-tête————————*/
int lire_index(unsigned int carac[], char nom[], int choix, short int *nbfich, short int mark)
{
  FILE *ARCHIVE;
  unsigned char charlu;
  unsigned int taille=0; /* Taille du fichier */
 
  /* Ouverture du fichier */
  if( (ARCHIVE=fopen(nom,"rb"))==NULL)
  {
    perror("Erreur dans la fonction lire_index(). Impossible d’ouvrir l’archive . ");
    exit(EXIT_FAILURE);
  }
  if(mark==1)
  {
    /* Vérification simpliste pour vérifier que c’est bien une archive valide */
    fread(nbfich,sizeof(short int),1,ARCHIVE);
    taille=taille+sizeof(short int);
    if(choix==2 && *nbfich!=0) /* Si l’archive a été crée avec (1) et qu’elle ne contient pas un fichier */
    {
      printf("L’archive n’a pas été créée avec (1).",nbfich);
      exit(EXIT_FAILURE);
    }
    if(choix==4 && *nbfich<1)
    {
      printf("L’archive n’a pas été créée avec (3). \n");
      exit(EXIT_FAILURE);
    }
  }
  /* Lecture du nombre d’occurences de chaque caractère */
  fread(&charlu,sizeof(char),1,ARCHIVE);
  taille=taille+sizeof(char);
  do {
    fread(&carac[charlu],sizeof(int),1,ARCHIVE); /* Lecture du nombre d’occurences de chaque caractère */
    fread(&charlu,sizeof(char),1,ARCHIVE); /* Lecture d’un nouveau caractère */
    taille=taille+sizeof(int)+sizeof(char);
  }while(charlu); /* La fin de l’index est signalé par 0 */
  fclose(ARCHIVE);
  return taille;
}
 
/*———————–Fabrication du nom des fichiers———————-*/
void extraire_nom(char nom[], struct arbre_huff *arbre, int choix, int taille, unsigned int taille_fich, short int nbfich)
{
  char nomfich[120]={0};
 
  /* Fabrication du nom original */
  strncat(nomfich,nom,strlen(nom)-4); /* Copie du nom de l’archive moins les 3 derniers caractères */
 
  if(choix==2) /* Si l’archive contient un seul fichier */
  taille=decodage(nom,nomfich,arbre,taille,1);
 
  if(choix==4) {
    do {
      taille=decodage(nom,nomfich,arbre,taille,0);
      nbfich–;
      strcpy(nomfich,"");
      strncat(nomfich,nom,strlen(nom)-4);
    }while(nbfich);
  }
}
 
/*————————Décodage d’un fichier————————–*/
int decodage(char nom[], char nomfich[], struct arbre_huff *arbre, int taille, short int mark)
{
  FILE *ARCHIVE, *F;
  unsigned int buffer=0; /* Prochains octets à decoder */
  char nomfich2[100]={0}; /* Fichier à decompresser */
  int charlu,i=0;
  unsigned int taille_buffer=0;
  unsigned int taille_fich; /* Taille du fichier en decompression */
  struct arbre_huff *carac; /* Caractère décodé */
 
  /* Ouverture des fichiers */
  if( (ARCHIVE=fopen(nom,"rb"))==NULL)
  {
    perror("Erreur dans l’ouverture de l’archive ");
    exit(EXIT_FAILURE);
  }
  if(mark==0)
  {
    fseek(ARCHIVE,taille,SEEK_SET);
    do{
      fread(&nomfich2[i],sizeof(char),1,ARCHIVE);
      i++;
    }while(nomfich2[i-1]!=’\n’);
    taille=taille+strlen(nomfich2);
    strcat(nomfich,"\\");
    strncat(nomfich,nomfich2,strlen(nomfich2)-1);
    printf("Décompression de %s\n",nomfich);
  }
  if((F=fopen(nomfich,"wb"))==NULL)
  {
    perror("Erreur dans la création du fichier ");
    exit(EXIT_FAILURE);
  }
 
  fseek(ARCHIVE,taille,SEEK_SET); /* Placemement à la fin de l’en-tête */
 
  fread(&taille_fich,sizeof(int),1,ARCHIVE); /* Lecture de la taille du fichier */
  taille=taille+sizeof(int);
 
  while(((charlu=fgetc(ARCHIVE))!=EOF) && taille_fich)
  {
    taille++;
    /* Insertion du caractère lu dans le buffer */
    buffer=buffer<<8;
    buffer=buffer|charlu; /* Stockage du caractère à la suite du buffer */
    taille_buffer=taille_buffer+8;
 
    while(taille_fich &&(carac=convert_huff(arbre,buffer,taille_buffer,0)))
    {
      taille_fich–;
      fputc(carac->c,F);
      taille_buffer=taille_buffer – carac->bits;
    }
  }
  taille++;
  fclose(F);
  fclose(ARCHIVE);
  return taille;
}
 
/*———————–Recherche du caractère dans l’arbre————-*/
struct arbre_huff * convert_huff(struct arbre_huff *arbre, unsigned int buffer, unsigned int buffer_taille, unsigned int niveau)
{
  if(niveau>buffer_taille) /* Si il n’y a pas assez de bits pour faire un caractère */
  return NULL;
 
  if((arbre->gauche==NULL)&&(arbre->droite==NULL)) /* Le caractère a été trouvé */
  return arbre;
 
  /* Si le dernier chiffre est un 0 on part à gauche */
  if((arbre->gauche!=NULL) && !((buffer >> (buffer_taille – niveau-1))&1))
  return convert_huff(arbre->gauche,buffer,buffer_taille,niveau+1);
 
  /* Si le dernier chiffre est un 1 on part à droite */
  if((arbre->droite!=NULL) && ((buffer >> (buffer_taille – niveau-1))&1))
  return convert_huff(arbre->droite,buffer,buffer_taille,niveau+1);
 
  return NULL; /* Si le code n’existe pas dans l’arbre */
}

22 réflexions au sujet de “Code source programme de Huffman en langage C”

  1. Bonjour !

    J’ai une question : est-ce normal que quand je compresse un fichier texte, le fichier compressé, après l’avoir ouvert ne me donne pas des bits ? Mais me donne d’autres caractères ? (sinon la décompression fonctionne très bien)

    Répondre
    • Bonjour Fox,

      C’est tout à fait normal en effet. L’archive est au format binaire et il n’est plus possible de l’ouvrir avec un éditeur de texte classique car les caractères présents ne sont pas tous affichables. Pour savoir le contenu de chaque octet, il faut à la place utiliser un éditeur hexadécimal. Il en existe des dizaines à télécharger gratuitement.

      Répondre
      • Car j’ai le même projet à faire (mais juste avec un .txt), il faut que je puisse le compresser et le décompresser avec Huffman. (il faut que le fichier compressé soit lisible et qu’il y ait des 1 et des 0) Comment faire pour l’ouvrir avec un simple bloc note ?
        Sinon je vais tester avec notepad ^^

        Répondre
        • Bonjour, cela m’intéresse aussi, comment faire pour l’ouvrir avec un simple bloc note et que l’affichage du texte soit que des 0 et des 1 svp ?

          Merci d’avance

          Répondre
        • De façon très simplifiée, voici pourquoi vous ne pouvez pas voir le résultat de la compression avec un éditeur de texte classique : la compression va remplacer des caractères alphabétiques codés sur 8 bits par une suite de bits (0 ou 1) de longueur variable. Les éditeurs de texte travaillent avec des groupes de longueur fixe de 8 bits, le résultat de la compression de Huffman n’est donc pas compréhensible pour eux. Pour connaître le contenu de l’archive au format binaire, il faut passer par un éditeur hexadécimal et faire la conversion Hexa -> Binaire.

          Par ailleurs si on remplace A par 0101, on n’a rien compressé puisque le résultat est 4 fois plus long que la lettre d’origine !!

          Répondre
    • Bonjour francky,

      Dans le code ci-dessus, la fonctionnalité n’est pas mise en place mais ça ne me semble pas très compliqué à faire. Il suffirait de compter la taille du fichier original lors du dénombrement de chacun des caractères dans une variable CPT1. Il faudrait compter chaque octet écrit dans l’archive en n’oubliant pas d’ajouter la taille de l’arbre dans une variable CPT2. En fin de programme, le taux de compression correspond à l’opération CPT1 / CPT2.

      Répondre
  2. Bonjour !!! Tazzaz, merci beaucoup pour le projet ça m’a bien aidé, j’ai rencontré un souci et je ne parviens pas à résoudre le problème, lorsque l’utilisateur entre le nom du fichier à compresser ou à décompresser, ça me renvoie toujours les erreurs contenues dans la fonction perror alors comment faire s’il te plait… et merci d’avance.

    Répondre
    • Bonjour Stéphane,

      Très content que ce code source écrit il y a plus de 10 ans ait pu encore être utile 🙂

      Pour ton problème, c’est la première fois que j’en entends parler. Pour que le programme fonctionne correctement, les répertoires C:\Temp\ et C:\Temp\C\ doivent avoir été créés préalablement. Est-ce que tu as bien renseigné le chemin complet du fichier à compresser ? Par exemple : C:\Temp\Fichier.doc Tu peux voir les captures écran de l’utilisation du programme sur cette page : http://www.tazzaz.com/16-ii-la-theorie-de-la-programmation/

      Répondre
    • Bonjour Michael,

      Le programme a été écrit spécialement pour Windows à cause de la partie qui permet de compresser tous les fichiers d’un répertoire. Mise à part cette partie du code qui utilise la librairie spécifique windows.h, tout le reste devrait fonctionner sous Linux.

      Comme c’est une question qui revient souvent, si jamais tu souhaites partager tes adaptations, tu peux me les envoyer, c’est avec plaisir que je créerai une nouvelle page pour la version Linux.

      Répondre
  3. Bonjour !! Je n’ arrive pas à compiler le programme, est-ce qu’ il y aurait un lien pour avoir le code-source ? J’ai fait que copier et coller et peut être qu’ il y aurait eu des erreurs. Merci d’avance

    Répondre
  4. Bonjour ,

    Je voulais avoir une petite précision svp, je veux construire un compresseur d’image JPEG using RLE (Run Length Encoding) et le codage de Huffman , et je voulais savoir si pour vos entré pour le codage de Huffman, vous avez utilisé les codes RLE ( nb.zéros, taille en bits de l’amplitude, amplitude) ?

    Je vous remercie d’avance pour votre aide

    Répondre
  5. Salut merci pour le code source. Dans la fonction creer_code tu mets que :

    /* Condition d’arret de la fonction récursive : si on est sur une feuille */
    if((arbre->gauche==NULL)&&(arbre->droite==NULL))

    est-ce que ce serai pas un || au lieu d’un && car si on a une branche ou par exemple le fils droit est une feuille et le fils gauche n’en ai pas une, alors jamais on ne pourra rentré dans la condition.

    Répondre
    • Salut,

      Je suis content si ce code peut encore servir en 2019

      Concernant ta question, dans ma logique lors des développements, c’est bien un &&. Les pointeurs « gauche » et « droite » contiennent l’adresse du prochain élément. A ce stade, on ne sait pas s’il s’agit d’une feuille ou d’un nœud mais ça n’est pas ce qu’on cherche à savoir. En fait, on descend dans l’arborescence de l’arbre binaire jusqu’à tomber sur une feuille, c’est à dire un éléments qui n’a pas de fils donc (arbre->gauche==NULL)&&(arbre->droite==NULL)

      Peut-être que avec || ça peut toujours marcher, car il me semble qu’il est impossible d’avoir un seul nœud enfant sur un nœud de regroupement. Mais dans ma logique, c’est moins clair.

      Répondre
  6. Bonjour, merci beaucoup pour cette projet!
    Mais j’ai un petit problème. J’ai un erreur pour la compilation du Huffman.c, qur le code : for(i=strlen(nom);(charlu=nom[i])!=’\\’;i–);
    strcpy(nomfich,&nom[i]);

    Erreur affiché c’est: stray ‘\342’ in program.
    Aider moi s’il vous plaît, Merci beaucoup!

    Répondre
    • Bonjour,
      Quels sont le compilateur et l’OS qui provoquent cette erreur ? C’est peut-être les apostrophes qui sont mal encodées. Il faudrait réécrire ’\\’ en '\\'

      Répondre

Laisser un commentaire