Compression Huffman avec LZ77 - Page 3

Quelles sont ces fonctionnalités ?

Le LZMA en serait une. Sauf avec Winelib éventuellement. (Wine tout court n'est pas une solution, car spécifique x86.)
Maintenant, la raison pour laquelle c'est Win32 only est:
* les extensions de M$VC. Je me tape quelques warnings en compilant avec g++, et le programme résultant plante. Je n'ai pas encore réussi à trouver d'où vient le plantage.
* les objets COM. Quelle idée d'utiliser ça dans un logiciel en C++ qui pourrait très bien utiliser les objets natifs du C++.

Leur exemple du chapitre 6 n'est pas compilable et quand j'arrive à le compiler le compresseur et le décompresseur ne fonctionnent pas.

Il faut partir de LzmaTest.c. Il a sauté pas mal d'étapes dans son readme.

Ah je l'ai pas LzmaTest.c, tu peux me donner le lien?

J'arrête le compresseur arithmétique ça fonctionne vraiment pas.

C'est dans le SDK LZMA.

J'ai essayé de réaliser un Huffman progressif et c'est normal que les taux soit un tout petit peu mieux que le Huffman semi-adaptatif?

Par contre j'ai un assez gros problème, je possède les structures:

//Définition d'une feuille
typedef struct Sheet {
  BOOL noeud;              //TRUE=Noeud, FALSE=Feuille
  
  union {
    unsigned char data;    //Donnée d'une feuille
    struct Noeud *ptr;     //Pointeur sur un autre noeud
  } U_Sheet;
  
} H_Sheet;

//Définition d'un noeud
typedef struct Noeud
{
  H_Sheet FDroite;          //Feuille droite
  H_Sheet FGauche;          //Feuille gauche
  char CodeNoeud [MAXCODE];
} H_Noeud; 

Et dans une fonction j'alloue la mémoire à une feuille ou noeud de cette façon:
H_Noeud *PtrNoeud=((H_Noeud *) malloc (sizeof (H_Noeud)));

Mais je voudrais effacer complètement l'arbre, pour ça j'ai au moins un pointeur qui pointe sur ça racine et j'ai cette fonction:

H_Noeud *HUFF2_DeleteTree (H_Noeud *PtrRacine)
{  
  if (PtrRacine)
  {
    if (PtrRacine->FGauche.U_Sheet.ptr) PtrRacine->FGauche.U_Sheet.ptr=HUFF2_DeleteTree ((H_Noeud*)(PtrRacine->FGauche.U_Sheet.ptr));
    if (PtrRacine->FDroite.U_Sheet.ptr) PtrRacine->FDroite.U_Sheet.ptr=HUFF2_DeleteTree ((H_Noeud*)(PtrRacine->FDroite.U_Sheet.ptr));
    free (PtrRacine);
  }
  return NULL;
}

Or je ne comprend pas le programme plante lamentablement.

Parce que malloc n'initialise pas tes pointeurs à 0 (NULL).

Non, parce que free ne teste pas pour toi si c'est un noeud ou une feuille.

OK j'ai remarqué ça, j'ai donc recodé mes algos et c'est plus rapide et plus facile à gérer.

C'est vraiment normal que j'ai les même taux de compression en huffman semi-adaptatif et huffman adaptatif?

Aahhhhhhhhh
Après avoir redéveloppé tous les algos pour que ça soit plus facile à gérer et plus rapide j'ai réalisé une nouvelle structure:

//Arbre
typedef struct H_Tree {
  H_Tree *FGauche;
  H_Tree *FDroite;
  
  H_Tree *ptr;
    
  BOOL noeud;
  unsigned char ascii_code;
  unsigned long code;
  unsigned char bits; 
};

//Table ASCII
typedef struct {
  H_Tree donnee;
  
  unsigned long freq;
  BOOL codifie;
  unsigned char ascii_code;
  unsigned long code;
  unsigned char bits;
} H_ASCII;

Pour réaliser un arbre je procéde de cette façon:

//Création de l'arbre
int HUFF_MakeTree (H_ASCII *Table_ASCII, unsigned short DimAscii, H_Tree **PtrRacine)
{
  H_ASCII tmp_table;           //Table temporaire
  H_Tree *PtrNoeud;
  
  BOOL insert;
  unsigned short index;
  unsigned short i, j;
  
  //Parcours fréquences ASCII ordre croissant
  for (i=DimAscii-1; i>0; i--)
  {
    //Allocation pour noeud
    PtrNoeud=(H_Tree *)malloc (sizeof (H_Tree));
    PtrNoeud->FGauche=(H_Tree *)malloc (sizeof (H_Tree));
    PtrNoeud->FDroite=(H_Tree *)malloc (sizeof (H_Tree));
    
    //Erreur out of memory
    if (PtrNoeud==NULL) return 0;
    
    //Partie droite (plus petite fréquence)
    memcpy (PtrNoeud->FDroite, &Table_ASCII [i].donnee, sizeof (H_Tree));
    //Partie gauche (plus grande fréquence)
    memcpy (PtrNoeud->FGauche, &Table_ASCII [i-1].donnee, sizeof (H_Tree));
    
    //Cumul des données
    //Ajoute les fréquences
    tmp_table.freq=Table_ASCII [i].freq+Table_ASCII [i-1].freq;
    tmp_table.donnee.noeud=true;
    tmp_table.donnee.ptr=PtrNoeud;
    
    //Reclassement du noeud dans la table
    for (j=i, insert=false; (j>0) && (!(insert)); j--)
      //Redéfinition de la table ASCII (enleve item)
      if (Table_ASCII [j-1].freq < tmp_table.freq)
        *(Table_ASCII+j)=*(Table_ASCII+j-1);
      else {
        insert=true;
        index=j;}
    
    if (!insert) index=0;
    
    //Combine ASCII
    *(Table_ASCII+index)=tmp_table;
  }
  
  //Création du pointeur vers la racine de l'arbre
  *PtrRacine=PtrNoeud;
  
  //Pas d'erreur
  return -1;
}

Et donc enfin pour effacer un arbre je réalise cette fonction, théoriquement elle doit fonctionner? Si c'est pas le cas pourquoi ça plante?

//Suppression d'un arbre de huffman.
H_Tree *HUFF2_DeleteTree (H_Tree *arbre)
{
  if (arbre->noeud && arbre)
  {
    if (arbre->FGauche && (arbre->FGauche->noeud)) arbre->FGauche=HUFF_DeleteTree (arbre->FGauche);
    if (arbre->FDroite && (arbre->FDroite->noeud)) arbre->FDroite=HUFF_DeleteTree (arbre->FDroite);
    free (arbre);
  }
  
  return NULL;
}

Après des recherches et des recherches je ne trouve pas de solutions, quand je pense que j'ai tout redéveloppé pour ça.

Et si tu utilisais un débogueur pour comprendre d'où vient ton bogue?

Ouai mais c'est pas top mon truc les débogueur, y en a un dans DevC++ mais je sais pas m'en servir.
Et j'ai pas Linux redHat.

Si tu avais lu le site, tu verrais que ça tourne aussi sous Cygwin (qui, soit dit en passant, est également un produit de Red Hat hébergé sur sources.redhat.com).

geogeo
: Ouai mais c'est pas top mon truc les débogueur, y en a un dans DevC++ mais je sais pas m'en servir.

C'est vrai que débugger par forum interposé c'est plus ton truc

Et je te garantis que tu trouverais la solution très vite avec un débuggeur approprié, surtout que ton pb est simple et serait immédiatement détecté par un débuggeur détectant les accès à NULL... (comme débuggeur tu as soit Visual C++, soit DevC++, soit gdb en ligne de commande [avec Cygwin, par exemple], soit KDevelop sous Linux, etc...)

Ouai je viens de lancer le débuggeur et il me dit erreur de segmentation?
De plus il me renvoie une variable PtrRacine avec un contenu tordus. Il semble que mon erreur soit dû des pointeurs qui devrait être NULL mais qui ne le sont pas.

geogeo
: Ouai je viens de lancer le débuggeur et il me dit erreur de segmentation?

Et il a bien raison, parce que c ce qui se passe.

De plus il me renvoie une variable PtrRacine avec un contenu tordus.

Il ne te dit pas qu'il ne peut pas accéder au contenu? (jamais utilisé DevC++)

Il semble que mon erreur soit dû des pointeurs qui devrait être NULL mais qui ne le sont pas.

... ou plutôt le contraire

Je ne peux que répéter mon message ./68:

Kevin Kofler :
Parce que malloc n'initialise pas tes pointeurs à 0 (NULL).

C'est à toi d'initialiser tes pointeurs.

ok ok donc après cette ligne je dois ajouter ça non?

//Allocation pour noeud
PtrNoeud=(H_Tree *)malloc (sizeof (H_Tree));
PtrNoeud->FGauche=(H_Tree *)malloc (sizeof (H_Tree));
PtrNoeud->FDroite=(H_Tree *)malloc (sizeof (H_Tree));

A ajouter:

PtrNoeud->FGauche->FGauche=NULL;
PtrNoeud->FGauche->FDroite=NULL;
PtrNoeud->FDroite->FGauche=NULL;
PtrNoeud->FDroite->FDroite=NULL;

Ca pante toujours, j'abandonne, je pige pas désolé.

Essaye d'utiliser calloc à la place de malloc.

Toujours pareil.

La différence est que calloc inclut un memset, donc il ne devrait pas y avoir de pointeurs vers des endroits non définis (mais un NULL).

geo²> et si tu lisais mes posts? je ne te dis pas ce qui fait planter parce que c pas une solution de copier/coller ton code ici plutôt que d'utiliser un débuggeur, mais en tout cas il y a au moins un bug dans le truc qui libère la mémoire, et un débuggeur te montrerait immédiatement où et pkoi ça foire...

Bon après avoir corrigé certaines erreur j'arrive à compresser un petit peu mais ça plante toujours, non pas instantanément mais après un temps de compression.

Donc voici le code de compression:

//Application de l'algorithme
int HUFF2_Compress (H_Tree **PtrRacine, H_ASCII *Table_ASCII, unsigned short &DimAscii, FILE *input, FILE *output)
{
  //Variables fichier
  unsigned char c;    //Caractère
  unsigned char byte=0;
  unsigned char start=0;
  
  //Table ASCII temporaire de sauvegarde
  H_ASCII *table_sav=(H_ASCII *)malloc (sizeof (H_ASCII)*ASCII_MAX);
  
  //Parcours fichier
  while (!feof (input))
  {
    //Caractère en cours
    c=fgetc (input);
    
    //Fin du fichier
    if (feof (input)) break;
    
    //Ecriture caractère avec le code de Huffman progressif
    if (DimAscii>1)
    {
      //Ecriture code de Huffman
      if (HUFF2_FindChar (Table_ASCII, c))
        BitWrite (Table_ASCII [c].code, byte, start, Table_ASCII [c].bits, output);
      else
        BitWrite (c, byte, start, 8, output);
    }
    //Ecriture simple caractère
    else
    {
      //Simple caractère
      BitWrite (c, byte, start, 8, output);
    }
    
    //Copie table si au moins 1 caractère
    if (DimAscii)
      HUFF2_CopyTable (table_sav, Table_ASCII, DimAscii);
    
    //Ajoute fréquence
    HUFF2_AddFreq (Table_ASCII, DimAscii, c);
    HUFF2_CopyTable (Table_ASCII, table_sav, DimAscii);
    
    //Si plus d'un caractère
    if (DimAscii>1)
    {                  
      //Création de l'arbre
      HUFF_MakeTree (Table_ASCII, DimAscii, PtrRacine);
      
      //Codification
      (*PtrRacine)->code=0; (*PtrRacine)->bits=0;
      HUFF_CreateCode (Table_ASCII, *PtrRacine);
      
      //Efface ancien arbre
      //printf ("%u - %lu\n", DimAscii, *PtrRacine);
      
      //PLANTE à CAUSE DE CETTE LIGNE
      *PtrRacine=HUFF2_DeleteTree (*PtrRacine);
    }
  }
  
  //Octet restant
  if (start!=0)
    //Ecriture octet
    fputc (byte, output);
    
  //Libère mémoire
  //HUFF2_DeleteTree (*PtrRacine);
  free (table_sav);
}

La fonction qui créer l'arbre:

//Création de l'arbre
int HUFF_MakeTree (H_ASCII *Table_ASCII, unsigned short DimAscii, H_Tree **PtrRacine)
{
  H_ASCII tmp_table;           //Table temporaire
  H_Tree *PtrNoeud;
  
  BOOL insert;
  unsigned short index;
  unsigned short i, j;
  
  //Parcours fréquences ASCII ordre croissant
  for (i=DimAscii-1; i>0; i--)
  {
    //Allocation pour noeud
    PtrNoeud=(H_Tree *)malloc (sizeof (H_Tree));
    PtrNoeud->FGauche=(H_Tree *)malloc (sizeof (H_Tree));
    PtrNoeud->FDroite=(H_Tree *)malloc (sizeof (H_Tree));
    
    PtrNoeud->FGauche->FGauche=NULL;
    PtrNoeud->FGauche->FDroite=NULL;
    PtrNoeud->FDroite->FGauche=NULL;
    PtrNoeud->FDroite->FDroite=NULL;
    PtrNoeud->FGauche->noeud=false;
    PtrNoeud->FDroite->noeud=false;
    
    //Erreur out of memory
    if (PtrNoeud==NULL) return 0;
    
    //Partie droite (plus petite fréquence)
    memcpy (PtrNoeud->FDroite, &Table_ASCII [i].donnee, sizeof (H_Tree));
    //Partie gauche (plus grande fréquence)
    memcpy (PtrNoeud->FGauche, &Table_ASCII [i-1].donnee, sizeof (H_Tree));
    
    //Cumul des données
    //Ajoute les fréquences
    tmp_table.freq=Table_ASCII [i].freq+Table_ASCII [i-1].freq;
    tmp_table.donnee.noeud=true;
    tmp_table.donnee.ptr=PtrNoeud;
    
    //Reclassement du noeud dans la table
    for (j=i, insert=false; (j>0) && (!(insert)); j--)
      //Redéfinition de la table ASCII (enleve item)
      if (Table_ASCII [j-1].freq < tmp_table.freq)
        *(Table_ASCII+j)=*(Table_ASCII+j-1);
      else {
        insert=true;
        index=j;}
    
    if (!insert) index=0;
    
    //Combine ASCII
    *(Table_ASCII+index)=tmp_table;
  }
  
  //Création du pointeur vers la racine de l'arbre
  *PtrRacine=PtrNoeud;
  
  //Pas d'erreur
  return -1;
}

Et enfin la focntion qui doit théoriquement effacer un arbre.

//Suppression d'un arbre de huffman.
H_Tree *HUFF2_DeleteTree (H_Tree *arbre)
{
  if (arbre && arbre->noeud)
  {
    if (arbre->FGauche && (arbre->FGauche->noeud)) arbre->FGauche=HUFF2_DeleteTree (arbre->FGauche);
    if (arbre->FDroite && (arbre->FDroite->noeud)) arbre->FDroite=HUFF2_DeleteTree (arbre->FDroite);
    free (arbre);
  }
  
  return NULL;
}

Le débogeur ne m'indique plus rien si ce n'est Segmentation de la mémoire maius sans pointer sur une ligne ou afficher une variable. Je ne vois vraiment pas mon ou mes erreurs.

geogeo :
Le débogeur ne m'indique plus rien si ce n'est Segmentation de la mémoire maius sans pointer sur une ligne ou afficher une variable. Je ne vois vraiment pas mon ou mes erreurs.

Visual C++ rulezzz
Mais tu peux toujours trouver l'endroit où ça plante en mettant plein de breakpoints (et en faisant par dichotomie).

geogeo :
Le débogeur ne m'indique plus rien si ce n'est Segmentation de la mémoire maius sans pointer sur une ligne ou afficher une variable. Je ne vois vraiment pas mon ou mes erreurs.

Probablement un plantage dans une librairie système, pour laquelle M$ n'inclut aucune information de débogage. Et de toute façon, le problème n'est pas là. Fais un backtrace (commande bt) et tu auras la ligne de ton code qui est à l'origine de l'erreur.

pour laquelle M$ n'inclut aucune information de débogage

Si, en tout cas pour Visual Studio