Bonjour voila, j'essai d'implémenter la compression de huffman dans un archiveur (qui lui fonctionne très bien), j'ai testé deux algorithmes de huffman (dont un présent sur ce site) et a chaque fois c'est pareille: a la décompression, ca me rajoute un ou deux caractère a la fin du fichier qui n'on rien a faire la ! J'ai biensur testé indépendement de mon archiveur. Quelqu'un sait d'ou cela peut venir ?? voici un des deux codes que j'ai testé:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct arbre
{
unsigned char m;
unsigned long z;
struct arbre *pere, *fg, *fd;
};
struct arbre ar[512], *deb;
void tableau(void);
void code(FILE *e, struct arbre *h, struct arbre *fils);
void ecrire(FILE *e, int b);
int lire(FILE *s);
char octet;
int octet1, p;
void tableau(void)
{
int i, n1 = 256;
while(1)
{
struct arbre *u = NULL, *v = NULL;
for (i=0; i<n1; i++)
if (ar + i != u)
if ((ar[i].z > 0) && (ar[i].pere == NULL)){
if ((u == NULL) || (ar[i].z < u->z))
{
if ((v == NULL) || (u->z < v->z))
v = u;
u = ar + i;
}
else if ((v == NULL) || (ar[i].z < v->z))
v = ar + i;
}
if (v == NULL)
{
deb = u;
break;
}
u->pere = ar + n1;
v->pere = ar + n1;
ar[n1].z = u->z + v->z;
ar[n1].fd = u;
ar[n1].fg = v;
n1++;
}
}
void code(FILE *e, struct arbre *h, struct arbre *fils)
{
if (h->pere != NULL)
code(e, h->pere, h);
if (fils)
{
if (fils == h->fd)
ecrire(e, 0);
else if (fils == h->fg)
ecrire(e, 1);
}
}
void ecrire(FILE *e, int b)
{
if ((p == 8) || (b == -1))
{
fputc(octet, e);
p = 0;
}
octet = (octet << 1) | b;
p++;
}
int decode(FILE *s, struct arbre *h)
{
while (h->fd != NULL)
if (lire(s))
h = h->fg;
else
h = h->fd;
return( h->m );
}
int lire(FILE *s)
{
int r;
if (p == 8)
{
octet1 = fgetc(s);
p = 0;
}
r = octet1 & 0x80;
octet1 <<= 1;
p++;
return(r);
}
int compression(FILE *s)
{
FILE *e;
int c, f = 0;
unsigned long n = 0;
/*if ((s = fopen(entree,"rb"))==NULL) {printf("fichier vide\n");return 0;};*/
e = fopen("temp","wb");
while (((c = fgetc(s)) != EOF))
{
c &= 255;
if (ar[c].z == 0)
{
ar[c].m=c;
f++;
}
ar[c].z++;
n++;
}
fwrite(&n, sizeof(n), 1, e);
fwrite(&f, sizeof(f), 1, e);
for (c=0; c<256; c++)
{
if (ar[c].z > 0)
{
fwrite(&ar[c].m, sizeof(char), 1, e);
fwrite(&ar[c].z, sizeof(unsigned long), 1, e);
}
}
tableau();
fseek(s, 0L, 0);
while ((c=fgetc(s)) != EOF)
code(e, ar+(c&255), NULL);
ecrire(e, -1);
fclose(e);
fclose(s);
return 0;
}
int decompression(FILE *s)
{
FILE *e;
int f = 0;
unsigned char z;
unsigned long n = 0;
e = fopen("temp","rb");
p = 8;
fread(&n, sizeof(n), 1, e);
fread(&f, sizeof(f), 1, e);
while (f--)
{
fread(&z, sizeof(char), 1, e);
ar[z].m = z;
fread(&ar[z].z, sizeof(unsigned long), 1, e);
}
tableau();
while (n--){
fputc(decode(e, deb), s);
}
fclose(e);
fclose(s);
return 0;
}