Discussion :

[Darksnakes]

Salut tout le monde

Voilà dans le but d'un projet, je dois écrit un algorithme de compression/decompression sur lzw.

J'ai écrit cette algortihme mais j'aurais besoin de vos conseil pour améliorer la rapiditié de celui ci lors de la compression( la decompression marche rapidement)


Pour ceux qui connaissent l'algorithme pour mon dictionnaire j'ai décidé d'utiliser comme dictionnaire un tableau de liste et une fonction de "Hachage" autrement dit qui me donne un numero d'une liste en fonction de la sequence que je dois placer dans le dicitonnaire(et toujours le même numero pour la même sequence).
Pour moi il me sembler que c'était un bon compromis en terme de rapidité et de vitesse.
L'algorithme code progréssivement de 9 à 16 bits avant de réinitialiser le dictionnaire.

Donc j'aimerais savoir si il faudrait que j'utilise une autre structure de recherche pour améliorer la rapidité ou peut etre une meilleur fonction de hachage.
Et j'aimerai aussi savoir si il est possible de l'améliorer pour que je compresse autre chose que des images. En effet dans les images (et autre fichier) on retrouve le caractère NULL, hors j'utilise les fonction tel que strcpy et donc ça pose probleme.. J'avais pensé à utliser les fonction du type memcpy mais elles sont vraiment trops lente.
Alors est ce que je dois faire mes propres fonctions de copy , comparaison et concatenantion et dans ce cas la je me trimbalerais la taille de chaque char * ou est ce qu'il existe une autre solution?


voici mes codes, je suis ouvert à toutes question et remarque. Merci d'avance

Yann

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
 
//dico.h
#define CODE_FIN 256
#define CODE_RAZ 257
#define CODE_BIT_SUP 258
#define CODE_DEBUT 259
#define TAILLE_MAX 65536 //2^16
#define TAILLE_DEBUT 512 //2^9
#define MODULO_HACH 200
#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[]);

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
 
//dico.c
#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");}
   }
}

Code :

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

1
2
3
4
5
6
7
8
9
 
//compressionlzw.h
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
 
int Calculer_nb_bit(int i_Code);
void Compresser_lzw(char * i_Nom_fichier_in, char * i_Nom_fichier_out);

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
99
 
//compressionlzw.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dico.h"
#include "ecrire_bit.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;
     int i;
 
     Fichier_compresse = fopen(i_Nom_fichier_out, "w");
     Curseur = fopen(i_Nom_fichier_in, "r");
     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);
}

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
 
//ecrire_bit.c
#include "ecrire_bit.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; char 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=(char)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;m<8;m++)
                     {codeascii=codeascii+t[m]*pow(2,(7-m));}
                  x=(char)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);
    }
 
}

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
 
//main
#include "compressionlzw.h"
#include "ecrire_bit.h"
#include <math.h>
#include <time.h>
 
int main(int argc, char **argv){
   time_t debut,fin;
   char * Nom_fichier_out;
   FILE * Curs;
   int taille;
   if ((argc == 2) || (argc == 3))
    {  
	if (argc == 2)
  	  {
   	   Nom_fichier_out=(char *)malloc(strlen(argv[1])+5);
   	   strcpy(Nom_fichier_out,argv[1]);
   	   strcat(Nom_fichier_out,".lzw");
	  }
 
        else
          {
           Nom_fichier_out=argv[2];
          }
 
	Curs=fopen(argv[1],"a");
        fseek(Curs,0,2);
        taille=ftell(Curs);
        fclose(Curs);
        printf("Compression du fichier %s(%d octet(s)) vers %s\n",argv[1],taille,Nom_fichier_out);
        printf(".......\n");
        debut=time(NULL);
	Compresser_lzw(argv[1],Nom_fichier_out);
        fin=time(NULL);
	Curs=fopen(Nom_fichier_out,"a");
        fseek(Curs,0,2);
        taille=ftell(Curs);
        fclose(Curs);
	printf("Compression effectuée en %f secondes(%d octet(s)).\n",difftime(fin,debut),taille);
     }
  else
    {
     printf("utilisation : ./lzw fichier_entree [fichier_sortie]\n");
    }
  free(Nom_fichier_out);
    }

mici^^