aide à propos de l'algorithme LZW

**walido_mkacha5** · 07/01/2011, 19h30

bonjour
j'ai des difficultés dans l'algorithme de LZW
bon concernant la compression c'est bon ça marche.
en fait j'ai pas pu faire une fct dans la partie du décompression c'est lire_x_bit qui me retourne le code du chaine compressée voilà mon code source é si vous pouvez m'aidez
merci
DICO.C

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
  #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "dico.h"
 
 
t_Liste * Creer_liste(void) {
     return (t_Liste*) malloc(sizeof(t_Liste));
     }
 
int Hacher(char* i_Sequence) {
    int Cle = (unsigned char) i_Sequence[0] + (unsigned char) i_Sequence[strlen(i_Sequence)] + strlen(i_Sequence);
    return Cle % MODULO_HACH;
}
 
void Apprendre_sequence (char* i_Sequence, int i_Code, t_Liste* io_Dico[]) {
     //On calcul la clé
     int Cle=Hacher(i_Sequence);
     t_Liste* Cellule;
     //on créé la cellule
     Cellule = Creer_liste();
     Cellule -> Code = i_Code;
     Cellule -> Sequence = (char *) malloc((strlen(i_Sequence) +1 ) * sizeof(char));
     strcpy(Cellule -> Sequence, i_Sequence);
     //On rajoute cette cellule en debut de la liste correspondante
     Cellule -> Suiv = io_Dico[Cle];
     io_Dico[Cle] = Cellule;
     }
 
int Est_apprise(char* i_Sequence, t_Liste* io_Dico[])
//renvoie le code de la chaine m si elle est deja aprise, -1 sinon
 {
     int Cle = Hacher(i_Sequence);
     int Code;
     bool Ok = false;
     t_Liste* Temp = io_Dico[Cle];//Pointeur sur la liste où doit se trouver la sequence si on la connais
     //si la Sequence n'est qu'un seul charactere, son code est le code ascii.
     if (strlen(i_Sequence) == 1)
     	{return (unsigned char) i_Sequence[0];}
     else { //tant qu'on a pas parcouru toute la liste et qu'on n'a pas trouvé la sequence
            while ((Temp != NULL) && !(Ok))
     		   {
		    Ok = (strcmp(i_Sequence, Temp -> Sequence) == 0);
      	            Code = Temp -> Code;
     		    Temp = Temp -> Suiv;
                   }
	  }
    if (Ok) return Code;
    else return -1;
}
void Vider_liste(t_Liste * io_Liste)
{
 if (io_Liste != NULL)
    {
	if (io_Liste->Suiv == NULL)
       	   {free(io_Liste->Sequence);
            free(io_Liste);}
    	else {Vider_liste(io_Liste->Suiv);
            free(io_Liste->Sequence);
            free(io_Liste);}
    }
}
void Vider_dico( t_Liste * io_Dico[])
{int i;
 for (i=0; i<MODULO_HACH; i++)
{ Vider_liste(io_Dico[i]);
  io_Dico[i]=NULL;}
}
 
void afficher_dico(t_Liste * Dico[]){
int i;
t_Liste * temp;
 for (i=0; i<MODULO_HACH; i++)
   {temp=Dico[i];
   if (Dico[i] != NULL)
   {printf("[%d] :\n",i);
   while (temp != NULL)
     {printf(" (%s) ", temp->Sequence);
     temp=temp->Suiv;}printf("\n");}
   }
}

DICO.H

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define CODE_FIN 256
#define CODE_RAZ 259
#define CODE_BIT_SUP 258
#define CODE_DEBUT 256
#define TAILLE_MAX 65536 //2^16
#define TAILLE_DEBUT 512 //2^9
#define MODULO_HACH 3200
#define NB_BIT_DEBUT 9
 
 
typedef struct Liste  {
			char* Sequence;
			int Code;
			struct Liste * Suiv;
			}t_Liste;
 
//creer une cellule d'une liste
t_Liste * Creer_liste();
 
//Donne une cle pour une Sequence (toujours la même clé pour la même sequence).
int Hacher(char* i_Sequence);
 
//rajoute la sequence et son code dans le Dictionnaire grace à la Clé
void Apprendre_sequence (char* i_Sequence, int i_Cle, t_Liste* io_Dico[]);
 
//si une séquence se trouve dans le dictionnaire elle renvoie son code, -1 sinon
int Est_apprise(char* i_Sequence, t_Liste* io_Dico[]);
 
//reinitialise le dictionnaire.
void Vider_dico( t_Liste * io_Dico[]);
 
//affiche les sequence présentes dans le dictionnaire.
void afficher_dico(t_Liste * Dico[]);

compression.c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dico.h"
#include"compression.h"
 
int Calculer_nb_bit(int i_Code)
{
    if (i_Code <= 511) return 9;
    else if (i_Code <= 1023) return 10;
    else if (i_Code <= 2047) return 11;
    else if (i_Code <= 4095) return 12;
    else if (i_Code <= 8191) return 13;
    else if (i_Code <= 16383) return 14;
    else if (i_Code <= 32767) return 15;
    else return 16;
}
 
void Compresser_lzw(char * i_Nom_fichier_in, char* i_Nom_fichier_out)
{
 
     FILE * Fichier_compresse;
     FILE * Curseur;
     char * Sequence = (char *) malloc(sizeof(char));
     char * Attente = (char *) malloc(sizeof(char));
     char  Lu;
     t_Liste * Dico[MODULO_HACH] = {NULL};
     int Code = CODE_DEBUT;
     //code==256=>fin de compression
     //code==257=>raz
     //code=258=>Nb_bit++
     int Code_Attente;
     int Code_Seq;
     int Nb_bit;
 
 
     Fichier_compresse = fopen(i_Nom_fichier_out, "wb");
     Curseur = fopen(i_Nom_fichier_in, "rb");
     Attente[0] = '\0';
     Sequence[0] = '\0';
     while (fread(&Lu, sizeof(char), 1, Curseur) == 1)
       {    free(Sequence);
            Sequence=(char *) malloc((strlen(Attente) + 2) * sizeof(char));
            strcpy(Sequence, Attente);
            strncat(Sequence, &Lu, 1);
	    Code_Seq = Est_apprise(Sequence, Dico);
	    //printf("Est_apprise\n");
            Nb_bit = Calculer_nb_bit(Code);
            if  (Code_Seq != -1)
//si on connais la sequence, on la met en Attente.
	      {
	        free(Attente);
                Attente = (char *) malloc((strlen(Sequence)+1) * sizeof(char));
		strcpy(Attente, Sequence);
                 Code_Attente = Code_Seq;
                 }
            else
                {
     //sinon on l'apprend.
		//printf("code :%d\n",Code);
		Apprendre_sequence(Sequence, Code, Dico);
                ecrire_x_bit(Code_Attente, Nb_bit, Fichier_compresse);
                //printf("ecrit : %d\n",Code_Attente);
                Code++;
                if (Nb_bit != Calculer_nb_bit(Code))
                   {
			ecrire_x_bit (CODE_BIT_SUP, Nb_bit, Fichier_compresse);
                        Nb_bit = Calculer_nb_bit(Code);
                    }
         	free(Attente);
                Attente=(char *) malloc(sizeof(char) + 1);
                Attente[0] = Lu;
                Attente[1] = '\0';
                Code_Attente = (unsigned char) Lu;
		if (Code == TAILLE_MAX) {
                           printf("Raz Dico\n");
			   ecrire_x_bit(Code_Attente, Nb_bit, Fichier_compresse);
			   ecrire_x_bit(CODE_RAZ, Nb_bit, Fichier_compresse);
                           Vider_dico(Dico);
                           Code = CODE_DEBUT;
			   free(Attente);
			   Attente = (char *) malloc(sizeof(char));
			   Attente[0] = '\0';
                           }
 
 
                }
     }
//a la fin, il reste encore le dernier caractere Lu en Attente
      ecrire_x_bit(Code_Attente, Nb_bit, Fichier_compresse);
      ecrire_x_bit(CODE_FIN, Nb_bit, Fichier_compresse);
      fclose(Fichier_compresse);
      fclose(Curseur);
     free(Sequence);
     free(Attente);
Vider_dico(Dico);
}

compression.h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
 
void ecrire_x_bit(int nb, int nbbit, FILE * Fic);
 
void Compresser_lzw(char * i_Nom_fichier_in, char * i_Nom_fichier_out);
void Decompresser_lzw(char * i_Nom_fichier_lzw);
 
typedef struct Seq_Taille
{
    char* Sequence;
    int Taille;
} t_Seq_Taille;

ecrire.c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<stdio.h>
#include <math.h>
 
static int t[8];//buffer
static int position=0;
 
 
void ecrire_x_bit(int nb, int nbbit, FILE * Fic)
{int c=nb,i=position,codeascii=0,cptb=0; int x;
  int m,k=0;
while (c!=0)
  {    t[i]=c%2;
       cptb++;
       i++;
       c=c/2;
       if (i==8) {
	          for (m=0;m<8;m++)
		    {
		      codeascii=codeascii+t[m]*pow(2,(7-m));
		    }
		  x=(int)codeascii;
                  codeascii=0;
                  fwrite(&x,sizeof(char),1,Fic);
		  i=0;
                 }
       }
position=i;
while (cptb!=nbbit)
      {
      i=position;
      t[i]=0;
      cptb++;
      i++;
      m=0;
      if (i==8) { for (m=0;m<8;m++)
                     {codeascii=codeascii+t[m]*pow(2,(7-m));}
                  x=(int)codeascii;
                  codeascii=0;
                  fwrite(&x,sizeof(char),1,Fic);
                  position=0;
                 }
                 else {position=i; }
      }
 
if (nb==256 && position!=0)
  {
    for (k=position;k<8;k++)
         {t[k]=0;}
    for (i=0;i<8;i++)
             {codeascii=codeascii+t[i]*pow(2,(7-i));}
    x=codeascii;
    fwrite(&x,sizeof(char),1,Fic);
    }
 
}

decompression.c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include"compression.h"
#include "dico.h"
#include "math.h"


void Decompresser_lzw(char * i_Nom_fichier_lzw)
{

     FILE * Curseur;
     FILE * Fichier_decompresse;
     int Code_lu;
     int Nb_bit=NB_BIT_DEBUT;
     t_Seq_Taille * Dico=(t_Seq_Taille *)malloc(pow(2,16)*sizeof(t_Seq_Taille));
     int i;
     int Codec=CODE_DEBUT;
     int Taille;
     //initialisation du dictionnaire sur les 256 premier caractères
     for (i=0;i<256;i++)
     {
	Dico[i].Sequence=(char *)malloc(sizeof(char));
     	Dico[i].Sequence[0]=i;
     	//Dico[i].Sequence[1]='\0';
	Dico[i].Taille=1;
     }

     for (i=256;i<pow(2,16);i++)
     {
	Dico[i].Sequence=NULL;
	Dico[i].Taille=0;
     }
     Curseur=fopen(i_Nom_fichier_lzw,"r");
     Fichier_decompresse=fopen("decompression.txt","w");
     Code_lu=lire_x_bit(NB_BIT_DEBUT,Curseur);
     //on verifie qu'on a pas compresse un fichier vide
     if (Code_lu != CODE_FIN)
	{
        fread(&Code_lu,sizeof(char),1,Fichier_decompresse);
        Dico[Codec].Sequence=(char *)malloc(sizeof(char));
	Dico[Codec].Sequence[0]=Code_lu;
	//Dico[Codec].Sequence[1]='\0';
	Dico[Codec].Taille=1;
	}
	Code_lu=lire_x_bit(Nb_bit,Curseur);
     //tant qu'on est pas arrive au Code de fin de compression.
     while (Code_lu != CODE_FIN )
     {
	//si c'est le Code de r.a.z
           if (Code_lu==CODE_RAZ)
              {
		printf("R.A.Z\n");
		for(i=0;i<pow(2,Nb_bit);i++)
		{
		  if (Dico[i].Sequence != NULL)
			{free(Dico[i].Sequence);}
		  Dico[i].Taille=0;
		}
                Codec=CODE_DEBUT;
		Nb_bit=NB_BIT_DEBUT;
		Code_lu=lire_x_bit(NB_BIT_DEBUT,Curseur);
		if (Code_lu != CODE_FIN)
        	{
         		fread(&Code_lu,sizeof(char),1,Fichier_decompresse);
         		Dico[Codec].Sequence=(char *)malloc(sizeof(char));
			Dico[Codec].Sequence[0]=Code_lu;
			Dico[Codec].Taille=1;
			//Dico[Codec].Sequence[1]='\0';
		}
		printf("fin R.A.Z\n");

              }
            //si c'est le Code de lecture sur un bit suplémentaire on double le dico
           else if (Code_lu==CODE_BIT_SUP)
                	{
                            Nb_bit++;
                            //Dico=(t_Seq_Taille*)realloc(Dico,pow(2,Nb_bit)*sizeof(t_Seq_Taille));
                            }
           else
     	   {
	    Taille=Dico[Codec].Taille;
	    Dico[Codec].Sequence[Taille]=Dico[Code_lu].Sequence[0];
	    //Dico[Codec].Sequence[Taille+1]='\0';
	    Dico[Codec].Taille++;
	    for(i=0;i<Dico[Code_lu].Taille;i++)
		{fputc(Dico[Code_lu].Sequence[i],Fichier_decompresse);}
	    Codec++;
	    Dico[Codec].Sequence=(char *)malloc(sizeof(char)*(Dico[Code_lu].Taille));
	    Dico[Codec].Sequence=memcpy(Dico[Codec].Sequence,Dico[Code_lu].Sequence,Dico[Code_lu].Taille);
	    Dico[Codec].Taille=Dico[Code_lu].Taille;
     	  }
     Code_lu=lire_x_bit(Nb_bit,Curseur);
     }
     fclose(Curseur);
     fclose(Fichier_decompresse);
}

**jeroman** · 07/01/2011, 20h10

Salut

Utilise les balises CODE. C'est illisible.

aide à propos de l'algorithme LZW

C

Discussions similaires

Partager

Partager