besoin de beaucoup d'aide sur la réalisation d'un codage Huffman en C

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 Page Suivante Page Précédente Bas de page
Auteur	Sujet : besoin de beaucoup d'aide sur la réalisation d'un codage Huffman en C

Emmanuel Delahaye

C is a sharp tool

Reprise du message précédent :

wadcyr8_197 a écrit :

je viens de faire lis ce post à un gars de ma classe et il dit qu'il a eu besoin du "back to basic" aussi, par ailleurs, je ne crois pas avoir fait d'impasse, mais je reconnais avoir eu du mal à suivre le cour en amphi de 100 !!!!

Suivre les cours c'est bien, mais l'important est de s'entrainer un max chez soi (ou sur les machines de la fac, mais j'y crois pas trop...). Il est aussi indispensable d'avoir un support de cours sérieux (poly, bouquin, site web), et de poser des questions sur le cours (les forums sont faits pour ça et on a le temps d'aller en profondeur).

Par contre, lors d'un exercice (surtout aussi complexe qu'un codeur/encodeur de Huffman), les bases doivent être acquises (de la façon que j'ai indiqué avant), et on doit plus se concentrer que sur le problème (conception, réalisation, test). A ce moment là, le rôle du forum est d'aider au debuggage ou à la résolution de certains détails ardus, mais pas de faire un cours détaillé. C'est trop tard.

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/

Publicité

pains-aux-raisins

Fatal error

Emmanuel Delahaye a écrit :

+1 :jap:

wadcyr8_197

Emmanuel Delahaye a écrit :

poser les questions en cours c'est bien, mais quand on est en petite classe ça passe, en amphi, les profs aiment pas
ensuite, à part les pointeurs et les allocations mêmoires (malloc), mes bases sont pas trop catastrophique, mais même l'explication du prof de td m'a encore plus embrouillé !

Emmanuel Delahaye

C is a sharp tool

wadcyr8_197 a écrit :

poser les questions en cours c'est bien, mais quand on est en petite classe ça passe, en amphi, les profs aiment pas <...>

C'est pour ça que j'insiste sur le rôle des forums à ce moment là. T'as pas compris un truc en cours, tu rééssayes chez toi. En cas de problème -> forum. On est là pour ça...

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/

wadcyr8_197

Emmanuel Delahaye a écrit :

C'est pour ça que j'insiste sur le rôle des forums à ce moment là. T'as pas compris un truc en cours, tu rééssayes chez toi. En cas de problème -> forum. On est là pour ça...

ce qu'il y a c'est que je pensais avoir compris puisque le td qu'on a fait j'y arrivais, mais arriver a ce truc je m'apercois que ce n'etait pas le cas !

edit : miracle j'ai réussi à faire marcher ma table de fréquence à partir de mon prog original ça donne ça :

Code :

#include<stdio.h>
#include<string.h>
struct tableau2 /* on def une structure de table a deux lignes : une de char */
{ /* et une de floattants */
char carac;
float freq;
};
struct tableau2 tabf[256];
// la fonction appartient verifie qu'un char de la phrase à coder est ou non dans la table de fréquence
int appartient (char s, struct tableau2 tabf2[])
{
int i;
for ( i = 0 ; i <256 ;i++ )
{
if (tabf2[i].carac == '\0')
break;
if ( s == tabf2[i].carac )
return i;
}
return -1;
}
//la fonction frequence cree la table de frequence
// cependant, on rentre d abord dans le tableau les occurrences des lettres
// et on divise a la fin par la longueur de la chaine pour avaoir les freq
struct tableau2 * frequence (char phrase[])
{
int cmp=-1; // compter pour savoir dans quelle colonne on se situe dans le tableau
int i;
int N=strlen(phrase);
//printf("sizeof : %i \n", N);
for ( i = 0 ; i < N ; i++ )
{
//printf("i : %i \n", i);
int temp;
temp=appartient(phrase[i], tabf);
if ( temp == -1 )
{
cmp += 1;
tabf[cmp].carac=phrase[i];
tabf[cmp].freq=1;
}
else
tabf[temp].freq=tabf[temp].freq + 1;
}
//printf("%i \n", cmp);
for ( i = 0 ; i < cmp ; i++ )
{
tabf[i].freq=tabf[i].freq/N; // passage du nombre d occurrence a la freq
printf ("%i : %c, %f \n", i,tabf[i].carac,tabf[i].freq); // affichage du tableau de frequence
}
return tabf;
}
int main (void)
{
//char *phra;
char phrase[]="peter le chien est tres petit";
//printf("Entrez votre phrase : \n" );
//scanf("%s",phra);
//int L=strlen(phra);
//char phrase[L]= *phra;
frequence(phrase);
return 1;
}

merci pour le coup de main :jap:

maintenant je vais passer à la construction de l'arbre en lui même !!! :cry:

Message édité par wadcyr8_197 le 03-01-2005 à 11:24:03

Emmanuel Delahaye

C is a sharp tool

wadcyr8_197 a écrit :

Sinon, pour revenir a l'histoire des 256 competeurs, j'ai relu les posts et je crois que je n'ai pas eu l'explications que j'esperais parce que j'ai pas super bien pose ma question.

Je reprends:

Citation :

Le tableau de compteurs a une taille de 256, donc un index de 0 à 255.
La table des caractères va de 0 à 255. Tu ne remarques rien ?

Ce qu'il fallait remarquer, c'est que les caractères étant numérotés de 0 à 255, ils peuvent servir d'index au tableau.

Le compteur de 'a', c'est tout simplement compteur['a']. Le compteur de 'Z', c'est compteur['Z'].

Il suffit donc de parcourir la chaine caractères par caractères, et d'incrémenter le compteur correspondant :

char const *p = s;

while (*p)
{
compteur[*p]++;
p++;
}

Si tu trouves ça difficile, tu vas mourir avec l'arbre...

Peut être que l'informatique n'est pas ta voie...

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/

wadcyr8_197

Emmanuel Delahaye a écrit :

Je reprends:

Citation :

Le tableau de compteurs a une taille de 256, donc un index de 0 à 255.
La table des caractères va de 0 à 255. Tu ne remarques rien ?

char const *p = s;

while (*p)
{
compteur[*p]++;
p++;
}

Si tu trouves ça difficile, tu vas mourir avec l'arbre...

ok, mais en fait, je m'obtinais sur un truc completement con je partais sur le principe que l'on avait uniquement compteur[0] .... compteur[255] j'avais oublié le fait qu'on pouvait utiliser d'autre denomination !!! :pt1cable: et fatigue ça arrange pas les choses !!!

[citation]Peut être que l'informatique n'est pas ta voie...[/citation]
je pense que si, mais faut juste que je prenne l'habitude sur le mode de raisonnement qui ne correspond pas au mien.
ps : je suis pas en info mais en télécoms

rolphin

Les données pouvant être lu depuis n'importe quoi, je pense qu'il serait judicieux
de faire un test sur la longueur et non pas sur la valeur de p.
Un 0 terminal est beaucoup trop vite oublié.

Code :

char const *p = s;
while (*p)
{
compteur[*p]++;
p++;
}

Il faut penser à utiliser la longueur qu'un eventuel read() nous aurais retourné...

Code :

unsigned int len;
char const *p = s;
while (len--)
{
compteur[*p]++;
}

Emmanuel Delahaye

C is a sharp tool

rolphin a écrit :

Les données pouvant être lu depuis n'importe quoi, je pense qu'il serait judicieux
de faire un test sur la longueur et non pas sur la valeur de p.

Il s'agit de tester la valeur de *p. (0 en l'occurence). En amont, il faut s'assurer de fournir une chaine conforme.

Citation :

Un 0 terminal est beaucoup trop vite oublié.

Si la chaine n'est pas conforme, il n'y a aucun moyen de connaître sa longueur.

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/

rolphin

Citation :

Il s'agit de tester la valeur de *p. (0 en l'occurence). En amont, il faut s'assurer de fournir une chaine conforme.

On peut très bien travailler sur des données ou le 0 est une donnée et pas
un marqueur...

Citation :

Si la chaine n'est pas conforme, il n'y a aucun moyen de connaître sa longueur.

D'ou l'utilité de par exemple le très connu Content-Length...
Il est _toujours_ mieux de travailler avec des tailles et non pas
de vérifier l'éventuelle présence d'un O terminal.
En plus on gagne un caractère à chaque fois, et ca c'est de la balle.

De toute façon c'est la faute aux fonctions de stdio dont l'api est
vraiment mal faite, car tout vient d'un read() qui lui renvoi la taille du block lu...
Pourquoi avoir choisi de cacher cette information ?
Cela reste un non sens...

Si strcpy "and friends" n'avaient jamais existé, je me demande bien avec quoi nous nous amuserions actuellement...

Publicité

pains-aux-raisins

Fatal error

roooohhh le gentil troll [:ddr555]

Message édité par pains-aux-raisins le 04-01-2005 à 17:23:24

Emmanuel Delahaye

C is a sharp tool

[citation=936941,40,9]On peut très bien travailler sur des données ou le 0 est une donnée et pas un marqueur...[/citation]
Ici, il était question de chaines C...

Citation :

Si la chaine n'est pas conforme, il n'y a aucun moyen de connaître sa longueur.

On gagne rien du tout en taille, car il faut bien stocker la longueur quelque part, par contre, on gagne en vitesse, ç'est sûr.

Ceci devrait t'interesser:

http://mapage.noos.fr/emdel/clib.htm
Module FSTR (Flexible Strings)

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/

rolphin

Citation :

Ceci devrait t'interesser:
http://mapage.noos.fr/emdel/clib.htm
Module FSTR (Flexible Strings)

En effet j'utilise des stralloc, c'est exactement pareil ;]

L'énorme avantage c'est qu'en allouant toujours un peu plus on peut
se permettre de boucle de parcours de chaine en apparence pas tres sures,
comme aller voir deux elements plus loin que la fin de la string...

Ou ajouter un 0 terminal sans jamais se soucier de savoir si y'a de la place... y'a toujours de la place.

Tu devrais je pense plus promouvoir ta lib... Ca ferait du bien au monde du C...
J'en ai une aussi basée sur libowfat: http://www.fefe.de/libowfat/

pains-aux-raisins

Fatal error

Emmanuel Delahaye a écrit :

Ici, il était question de chaines C...

Citation :

Si la chaine n'est pas conforme, il n'y a aucun moyen de connaître sa longueur.

Très intéreressant

rolphin

Quand je parlais de taille, je m'interessais au buffer
qui va ëtre rempli par les données. On ne perds plus
le dernier caractère.

Après, en effet non seulement on ne gagne pas de place,
mais on perds de la place, (façon de parler) car la longueur
va être stockée, dans unsigned int ou unsigned long... qui
est plus important qu'un char ...

Donc pour être tout à fait correct, ne pas utiliser de 0 terminal
et de stocker la taille autrepart, ca permet de gagner en vitesse,
de gagner en ''sécurité'' mais on perds un tout petit peu en place.

C'est d'autant plus important lorsqu'on utilise une structure bien
faite contenant, la taille de la string, sa longueur et la taille
effective d'allocation. (ce que fait stralloc, et fstr).

wadcyr8_197

salut tout le monde

merci bien pour le coup de main, j'ai bien avance depuis, j'ai fini mon tableau de frequence et j'ai meme construit mon arbre (enfin presque), je compile correctement, mais j'ai un segmentation fault qui apparait mais pas a chaque fois et quand il commence a me le faire, j'ai juste besoin de mettre un printf dans ma fonction pour que ca passe
Le pire c que quand j'explore le prog avec gdb, l'arbre est bien creer ?!?
donc si quelqu'un a une idee pour ce petit bug :

Sve@r

wadcyr8_197 a écrit :

Oh lalalala !!! T'es tombé dans le pire des cas: un segfault qui apparaît de façon aléatoire et qui disparaît quand tu mets un "printf" en plus.
C'est typique d'un pointeur qui va pointer à un endroit où il n'a plus le droit d'aller (style il balaye un tableau de "n" éléments dans une boucle variant de "0" à "n" )

Sans avoir vu le code, j'envisagerais bien l'idée que, lorsque tu crées un noeud de ton arbre, tu aies oublié de mettre les pointeurs fils à "NULL". Ensuite, quand tu balayes ton arbre, tu dois probablement utiliser une fonction récursive du type

Code :

void balaye(t_arbre *noeud)
{
if (noeud->gauche)
balaye(noeud->gauche);
... traitement du noeud ...
if (noeud->droite)
balaye(noeud->droite);
}

Si mon idée est correcte, quand tu arrives en fin de branche, comme ton dernier noeud n'a pas été bien initialisé, la fonction "balaye" voit que le pointeur gauche (ou droit) n'est pas nul et va chercher à explorer ce pointeur => segfault sauf les cas où le compilo lui a mis "nul" par hasard.
Enfin c'est une idée...

matafan

Compile avec -g, ulimit -c unlimited, capture un core, et debug a partir du core.

wadcyr8_197

j'ai finalement trouvé, c'est juste que le prog, n'aime pas qu'une fonction renvoie un pointeur qui a été défini en local, même si on lui fait un petit malloc !
j'ai donc définit ledit pointeur en global et tout baigne !!!
maintenant faut que je passe à la lecture de l'arbre pour établir la table de codage (fils_gauche=0 et fils_droit=1)
ça va être drole
surtout pour le faire ce soir et réviser mes partiels de la semaine prochaine en même temps !!!

Emmanuel Delahaye

C is a sharp tool

wadcyr8_197 a écrit :

j'ai finalement trouvé, c'est juste que le prog, n'aime pas qu'une fonction renvoie un pointeur qui a été défini en local, même si on lui fait un petit malloc !

Pas normal. A mon avis, il y a un autre problème ou alors tu ne renvois pas la bonne valeur, ou l'allocation n'a pas fonctionné et tu retournes NULL...

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/

Lam's

Profil: bas.

...ou alors, il ne passe pas le pointeur par référence. Donc, le fait de l'allouer dans la fonction ne modifie pas sa valeur dans la fonction appellante.

wadcyr8_197

pourtant, maintenant, tout marche correctement et c'et la seule chose que j'ai changée !

mais le C a ses raisons que la raison ignore

pains-aux-raisins

Fatal error

wadcyr8_197 a écrit :

pourtant, maintenant, tout marche correctement et c'et la seule chose que j'ai changée !

mais le C a ses raisons que la raison ignore

Le C a ses raisons normalisées par la norme ANSI que ta raison ignore

Emmanuel Delahaye

C is a sharp tool

wadcyr8_197 a écrit :

pourtant, maintenant, tout marche correctement et c'et la seule chose que j'ai changée !

Tu as masqué le problème, mais ça ne veut pas dire qu'il est corrigé... En général, ça pète le jour de la démo...

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/

wadcyr8_197

ouais, mais qu'est ce que je peux faire comme test autres que sur machine différente et passer gdb (sachant que avant, avec gdb le seg fault je pouvais le trouver, ce qui n'et plus le cas maintenant) ?

Lam's

Profil: bas.

Postes le code de la fonction qui faisait planter, on va jeter un oeil...

wadcyr8_197

Lam's a écrit :

Postes le code de la fonction qui faisait planter, on va jeter un oeil...

voici, mais je crois que vous allez manquer de chose donc si vous voulez l'intégralité des source pour comprendre, c'et ici : http://www.enseirb.fr/~guizani/projetc/

Code :

/* je rajoute les def ds structures : */
/****************************/
struct noeud {
char *caracteres;
float frequence;
struct noeud *fils_gauche;
struct noeud *fils_droit;
};
/* Un arbre est l'adresse de son noeud racine ou NULL s'il est vide. */
typedef struct noeud * arbre;
/************************************/
#define MAX 256
struct noeud tabf[MAX];
int cmp=-1; /* compteur de longueur de tableau */
arbre tab_arb[MAX];
/* On passe a la construction de l'arbre */
arbre cons_huff ( struct noeud * tab_freq )
{
int i,j;
int compteur=cmp;
arbre temp;
/* conversion de tab_freq en talbeau d'arbre */
for ( i = 0 ; i <= cmp ; i++ )
{
tab_arb[i]=arbre_cree_feuille(tab_freq[i].caracteres,tab_freq[i].frequence);
}
/* contruction de l'arbre */
while ( compteur > 0 )
{
for ( i = 0 ; i <2 ; i++ )
{
for ( j = compteur ; j > 0 ; j-- )
{
if ( noeud_frequence(tab_arb[j]) < noeud_frequence(tab_arb[j-1]) )
{
temp=tab_arb[j];
tab_arb[j]=tab_arb[j-1];
tab_arb[j-1]=temp;
}
}
} /* fin du "petit tri" */
tab_arb[0]=arbre_cons(tab_arb[0], tab_arb[1]);
tab_arb[1]=tab_arb[compteur];
tab_arb[compteur]=NULL;
compteur--;
}
return tab_arb[0];
}

Message édité par wadcyr8_197 le 14-01-2005 à 13:22:00

Lam's

Profil: bas.

Et c'est sur quelle variable que tu faisais un malloc ? (et tu la retournais comment ? )

wadcyr8_197

c'est sur tab_arb que je faisais du malloc
et je la retournais avec le return de fin de fonction

Publicité

Page : 1 2

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

besoin de beaucoup d'aide sur la réalisation d'un codage Huffman en C

Sujets relatifs
[BESOIN AIDE Dreamweaver] Créa Site Web avec Panier de Vente en Ligne	aide : problème pour un compteur de visiteur sur un site
Besoin d'aide pour un exercice.	Principes d'héritage et de polymorphisme... à l'aide !
Aide sur une contrainte d'integrité...	aide pour création forcée d'un fichier txt (et écriture)...
aide de créaion de formulaire	Besoin d'aide requête MySQL
Plus de sujets relatifs à : besoin de beaucoup d'aide sur la réalisation d'un codage Huffman en C

Page générée en 0.137 secondes