Sujet Précédent Sujet Suivant

Codage de huffman

snoopi_19ans Messages postés 7 Date d'inscription dimanche 16 avril 2006 Statut Membre Dernière intervention 20 mai 2009 - 23 avril 2007 à 21:33
emmatopiak Messages postés 149 Date d'inscription mercredi 28 mars 2007 Statut Membre Dernière intervention 17 mai 2007 - 29 avril 2007 à 13:48
#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

2 réponses

Réponse 1 / 2
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
23 avril 2007 à 21:39
Regarde la source de vecchio56 sur le code de huffman.

ciao...
BruNews, MVP VC++
0
Réponse 2 / 2
emmatopiak Messages postés 149 Date d'inscription mercredi 28 mars 2007 Statut Membre Dernière intervention 17 mai 2007 2
29 avril 2007 à 13:48
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)
0
Rejoignez-nous