Codage de huffman

Signaler
Messages postés
7
Date d'inscription
dimanche 16 avril 2006
Statut
Membre
Dernière intervention
20 mai 2009
-
Messages postés
149
Date d'inscription
mercredi 28 mars 2007
Statut
Membre
Dernière intervention
17 mai 2007
-
#include<stdio.h>
#include<stdlib.h>


typedef struct noeud;




typedef struct cell{
 
 cell *suiv;
 noeud *ab;
}cell;


typedef struct noeud{
 int crd;
 char ch;
 noeud *fg;
 noeud *fd;
}noeud;


typedef cell *lis;
typedef noeud *abr;


lis creer_lis_vid()
{
 lis l;


 l=NULL;


 return l;
}


abr creer_abr_vid()
{
 abr a;


 a=NULL;


 return a;
}


lis inser_lis(lis l, int d, char c)
{
 cell *n, *m;
 abr b;


 n=(cell*)malloc(sizeof(cell));
 b=(abr)malloc(sizeof(noeud));
    n->ab=b ;
 m=l;


 n->ab->crd=d;
 n->ab->ch=c;
 n->ab->fd=NULL;
 n->ab->fg=NULL;
   
 n->suiv=l;
 l=n;


 return l;
}


/*lis nouv_som(abr a, lis l, int crd)
{
 cell *nl,*n;




 nl=(cell*)malloc(sizeof(cell));
 nl->ab=a;
 




 return l;
}*/




int est_vide(abr a)
{
 return(a==NULL);
}


 


int est_feuille(abr a)
{
 return((a->fg==NULL)&&(a->fd==NULL));
}


 


abr  fils_gauche(abr a)
{
 return a->fg;
}
   




abr fils_droit(abr a)
{
 return a->fd;
}




abr creer_abr(abr a1, abr a2, int nb)
{
 abr b;


 b=(abr)malloc(sizeof(noeud));


 b->ch='%';
 b->crd=nb;
 b->fg=a1;
 b->fd=a2;


 return b;
}


lis constr_lis_char(lis p,abr a, FILE *f)
{
 lis k;
 k=p;
 char c;
 int init=1;


 f=fopen("test.txt","rb");


 while(!(feof(f)))
 {
  c=fgetc(f);
  if(!(feof(f)))
  {
   k=inser_lis(k,init, c);
  }
 }


 fclose(f);


 return k;
}


lis freq_char(lis p)
{
 lis lct;
 lis l,q,n;
 l=p;
 
 
 if (l==NULL)
 {
     return l;
 }
 
   while(l!=NULL)
   {
    n=l;
    q=l->suiv;
       
  while(q!=NULL)
  {
   if(q->ab->ch!=l->ab->ch)
   {
    n=q;
    q=q->suiv;
   }
   else
   {
    lct=q;
    n->suiv=q->suiv;
    q=q->suiv;
    l->ab->crd=l->ab->crd+1;
    free(lct);
   }
  };
  l=l->suiv;
   };
 
  
   return p;
}


lis Tri_Liste(lis p)
{
 char x;
 int y;
 
 
 
 lis nc,n;
 nc=p;
 
 
 if (p==NULL)
  return p;
 else
 {


 while(nc!=NULL)
 { 
   n=nc->suiv;
   while(n!=NULL)
    {
     if(nc->ab->crd>n->ab->crd)
     {
      y=n->ab->crd;
     
      x=n->ab->ch;
     
     
      n->ab->crd=nc->ab->crd;


      n->ab->ch=nc->ab->ch;


                     nc->ab->crd=y;
     
      nc->ab->ch=x;
     }


                    
     
     n=n->suiv;
    };
 nc=nc->suiv;
 };
 }
 return p;
}


void aff_lis(lis l)
{
 lis k;
 k=l;


 while(k!=NULL)
 {
  printf("%c\t",k->ab->ch);
  printf("%d",k->ab->crd);
  printf("\n");
  k=k->suiv;
 };
}
/*****************************************************/


abr arbre_huffman(lis l)
{
 abr a,b,c;
 cell *p;
  
   while(l->suiv!=NULL)
   {
 a=l->ab; 
 b=l->suiv->ab; 
 l=l->suiv->suiv;
    if(a->crdcrd)
  c=creer_abr(b,a, b->crd+a->crd);
 else
  c=creer_abr(a,b, a->crd+b->crd);
 




 p=(cell*)malloc(sizeof(cell));
 p->ab=c;


 printf("%d",p->ab->crd);


 p->suiv=l;
 l=p;
 l=Tri_Liste(l);
 printf("\n");
 aff_lis(l);
 printf("\n");
   };
 return c;
}




int nb_n(abr a)
{
 
 if(a!=NULL)
  return(1+nb_n(a->fd)+nb_n(a->fd));
 else
  return 0;


}


 


void prefixe(abr a)
{
 if(a!=NULL)
 {
  printf("|%d",a->crd);
  printf("%c",a->ch);
  printf("\t");
  
  prefixe(a->fg);
  prefixe(a->fd);
 }
}


void main()
{
 abr a;
 lis l;
 FILE *f;
 int n;




 l=creer_lis_vid();
 a=creer_abr_vid();


 l=constr_lis_char(l,a,f);
 printf("La liste des caracteres   :\n");
 aff_lis(l);
 l=freq_char(l); 
 printf("La liste des frequences   :\n");
 aff_lis(l);
 l=Tri_Liste(l);
 printf("Liste apres le tri   :\n");
 aff_lis(l);
    printf("\n\n");
 printf("Construction de l arbre de HUFFMAN\n");
 a=arbre_huffman(l);
 printf("\n\n"); 
 n=nb_n(a);
    printf("Le nombre des noeuds est   :%d\n\n", n);


comp(f,a);
 prefixe(a);


  printf("\n");
}


 




<<<<<<<<<<<salem alikom
voila  le code source de mon programme ecrit en language c,mon but c'est d'effectuer le codage avec la methode de huffman,en utilisant une liste et un arbre ,mais j'arrive pas a trouver la solution,merci de m'aider a clarifier l'idée, je n'arrive pas trouver la methode avec laquelle je vais compresser puis décompresser le fichier ,sachant que chaque caractère avec son occurance existe dans une feuille de l'arbre.>>>>>>>>
merci ,pour tout
A voir également:

2 réponses

Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
26
Regarde la source de vecchio56 sur le code de huffman.

ciao...
BruNews, MVP VC++
Messages postés
149
Date d'inscription
mercredi 28 mars 2007
Statut
Membre
Dernière intervention
17 mai 2007
1
salut,

Pour compresser avec le codage de Huffman il faut faire deux etapes:

la premiere c'est construire l'arbre de Huffman, ce que tu as fait, on va dire que ca marche je n'ai fait que survoler, mais par contre il te manque la deuxieme etape ( oui oui )
Donc:
 -dans la deuxieme etape, tu veux compresser une chaine, disons que c'est "bonjour"
 -tu prends le premier caractere de la chaine
- tu le trouves dans l'arbre et le trajet pour le trouver correspond à l'encodage.
-par exemple, si pour trouver 'b' dans l'arbre tu pars de la racine et tu fais gauche - droite - droite - droite
- alors l'encodage de 'b' va etre 0 1 1 1
 - puis tu fais 'o'
-idem, tu le cherches et tu vois que c'etait droite - gauche - droite - droite - gauche - gauche par exemple
-donc ca va te donner 1 0 1 1 0 0
-tu mets ca a la suite du premier et tu continues jusqu'a avoir fini la chaine
- pour decompresser ca sera plus facile meme
-tu pars de la racine, tu lis 0
-tu arrives a gauche de la racine, mais pas encore une feuille donc tu continues, tu lis 1
- toujours noeud intermediaire
- encore 1 et la tu arrives dans une feuille
-donc tu ecris la valeur de la feuille, qui est 'b' ici
-puis tu repars a la racine et tu continues sur 1 0 1 1 0 0 ...

Ah et si tu arrives pas a trouver la feuille dans l'arbre, tu peux toujours ajouter un pointeur vers le parent pour chaque noeud, ou utiliser de la recursivite (backtracking)