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

[DaZumba]

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]

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]

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]

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

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]

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.