Probleme Algorithme LZW : trop lent

**Darksnakes** · 29/03/2008, 18h05

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^^

**DaZumba** · 30/03/2008, 14h33

Dans la fonction Compresser_lzw(), c'est une très mauvaise idée de faire des free() et malloc() à l'intérieur de la boucle while sur fread(). Tu devrais pouvoir utiliser des tableaux de taille fixe (taille maximale) alloués en dehors de la boucle.
De plus, utilise fgetc() plutot que fread() -- lire un caractere dans un flux est exactement le rôle de fgetc() !

**Darksnakes** · 30/03/2008, 17h06

en ce qui concerne la taille maximal, je la connais pas d'avance. je peux très bien avoir des chaines de mille ou 10 milles caractères voir beaucoup plus(dans le cas ou le fichier n'est composé que de la même lettre).

Ensuite si j'utilise fread c'est totu simplement que j'ai recontré des probleme avec feof() et donc fread me permet et de lire un caractère et de savoir si je suis a la fin du fichier.

voila pourquoi j'ai fait ces choix la.

**DaZumba** · 30/03/2008, 18h08

Envoyé par Darksnakes

en ce qui concerne la taille maximal, je la connais pas d'avance. je peux très bien avoir des chaines de mille ou 10 milles caractères voir beaucoup plus(dans le cas ou le fichier n'est composé que de la même lettre).

Il ne faut pas garder toute une sequence en memoire ! Le truc, c'est de ne garder que ce qui est interessant pour l'algorithme, i.e. code pour la chaine de caractere + caractere suivant. Voir ici, notamment la section intitulée "The Implementation Blues".

Ensuite si j'utilise fread c'est totu simplement que j'ai recontré des probleme avec feof() et donc fread me permet et de lire un caractère et de savoir si je suis a la fin du fichier.

fgetc() renvoit EOF en cas d'erreur ou si la fin du fichier est atteinte (attention, pour cette raison fgetc() renvoit un int, pas un char).

**diogene** · 30/03/2008, 19h59

- Eviter tout ce qui fait parcourir les chaînes implicitement jusqu'à la fin (strlen, strncat,...)
- Eviter les appels redondants à des fonctions. Stocker la valeur rendue pour s'en resservir
- Je ne vois pas le rôle du tableau Attente:
Si Code_Seq != -1 , c'est un duplicata de Sequence
Sinon, il ne sert pas.
Pourquoi ne pas se contenter du tableau Sequence en réallouant de la place si nécessaire ?
Par exemple, (je ne sais pas si ce code marche, j'ai essayé de l'écrire en fonction du code existant, mais des choses peuvent m'avoir échappé. En tout cas, ce peut être une idée de départ)
LSequence est la longueur du tableau Sequence actuellement utilisée
LSequenceAlloc est la longueur actuellement allouée au tableau Sequence (mais pas forcément toute utilisée)

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
     Sequence = NULL;
     LSequence = 1;
     LSequenceAlloc = 0;
     while (...)
     {
       if(Lsequence+1 > LSequenceAlloc)   //assez de place dèjà allouée ?
       {       
          LSequenceAlloc = LSequence+1;  //ou plus si on veut
          prov = realloc(Sequence, LSequenceAlloc); 
          if(prov==NULL){//ERREUR pas assez de mémoire....}        
          Sequence = prov ;
       }
       Sequence[LSequence-1] = Lu;
       Sequence[LSequence] =  0;
       LSequence ++;
//       Nb_bit = Calculer_nb_bit(Code);     ne change que si Code change. Est inutile ici
       if  (Code_Seq != -1)Code_Attente = Code_Seq;
       else
           {
		Apprendre_sequence(Sequence, Code, Dico);
                ecrire_x_bit(Code_Attente, Nb_bit, Fichier_compresse);
                Code++;
                Nb_bitp = Calculer_nb_bit(Code)
                if (Nb_bit != Nb_bitp)
                {
		   ecrire_x_bit (CODE_BIT_SUP, Nb_bit, Fichier_compresse);
                   Nb_bit = Nb_bitp;
                }
                LSequence = 2;                
                Sequence[0] = Lu;
                Sequence[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;
                  LSequence = 1;
                }
           }
       }

**Darksnakes** · 30/03/2008, 20h52

Envoyé par DaZumba

Il ne faut pas garder toute une sequence en memoire ! Le truc, c'est de ne garder que ce qui est interessant pour l'algorithme, i.e. code pour la chaine de caractere + caractere suivant. Voir ici

Donc si je garde que le code, il me faut donc un tableau séquentiel ou un code correspondrais a une séquence. Le soucis est que si je fais une telle structure , il me semble que je vais perdre énormément en temps en recherche puisque je serais obliger de parcourir le tableau en entier au lieu d'une partie avec ma structure actuelle. A moins que je n'ai pas compris.

En ce qui concerne attente, effectivement c'est un duplicata de sequence, attente sert juste pour la compréhension, mais je vais essayer de suivre ton idée diogène effectivement ça devrait me faire gagner en temps.(a part que j'aime pas realloc^^)

sinon pour les strlen et strncat, comment je peux faire sans les utiliser?

et je vais egalement vérifier ce qui concerne les appel redondant,j'y avais pas penser.

Merci a vous deux,

Bonne soirée

**Darksnakes** · 31/03/2008, 19h00

bon j'ai suivi les conseils et j'ai réécrit le code en m'apercevant effectivement que attente ne sert absolument a rien, je n'utilise plus strlen mais je me balade la taille de seq mais je vois pas de différence notable au niveau de la durée (plus ou moins 2 minutes pour un fichier texte de 4,5M ><).
Est ce que j'ai loupé quelquechose?

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
 
#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  Lu;
     t_Liste * Dico[MODULO_HACH] = {NULL};
     int Code = CODE_DEBUT;
     int Code_Attente;
     int Code_Seq;
     int Nb_bit=NB_BIT_DEBUT;
     int Nb_bit_temp=Nb_bit;
     int Taille_seq=0;
     int i;
     Fichier_compresse = fopen(i_Nom_fichier_out, "w");
     Curseur = fopen(i_Nom_fichier_in, "r");
     Sequence[0] = '\0';
     while (fread(&Lu, sizeof(char), 1, Curseur) == 1)
       {   
	    Sequence=(char *) realloc(Sequence,(Taille_seq + 2) * sizeof(char));
            strncat(Sequence, &Lu, 1);
            Taille_seq++;
            Code_Seq = Est_apprise(Sequence,Taille_seq,Dico);
	    if  (Code_Seq != -1)
             //si on connais la sequence, on met son code en Attente.
	      {
	        Code_Attente = Code_Seq;
	      }
            else
                {
     //sinon on l'apprend.
		Apprendre_sequence(Sequence,Taille_seq,Code, Dico);
                ecrire_x_bit(Code_Attente, Nb_bit, Fichier_compresse);
                Code++;
                Nb_bit_temp = Calculer_nb_bit(Code);
                if (Nb_bit != Nb_bit_temp)
                   {
			ecrire_x_bit (CODE_BIT_SUP, Nb_bit, Fichier_compresse);
                        Nb_bit = Nb_bit_temp;
                    }
         	free(Sequence);
                Sequence=(char *) malloc(sizeof(char) + 1);
                Sequence[0] = Lu;
                Sequence[1] = '\0';
		Taille_seq=1;
                //on place le code du caractère lu en attente
                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);
                           //on se remet dans l'état initial.
                           Code = CODE_DEBUT;
			   Nb_bit=NB_BIT_DEBUT;
			   Nb_bit_temp=Nb_bit;
			   free(Sequence);
			   Sequence = (char *) malloc(sizeof(char));
			   Sequence[0] = '\0';
                           Taille_seq=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);
Vider_dico(Dico);
}

je remet la source du 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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
#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 i_Taille_seq) {
    int Cle = (unsigned char) i_Sequence[0] + (unsigned char) i_Sequence[i_Taille_seq] + i_Taille_seq;
    return Cle % MODULO_HACH;
}
 
void Apprendre_sequence (char* i_Sequence,int i_Taille_seq, int i_Code, t_Liste* io_Dico[]) {
     //On calcul la clé
     int Cle=Hacher(i_Sequence,i_Taille_seq);
     t_Liste* Cellule;
     //on créé la cellule
     Cellule = Creer_liste();
     Cellule -> Code = i_Code;
     Cellule->Taille=i_Taille_seq;
     Cellule -> Sequence = (char *) malloc((i_Taille_seq +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;
     }
bool Comparer_Chaine(char * i_Ch1, int i_Taille1, char * i_Ch2, int i_Taille2) {
int i=0;
bool egale=false;
if (i_Taille1 == i_Taille2)
{egale=true;
  while ((i<i_Taille1) && egale)
	{egale=(i_Ch1[i] == i_Ch2[i]);
	 i++;
	}
}
  return egale;
}
int Est_apprise(char* i_Sequence,int i_Taille_seq, t_Liste* io_Dico[])
//renvoie le code de la chaine m si elle est deja aprise, -1 sinon
 {
     int Cle = Hacher(i_Sequence,i_Taille_seq);
     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 (i_Taille_seq == 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 = Comparer_Chaine(i_Sequence,i_Taille_seq, Temp -> Sequence,Temp->Taille); //sera utile pour compresser des images ou autres fichier complexe contenant le caractère null
      	            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");}
   }
}

Peut etre est ce que je dois améliorer la recherche?

J'ai calculer pour ce fichier que pour un RAZ(j'en fait 12) du dico j'ai fais environ 330 000 fois le tant que, donc chaque détaille peut accelerer ou ralentir l'algo
Ha oui une question, comment afficher des millisecondes avec les fonctions de time.h? car pour tester mes boucles ça me serait bien utile(j'arrive uniquement à afficher des secondes entières).

Mici bcp, en tout cas mon code et plus clair maintenant.

**diogene** · 31/03/2008, 20h28

Code :

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

strncat(Sequence, &Lu, 1);

est inutile : Tu sais où mettre le caractère lu

Code :

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

1
2
3
4
                free(Sequence);
                Sequence=(char *) malloc(sizeof(char) + 1);
                Sequence[0] = Lu;
                Sequence[1] = '\0';

Il ne faut jamais désallouer sequence (sauf à la fin, hors de la boucle) : Dans le buffer actuel Sequence, il y a de la place disponible pour placer ces caractères et d'autres.
Pour éviter ces allocations et désallocations à chaque caractère lu, il faut réutiliser la place allouée précédemment. On ne réalloue que si le buffer devient trop petit. On l'agrandit alors (de 1 ou même de plus) et on dispose d'une place suffisante pour maintenant et disponible pour plus tard. Les (ré)allocations deviennent alors très rares.
Regarde le code que je t'ai posté et qui est basé sur cette idée.
On peut améliorer également Calculer_nb_bit puisqu'on connait le nombre actuel de bits, mais, c'est à voir plus tard

**Darksnakes** · 01/04/2008, 19h22

Effectivement le strncat ne sert plus.
Par contre en ce qui concerne le code que tu a écris et pour etre sur d'avoir compris : au lieu de liberer l'espace et de réallouer un espace plus petit, tu utilise un entier pour dire le nombre de caractère significatif (Lsequence), et tu gardes la longeur allouée dans LSequenceAlloc.

Et une question est ce que faire X reallocation de 1 ou faire une reallocation de X prend le même temps?

Si j'ai bien compris, je vais aller tester.

En ce qui concerne calculer_nb_bit c'est la partie entière supèrieur de Log(Code)/Log(2) (pour les valeur entre 2^9 et 2^16) mais je sais pas comment faire. Mais je crois aussi quil existe une fonction en c qui calcul le nombre de bit sur le quel un nombre décimal peut etre écrit en binaire, faut juste que je cherche.

En tout cas merci pour tous ces conseils^^ mon programme devient beaucoup plus claire

Bonne soirée

Yann

**diogene** · 01/04/2008, 20h35

Et une question est ce que faire X reallocation de 1 ou faire une reallocation de X prend le même temps?

non,c'est sur. L'ordre de grandeur entre les deux est un facteur X

Mais je crois aussi quil existe une fonction en c qui calcul le nombre de bit sur le quel un nombre décimal peut etre écrit en binaire, faut juste que je cherche

tu es dans un cas bien particulier : Si le nombre actuel de bits est n, le nombre futur est soit inchangé soit n+1.
On peut envisager par exemple quelque chose comme :

Code :

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

1
2
3
4
5
6
7
int Limites [] = {255,511,1023,2047,4095,8191,16383,32767};
...
int Calculer_nb_bit(int i_Code, int n_bits)
{
   if(n_bits == 16) return 16; //??   
   return   i_Code > Limites[n_bits-8]  ?  n_bits+1 : n_bits;
}

**Darksnakes** · 02/04/2008, 19h05

ben en fait nbbit dépend de code et code ne fait que augmenter au fur et à mesur de l'algo donc

Code :

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

1
2
3
int Calculer_nb_bit(int i_Code){
 return ceil(log(i_Code)/log(2));
} marche

j'ai tester et ça marche comme j'ai besoin sinon j'ai fait les changements concernant le realloc et ça marche niquel

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
 
void Compresser_lzw(char * i_Nom_fichier_in, char * i_Nom_fichier_out)
{
     FILE * Fichier_compresse;
     FILE * Curseur;
     char * Sequence =NULL;
     char  Lu;
     t_Liste * Dico[MODULO_HACH] = {NULL};
     int Code = CODE_DEBUT;
     int Code_Attente;
     int Code_Seq;
     int Nb_bit=NB_BIT_DEBUT;
     int Nb_bit_temp=Nb_bit;
     int Taille_seq=1;//Taille_seq-1 = nombre de caractère significatif.
     int Taille_alloc=0;//taille de l'espace disponnible dans Sequence
     int i;
     Fichier_compresse = fopen(i_Nom_fichier_out, "w");
     Curseur = fopen(i_Nom_fichier_in, "r");
     while (fread(&Lu, sizeof(char), 1, Curseur) == 1)
       {   //si il n'y a pas assez d'espace alloué pour l'ajout d'un caractère
	    while (Taille_alloc < Taille_seq+1)
	   	{
		Taille_alloc=Taille_seq+1;
	    	Sequence=(char *) realloc(Sequence,(Taille_alloc) * sizeof(char));
		}
            	Sequence[Taille_seq-1]=Lu;
            	Taille_seq++;
            	Code_Seq = Est_apprise(Sequence,Taille_seq-1,Dico);
	    if  (Code_Seq != -1)
             //si on connais la sequence, on met son code en Attente.
	      {
	        Code_Attente = Code_Seq;
	      }
            else
                {
     //sinon on l'apprend
		Apprendre_sequence(Sequence,Taille_seq-1,Code, Dico);
                ecrire_x_bit(Code_Attente, Nb_bit, Fichier_compresse);
                Code++;
                Nb_bit_temp = Calculer_nb_bit(Code);
                if (Nb_bit != Nb_bit_temp)
                   {
			ecrire_x_bit (CODE_BIT_SUP, Nb_bit, Fichier_compresse);
                        Nb_bit = Nb_bit_temp;
                    }
		//on place le code du caractère lu en attente
                Sequence[0] = Lu;
		Taille_seq=2;
                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);
                           //on se remet dans l'état initial.
                           Code = CODE_DEBUT;
			   Nb_bit=NB_BIT_DEBUT;
			   Nb_bit_temp=Nb_bit;
                           Taille_seq=1;
                           }
 
 
                }
     }
//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);
Vider_dico(Dico);
}

par contre une question pour le realloc, suis je obliger de passer par un pointeur intermédiaire?

sinon j'ai trouvé la source de lenteur de mon programme, ça venait enfait de ma fonction de hachage et de la taille de mon tableau qui donnait pas une bonne répartition de mes sequences , je les donc changé et depuis ça marche bien (8 seconde au lieu de 3 minutes) :

Code :

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

1
2
3
4
5
6
7
8
 
int Hacher(char* i_Sequence, int i_Taille_seq) {
    int i;
    int Cle=0;
    for(i=0;i<i_Taille_seq;i++)
    {Cle=((Cle*2)+(unsigned char) i_Sequence[i])% MODULO_HACH;}
    return Cle;
}

et une dernière question : est ce que strncpy va copier n caractères ou il s'arrete au premier caractère null si jamais il se trouve dans les n premier caractères?

bon merci bine maintenant je vais essayer d'optimiser la decompression de la même façon

bonne soirée

Yann

**contremaitre** · 03/04/2008, 11h24

Envoyé par Darksnakes

et une dernière question : est ce que strncpy va copier n caractères ou il s'arrete au premier caractère null si jamais il se trouve dans les n premier caractères?

char *strncpy (char *dest, const char *src, size_t n);
Dans le cas où la longueur src est inférieure à n, la fin de dest sera remplie avec des caractères nuls.

**diogene** · 03/04/2008, 15h44

ben en fait nbbit dépend de code et code ne fait que augmenter au fur et à mesur de l'algo donc

Code :

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

1
2
3
nt Calculer_nb_bit(int i_Code){
 return ceil(log(i_Code)/log(2));
}

Oui. C'est pourquoi il n'est utile d'appeler la fonction que si code change. Si code change, nbbit ne change pas ou augmente de 1. Comme je connais la valeur courante de nbbit, il est facile de calculer la nouvelle valeur sans passer par un log.

par contre une question pour le realloc, suis je obliger de passer par un pointeur intermédiaire?

Le pointeur intermédiaire permet de rétablir la situation en cas d'échec de la réallocation.
Personnellement, je ne m'encombrerais pas d'un

Code :

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

1
2
3
4
5
while (Taille_alloc < Taille_seq+1)
{
  Taille_alloc=Taille_seq+1;
  Sequence=realloc(Sequence,Taille_alloc);
}

qui est inutile, Taille_seq ne pouvant être supérieur à Taille_alloc.
Et pour réduire les cas de réallocation, j'augmenterais franchement la taille allouée

Code :

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

Taille_alloc += 100; // par exemple

**Darksnakes** · 04/04/2008, 20h00

Envoyé par diogene

Personnellement, je ne m'encombrerais pas d'un

Code :

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

1
2
3
4
5
while (Taille_alloc < Taille_seq+1)
{
  Taille_alloc=Taille_seq+1;
  Sequence=realloc(Sequence,Taille_alloc);
}

qui est inutile, Taille_seq ne pouvant être supérieur à Taille_alloc.
Et pour réduire les cas de réallocation, j'augmenterais franchement la taille allouée

Code :

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

Taille_alloc += 100; // par exemple

Oui effectivement, je sais pas pourquoi j'ai mis un while.

Sinon je suis en pleine optimisation de mon decompression.
Mais j'ai un soucis sur mes free, il me met :

Code :

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

1
2
 
*** glibc detected *** ./lzw: free(): invalid pointer: 0x080cb028 ***

et ça se produit sur

Code :

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

1
2
3
 
if (Dico[i].Sequence != NULL)
			free(Dico[i].Sequence);

Code :

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

1
2
 
t_Seq_Taille * Dico=(t_Seq_Taille *)malloc(pow(2,16)*sizeof(t_Seq_Taille));

Code :

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

1
2
3
4
5
 
typedef struct Seq_Taille  {
			char* Sequence;
			int Taille;
			}t_Seq_Taille;

d'ou peu venir le soucis?

voici le code (il est en cours d'optimisation, mais il marche sur les peites images)

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
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "lire_bit.h"
#include "dico.h"
#include "math.h"
#include "decompressionlzw.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)
	{
        fwrite(&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)
        	{
         		fwrite(&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);
}

Merci d'avance

Yann

[EDIT]
Remplacement dans le dernier code de la variable Code par Codec. Motif : fonctionnement des balises code. Diogene
[/EDIT]

**diogene** · 05/04/2008, 12h14

Code :

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

1
2
if (Dico[i].Sequence != NULL)
   {free(Dico[i].Sequence);}

Il est imprudent de laisser ce pointeur pointer dans le vide. On n'a aucun moyen de tester ultérieurement sa validité.

Code :

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

1
2
3
4
5
if (Dico[i].Sequence != NULL)
{
   free(Dico[i].Sequence);
   Dico[i].Sequence = NULL;
}

**Darksnakes** · 05/04/2008, 14h02

merci pour les balises, j'avais pas fait attention^^

en ce qui concerne le free, je pensait que ça mettait le pointeur a NULL, je viens d'apprendre quelquechose.

Mais j'ai aussi remarqué d'autre petites erreurs dans mon programme? je modifie et je tiens au courant

bonne journée

Yann

**walido_mkacha5** · 29/12/2010, 11h51

Bonjour DarkSnakes

En essayant de compiler votre programme la fonction Lire_x_bits n'est pas définis ,pouvez vous l'ajouter dans le but de tester votre programme,merci d'avance.

PS: Votre travail est impecable

Probleme Algorithme LZW : trop lent

C

Discussions similaires

Partager

Partager