Discussion :

[Mac LAK]

Aïe... Va falloir que tu fasses des efforts sur l'indentation, c'est absolument horrible, là... Ca commence dès la première ligne, par les espaces après les "#" (#include, #define)... Va falloir retravailler ça, c'est franchement pas génial à lire. En plus, t'es avare de commentaires, c'est encore plus difficile à lire.

Pour ton problème de récursivité, c'est que tu n'as pas dû correctement arrêter ton algorithme, car c'est bien en général une fonction récursive que l'on utilise pour cette opération.

Ensuite, je suis assez étonné de te voir arrêter arbitrairement la taille de tes codes de Huffman à 8 bits (#define M) : qui t'as dit que c'était le cas ? Ces codes peuvent aller jusqu'à 64 bits, si je me rappelle bien le pire cas possible !

Ensuite, les erreurs que j'ai pu relever :
1) Pas d'assertions ni de tests sur le dépassement du champ "code" de ta structure... Rajoute un "assert( i<8 );" dans le code avant chaque assignation à "tmp->code[i]". Ton débordement peut venir de là.
2) Tu fais un "malloc" sur tmp sans tester le retour. En plus, tu ne libère jamais cette mémoire !! Surtout que tu n'as pas besoin d'un malloc, tu peux utiliser une déclaration "CODE c ;" et utiliser "&c" (adresse de c) si tu veux un pointeur dessus... Pointeur dont tu n'as pas besoin ici, en plus. Bref, là, c'est la grosse zone.
3) Ton parcours d'arbre gauche et droit n'est pas séparé : une fois effectué celui sur le fils gauche, tu vas faire celui sur le fils droit... Et les codes vont se mélanger, car la variable "c" est globale et non pas locale à ta procédure => on ne peut pas utiliser la récursivité "comme ça" dans ces conditions.

Bref, c'est plutôt étrange que ton code arrive à fonctionner, même un peu... Corriges-ça de toute urgence, ça en a vraiment besoin.

a propos, dans ton arbre a toi, tu mettais quoi comme caractere pour les noeud qui ne sont pas des feuilles ??? moi j'ai mis le caractere de code 0 mais j'evite la confusion en testant, quand je parcours l'arbre, si le noeud est une feuille ou non, mais ptet que j'ai oublié un test quelque part et que ca pourrais regler le prob ... ta mis quoi toi ???

J'utilisais une déclaration de ce type pour les noeuds de l'arbre :

Code :

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

1
2
3
4
5
6
7
typedef struct _Node {
  unsigned char C ;        // Valeur du caractère ASCII du noeud
  unsigned long int F ;    // Fréquence du caractère, permet aussi de tester si le noeud est une feuille.
  unsigned long int CF ;   // Cumul des fréquences des deux sous-arbres.
  struct _Node* Left ;     // Sous-arbre gauche.
  struct _Node* Right ;    // Sous-arbre droit.
} TNode ;

Si la fréquence est non-nulle,c 'est une feuille, car les caractères n'apparaissant jamais dans le fichier d'origine n'apparaissent pas non plus dans la structure d'arbre. Si ce n'est pas une feuille, la valeur du caractère n'est même pas examinée (elle devait être à zéro, je pense).
Le cumul des fréquences sert pour l'insertion correcte d'une cellule dans l'arbre. On peut faire sans, mais ça simplifie le code résultant.
Le code de Huffman n'est bien entendu pas stocké, car il est équivalent au parcours de l'arbre (0=Left, 1=Right). Chaque noeud de l'arbre peut être une feuille aussi, avec ou sans sous-arbres.

Pour la phase de compression, j'utilisais une LUT : un tableau contenant tous les codes de Huffman, avec leur longueur (importante dans ce cas). Ainsi, je ne parcourais l'arbre qu'une seule fois.

[ben13]

OK merci

mais la je comprends pas

Ensuite, je suis assez étonné de te voir arrêter arbitrairement la taille de tes codes de Huffman à 8 bits (#define M) : qui t'as dit que c'était le cas ? Ces codes peuvent aller jusqu'à 64 bits, si je me rappelle bien le pire cas possible !

au pire ya 256 caracteres presents dans le texte donc 256 feuilles, la hauteur de l'arbre est donc log2 (256) = 8 ....

alors comment peut-il y avoir des codes plus long que 8 bits ????


autre chose : on est bien obligé d'utiliser une var globale pour la fonction recursive qui calcule le chemin non ???? pke avec un return moi ca marche pas

sinon j'ai rajouté les assert et apparement ca deborde pas

[Mac LAK]

• Il y a des fois où j'ai l'impression que tu ne lis pas complètement ce que je t'écris... C'est assez désagréable.

au pire ya 256 caracteres presents dans le texte donc 256 feuilles, la hauteur de l'arbre est donc log2 (256) = 8 ....

Bien sûr que non...
Ca dépend de la répartition des fréquences et du nombre de caractères réellement présents dans le fichier source.
L'arbre n'est pas équilibré, et de plus, la séparabilité des codes impose que pour coder 256 caractères, tu auras besoin de plus de 8 bits pour certaines valeurs. Ne confonds pas un arbre de codes de Huffman avec un simple arbre binaire, ce n'est pas du tout la même chose.

alors comment peut-il y avoir des codes plus long que 8 bits ????

Essaie de compresser un fichier binaire, tu verras bien. Prends l'exécutable de ton projet, je pense que tu vas avoir une mauvaise surprise.

autre chose : on est bien obligé d'utiliser une var globale pour la fonction recursive qui calcule le chemin non ???? pke avec un return moi ca marche pas

Justement, non : la récursivité implique que toutes les variables sont locales, et certainement pas globales !!
Si ça ne marche pas avec un return, c'est que tu as mal construit ta fonction. Déjà, rien qu'avec les malloc non-vérifiés et non-libérés que tu fais, ça ne peut pas marcher correctement. Tu n'as pas besoin d'allouer dynamiquement, il te suffit de déclarer un tableau "CODE HuffCodes[256]" et de taper là-dedans pour construire tes codes, c'est la manière habituelle pour les obtenir de manière efficace. Toi, tu alloue un nouveau code à chaque itération et en plus, tu écrase le code précédent !!!
Ensuite, tu parcours ton arbre en profondeur et tu construit chaque code lorsque tu arrives à une feuille.

sinon j'ai rajouté les assert et apparement ca deborde pas

Tu les as mis dans les boucles "for", j'espère ? Parcequ'avant ou après, ça n'a aucun intérêt. Vérifie aussi (toujours par assertions) tes "taille_pref". A propos, il faudra mettre "assert(i<M)" plutôt, désolé de cet oubli.
Egalement, vérifie que tu compiles bien avec les assertions activées. Pour le vérifier, introduit en début de la fonction main un "assert(0)" et vérifie que le programme s'arrête bien.

Et essaie de faire un jeu de test comme celui que je t'ai donné quelques posts plus haut. Tant que ton programme ne marchera pas nickel avec chacun de ces fichiers de test, c'est que tu t'es planté dans l'implémentation.

[ben13]

Bien sûr que non...
Ca dépend de la répartition des fréquences et du nombre de caractères réellement présents dans le fichier source.
L'arbre n'est pas équilibré, et de plus, la séparabilité des codes impose que pour coder 256 caractères, tu auras besoin de plus de 8 bits pour certaines valeurs. Ne confonds pas un arbre de codes de Huffman avec un simple arbre binaire, ce n'est pas du tout la même chose.

ok je savais pas que l'arbre etait pas equilibré .... le gros de mes probs vient surement de la alors ... les codes ne doivent pas etre separées ....
Je vais mettre mon M a 64 alors

Justement, non : la récursivité implique que toutes les variables sont locales, et certainement pas globales !!
Si ça ne marche pas avec un return, c'est que tu as mal construit ta fonction. Déjà, rien qu'avec les malloc non-vérifiés et non-libérés que tu fais, ça ne peut pas marcher correctement. Tu n'as pas besoin d'allouer dynamiquement, il te suffit de déclarer un tableau "CODE HuffCodes[256]" et de taper là-dedans pour construire tes codes, c'est la manière habituelle pour les obtenir de manière efficace. Toi, tu alloue un nouveau code à chaque itération et en plus, tu écrase le code précédent !!!
Ensuite, tu parcours ton arbre en profondeur et tu construit chaque code lorsque tu arrives à une feuille.

j'ai enlevé les malloc apres ton conseil j'ai plus de pointeur now mais bon je vais refaire cette fonction dirfferement je vais essayer

Tu les as mis dans les boucles "for", j'espère ? Parcequ'avant ou après, ça n'a aucun intérêt. Vérifie aussi (toujours par assertions) tes "taille_pref". A propos, il faudra mettre "assert(i<M)" plutôt, désolé de cet oubli.

tinkiete elles sont bien dans les for

Il y a des fois où j'ai l'impression que tu ne lis pas complètement ce que je t'écris... C'est assez désagréable.

dsl....je pense que now tu ma filé un max dinfos je vais essayer de bien bosser

merci encore

[ben13]

wait wait wait, si un code peut faire plus de 8 bits, forcement il ne rentre plus dans un unsigned char .......................... je doit tout refaire avec des int ........ enfin je comprends plus la

[Mac LAK]

ok je savais pas que l'arbre etait pas equilibré .... le gros de mes probs vient surement de la alors ... les codes ne doivent pas etre separées ....
Je vais mettre mon M a 64 alors

Pourtant, c'est très clair dans l'algo, cette propriété de l'arbre de Huffman...

j'ai enlevé les malloc apres ton conseil j'ai plus de pointeur now mais bon je vais refaire cette fonction dirfferement je vais essayer

Tant que tu n'utiliseras pas une table, tu seras emm..... par l'obtention des codes.

wait wait wait, si un code peut faire plus de 8 bits, forcement il ne rentre plus dans un unsigned char .......................... je doit tout refaire avec des int ........ enfin je comprends plus la

En tant que flux de bits, effectivement, il ne rentre plus. J'utilisais un "tableau" de 2 entiers longs pour gérer ça, mais tu peux aussi faire un "unsigned char code[64]" et stocker un seul bit par caractère... Ce n'est pas très optimisé, mais ça a l'avantage d'être facile à implémenter.
Et tu comprends maintenant pourquoi j'avais fait un "vrai" fichier de bits et non pas un simple "éclateur/recomposeur" d'octets.

Sur ce, joyeuses fêtes.

[ben13]

merci a toi mais la je crois que jy arriverai pas...

g pas la foi de tout refaire.

merci pour tout bonne fetes a toi aussi 8)

[ben13]

Bon je m'y suis remis et c OK tout marche meme pas de petit bug !!!!

Merci a toi car sans toi j'aurai jamais pensé que la hauteur de l'arbre pouvait etre superieure a 8, j'ai changé ca correctement et maintenant c OK, je me rends compte maintenant que c'est bizarre qu'il y avait aussi peu d'erreur avec un truc faux a ce point ....... (en effet mon arbre quand je compresse mon huff.c est de hauteur 13 .....)

voila merci encore a toi et ptet a bientot

[Mac LAK]

Bon je m'y suis remis et c OK tout marche meme pas de petit bug !!!!

Merci a toi car sans toi j'aurai jamais pensé que la hauteur de l'arbre pouvait etre superieure a 8, j'ai changé ca correctement et maintenant c OK, je me rends compte maintenant que c'est bizarre qu'il y avait aussi peu d'erreur avec un truc faux a ce point ....... (en effet mon arbre quand je compresse mon huff.c est de hauteur 13 .....)

voila merci encore a toi et ptet a bientot

Pas de quoi.
Bienvenue dans le monde du C, c'est le genre de pépins qui arrive fréquemment !!

Sinon, pense à cliquer sur le bouton [Résolu] en bas à gauche ! ;-)

[ben13]

Sinon, pense à cliquer sur le bouton [Résolu] en bas à gauche ! Wink

Il me reste un prob tres chiant. Chez moi (knoppix + compilateur GCC) comme je t dit ca marche du feu de dieu, j'ai meme fait le test ultime (compression de l'executable du programme (17Ko) et ca marche)

mais sur les ordis de ma fac (solaris sur station d'accueil de merde d'ailleurs + GCC aussi) la compilation marche mais apres decompression je me retrouve avec nimporte quoi, un fichier qui contient tres peu de lettres differentes pour la compression d'un fichier texte ...

alors voila si tu peux juste m'aider, je te demande pas de regarder mes sources mais juste de me dire si ca marche chez toi (si possible sous unix car j'ai fait une implementation unix et je sais pas ce que ca peut donner sous du ms dos)

Je te poste les liens de la source et de l'exec ...

Merci d'avance

http://pyts01.free.fr/projet/huff.c

http://pyts01.free.fr/projet/huff

[Pouic]

<...>
(si possible sous unix car j'ai fait une implementation unix et je sais pas ce que ca peut donner sous du ms dos)
<...>

Je connais un dragon qui va cracher des flammes...

<edit>
Et chez moi, ca fonctionne nickel

Par contre, quand même:

$ gcc huff.c
huff.c: Dans la fonction « huffman »:
huff.c:101: attention : `tmp' might be used uninitialized in this function
huff.c: Hors de toute fonction :
huff.c:373: attention : return type defaults to `int'
huff.c: Dans la fonction « main »:
huff.c:432: attention : type de caractère de conversion inconnu 0xa dans le format
huff.c:385: attention : unused variable `tab_codes_comp'
huff.c:440: attention : unused variable `i'
huff.c:373: attention : unused parameter `arge'

</edit>

++
Pouic

[ben13]

je sais j'ai corrigé tout ca a ma fac et tjs pareil ...

Je connais le -Wall ...

update : les nouvelles sources avec corrections sont online

[Mac LAK]

<...>
(si possible sous unix car j'ai fait une implementation unix et je sais pas ce que ca peut donner sous du ms dos)
<...>

Je connais un dragon qui va cracher des flammes...

Ouaip ! Ah, Pouic, comme tu me connais bien !

Plus sérieusement, mais il te serait difficile de le savoir sans me lire régulièrement, je n'ai pas d'Unix à la maison, je n'aime pas Unix, j'ai jeté mes CD d'install Linux et j'aime pas le GNU non plus... ;-)

Plus sérieusement, tu devrais corriger les erreurs que Pouic t'a remonté... Un bon principe, en C, est que "Un warning de compilation fait une erreur d'exécution". T'as pas idée du merdier que peuvent générer certains compilateurs C lorsqu'il y a des warnings et des optimisations simultanément... :-( Et il est tout à fait probable que lever ces warnings corrige le dysfonctionnement que tu constate sur Solaris.

A priori, je n'ai pas vu d'énormités dans le code source, à part l'utilisation de la constante "1" au lieu de "sizeof(unsigned char)" dans les fread/fwrite.

Je n'ai pas, à la maison, de quoi le compiler pour DOS ou Win32, désolé, et vu que ton programme est assez massivement orienté Unix, le porter sur DOS/Win32 risque d'être assez mignon.

Est-ce que le problème se produit aussi avec les fichiers binaires ?

J'essayerai de voir si je peux passer ton code sur PC Lint demain, je ne sais pas si ça marchera vu que je n'ai pas les entêtes spécifiques Unix, mais bon, on verra bien...

[ben13]

merci pour ta reponse

bon deja j'ai corrigé les erreurs cet aprem a ma fac et ca fesait pareil....

pas testé avec un binaire dsl

je vais voir encore un peu mais ce qui est bizarre c'est que mon ggc en mode -Wall me mets 2 erreurs de moins que celui de pouic .... a savoir :

huff.c:101: attention : `tmp' might be used uninitialized in this function
huff.c:373: attention : unused parameter `arge'

enfin je les corrige quand meme .....

[Emmanuel Delahaye]

je vais voir encore un peu mais ce qui est bizarre c'est que mon ggc en mode -Wall me mets 2 erreurs de moins que celui de pouic .... a savoir :

huff.c:101: attention : `tmp' might be used uninitialized in this function
huff.c:373: attention : unused parameter `arge'

enfin je les corrige quand meme .....

-Wall ne suffit pas. La config minimale sérieuse, c'est

Code :

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

-W -Wall -02

Par exemple, avec ton code, j'ai:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
gcc.exe -c main.c -o dexe/main.o -I"C:/DEV-CPP/include" -W  -Wall  -ansi  -O2
 
main.c: In function `huffman':
main.c:100: warning: `tmp' might be used uninitialized in this function
main.c: In function `main':
main.c:420: warning: implicit declaration of function `unlink'
main.c:372: warning: unused parameter `arge'
main.c:383: warning: `code' might be used uninitialized in this function
main.c:439: warning: `code' might be used uninitialized in this function

Pourquoi unlink() ? Qu'est-ce qui ne va pas avec remove() ? Pourquoi ne pas être standard quand c'est possible ?

[ben13]

-Wall ne suffit pas. La config minimale sérieuse, c'est
Code:
-W -Wall -02

c -O2 pas -02 mais effectivement ya encore 2 erreurs que j'ai reglé, merci a toi

j'envoie le nouvel executable, je vire la source car j'aimerai juste que kkun teste sous un env unix .. merci


PS : j'ai lu dans le man de gcc (en anglais) ce que fait -O2 mais j'ai pas tout saisi, tu peux me dire en 2 mots l'interet de toutes ces optimisations et si elles ne peuvent pas poser des probs dans certains cas ???? merci

[ben13]

Pourquoi unlink() ? Qu'est-ce qui ne va pas avec remove() ? Pourquoi ne pas être standard quand c'est possible ?

dsl javais pas vu cette remarque.

J'ai trouvé unlink sur la FAQ du site mais si tu me dit que remove est standard je vais mettre remove ...

[Emmanuel Delahaye]

PS : j'ai lu dans le man de gcc (en anglais) ce que fait -O2 mais j'ai pas tout saisi, tu peux me dire en 2 mots l'interet de toutes ces optimisations et si elles ne peuvent pas poser des probs dans certains cas

En ce qui concerne la vérification du code, ça met en oeuvre un processus supplémentaire qui vérifie le flot de données (de façon à éliminer le code redondant). Ce mécanisme permet de detecter des variables non initialisées (grave) et autres variables non utilisées ou jamais relues... (pas grave).

Le code produit est souvent plus compact ou plus rapide, voire les deux.

Les problèmes éventuels sont liés à l'utilisation de GDB (debugger), car l'exécution ne correspond plus à ce qui a été codé, et le cheminement réel est parfois suffisament tordu pour planter le débugger. En mode debug : -O0 ou pas de -O.

[ben13]

ok merci pour ces infos

[Caine]

Salut,
Mac Lak m'a demandé de tester ton code,

La compression semble marché, mais lla décompression donne un jolie segmentation fault.

Une petite remarque au passage, il faut toujours caster le pointeur de retour d'un malloc ans le type de la variable de stockage. Ca évite de chercher les erreurs de compilation de ce genre

Bon suivant mon temps libre, je vais voir de debuguer ça, mais ce ne sera pas pour tout de suite.