Discussion :

[ben13]

enfin je pense pas que ca pose des probs

dans mon fichier compressé j'ai la suite de caracteres correpondant au code ascii des int que j'ai codé, et le -6 (par ex) correpont bien au caractere qui a la code 250...

donc je pense pas que ca pose un prob en vue de la decompression ....

[ben13]

je suis tres content ca roule !!!

pour la decompression il me suffit de repasseren binaire, de reconstruire le tas de huffman et le parcourir bit par bit, ca devrait etre faisable

merci pour ton aide encore une fois je pense que je vais m'en sortir now, mais si j'ai un prob je reviendrais .....

[Mac LAK]

Je vois mal comment coder du Huffman sans passer la taille de chaque 'pseudo-caractères', puisque celle-ci est variable...

C'est pourtant très simple, et ça se résume en une seule expression : "séparabilité des codes de Huffman". C'est quand même une des bases de cet algo...
En bref, les codes de Huffman ne sont jamais préfixes d'un autre code de Huffman, et coder la longueur des codes compressés est donc complètement aberrant, pour ne pas dire saugrenu.
D'ailleurs, à ce sujet, il y a deux grandes manières d'implémenter les codes de Huffman : une version où il existe deux codes de deux bits comme "codes courts", et une version où il existe un code d'un seul bit. La méthode "classique" consiste à avoir un code minimal de 2 bits (compression maximale : 25% de la taille d'origine), mais l'autre permet sur certains fichiers d'améliorer la compression (12.5% de la taille d'origine).

maintenant je dois les prendres 8 par 8 et en faire un nombre compris entre 0 et 255. jai bien suivi mes cours sur la numération ( ) mais je suis obligé de me taper un algo avec les puissances de 2 ???? ya pas une fonction standard qui peut me convertir une suite de huit 0 et 1 en un entier ????????

A l'époque, j'avais également eu à coder un algo de Huffman. J'étais parti sur une méthode (à mon sens) beaucoup plus simple, qui était de transformer mon fichier en flux de bits. En version simple, ça consiste lire ou à écrire au travers d'un octet qui sert de "buffer" aux bits émis, ces bits étant émis par décalage binaire du buffer.
Tous les 8 bits émis, tu lis un nouvel octet ou tu écris celui qui est "plein". En interne, il te suffit de faire une encapsulation de tes fonctions de lecture/écriture (fread/fwrite) pour être tranquille.

Enfin, pour garantir la séparabilité des codes (qui est liée à la répartition statistiques des caractères), il est en général préconisé de stocker cette table des fréquences dans le fichier compressé. L'optimisation de ce stockage peut également être un exercice assez amusant.

Dans mon propre cas, l'implémentation était à faire en ADA, et ça n'a pas franchement été très compliqué malgré l'extrême rigidité du langage... Alors en C, c'est du gâteau ou presque d'implémenter un tel buffer, les problèmes ne pouvant réellement survenir que si l'on veut optimiser lourdement ces opérations de lecture/écriture.

Si tu sais lire l'ADA, je peux te faire passer ces sources.

[ben13]

salut mac LAK

moi j'ai eu la meme idee que toi sachant que la structure de tas a la propriété qu'aucun code est le prefixe d'un autre.

mon fichier compréssé est donc la suite des codes binaires de chacun des caracteres du texte, sans aucune indication de longueur puisque celle ci ne sert a rien.

bref la compression est tres bonne, il me reste plus qu'a implementer le tableau de correspondances caractere/code binaire dans le fichier compressé, et le tour est joué

je vais essayer d'optimiser la taille de ce tableau car sinon la compression sur des fichiers de petite taille risque de ne pas etre evidente ........

a+

[ben13]

pour les sources c'est gentil mais j'aime pas les sources ...... je prefere demander conseil s'il faut mais programmer moi meme, det toute facon je pense plus avoir de prob now.

et en plus je sais pas lire l'ADA

[Mac LAK]

Si tu veux, par contre, je peux poster ici les différentes optimisations que j'avais utilisées pour stocker la table des fréquences de manière la plus compacte possible. J'utilisais trois techniques différentes (et complémentaires) pour réduire cette taille.

Ce n'est pas forcément optimal, mais par rapport aux 1024 octets "par défaut" de cette table, je tombais souvent à des chiffres bien inférieurs (souvent <100 octets, si ma mémoire est bonne). Bien sûr, si la taille de la table de fréquence (même optimisée) était supérieure au gain de compression, je renvoyais un warning "Fichier non-compressible" : libre à l'utilisateur après de forcer la "compression" ou pas, mais il était prévenu que la taille "compressée" serait supérieure à la taille d'origine. De toutes façons, ce cas de figure est inévitable avec les algorithmes de compression sans pertes, alors autant le gérer proprement ! ;-)

Pour les sources, no problem : comme on dit, "Librement proposé, librement refusé" ! ;-) Et puis c'est vrai que ne pas savoir lire l'ADA, c'est une bonne raison...

[ben13]

merci a toi.

mais j'ai pensé que ca serait ptet pas une mauvaise idee que de stocker dans le fichier directement le tas de huffman. Parce que de toute facon le tableau de correspondances m'aurais servi uniquement a reconstruire l'arbre ....

je vais essayer mais je pense que ca doit pas poser de prob en C en mettant dans mon fichier des sizeof(ma structure de noeud de mon tas ....) fois le nombre de noeud que je peux calculer recursivement .....

[ben13]

je me rapellais plus qu'un pointeur etait codé sur un int ...

du coup l'arbre est beaucoup trop lourd

je vais donc coder la tableau (les 256 tanpis pour celles qui servent a rien) mais chaque case sera composé de seulement 2 unsigned char (un pour la taille du code et un pour le code que j'aurai convertir du pseudo binaire en char)

du coup 256*2 = 512 octets .... c'est raisonnable

[Mac LAK]

Effectivement, stocker l'arbre est une très mauvaise idée : il faut stocker uniquement les fréquences, et recalculer l'arbre avant de décompresser.

Perso, j'avais utilisé plusieurs astuces pour ce stockage :
- Stocker, en début de table, le nombre de bits utilisés pour stocker les fréquences (de 1 à 32) => déjà, on gagnait beaucoup de place, et comme de toutes façons le fichier était déjà lu bit à bit, ça ne pénalisait pas le traitement. Il suffit de 5 bits pour stocker cette valeur.
- Stocker le premier et le dernier caractère ayant une fréquence. Par exemple, sur du texte sans caractères accentués, ça donnait souvent 10 comme premier caractère (LF) au lieu de zéro, et 122 comme dernier caractère (au lieu de 255). Bref, une grosse place économisée. J'utilisais un bit pour indiquer s'il y avait un premier/dernier ou pas : en fonction du nombre de fréquences "gagnées" en début et fin de table, ce n'était parfois pas rentable de stocker ces deux valeurs => ainsi, je ne perdais qu'un seul bit au lieu de perdre deux octets.
- Enfin, sur les fréquences restantes, je stockais une "table de présence". C'était tout simplement une succession de bits correspondant aux fréquences possibles (dans le cas précédent, de 10 à 122 donc, soit 113 bits), indiquant s'il y avait une fréquence non-nulle (1) ou pas (0). Sur du texte, il y avait souvent de nombreux "trous" dans la table des fréquences, un calcul simple permet de savoir s'il est rentable de stocker une telle table de présence ou pas (nombre de fréquences nulles X taille en bits d'une fréquence > nombre de fréquences à stocker == rentable). Comme précédemment, un simple bit suffit à indiquer si cette table est présente ou pas.

Je te conseille de rajouter une signature (2 octets minimum) pour "identifier" le type de fichier (par exemple, les deux premiers octets du fichier étant toujours "AH" pour "Archive Huffman", ou n'importe quoi d'autre). Bref, le même "truc" que l'on trouve sur beaucoup de formats de fichiers (EXE Dos/Win, BMP, GIF, etc...).
Il ne serait pas nuisible de mettre en plus un checksum pour le calcul d'intégrité de l'archive (CRC16 ou CRC32 par exemple) : non seulement c'est plus fiable, mais ça t'évitera de crasher ton programme si les données sont corrompues.

On peut encore améliorer ce stockage des fréquences, bien entendu, mais ces trois trucs combinés donnaient souvent d'excellents résultats au vu du peu de calculs que ça demandait.

Si tu veux t'amuser un peu, pense à écrire sur la sortie de ton programme les gains obtenus par tes procédés d'optimisation du stockage, tu risques d'être agréablement surpris dans certains cas.

++ !

[ben13]

je vais pas faire tout ca lol c juste un projet pour mes cours....

non mais la j'ai un prob par contre

si je compresse un texte ou ya juste un '£' (caractere livre) dedans

il me mets ca

free(): invalid pointer 0x40086f6f!
Erreur de segmentation

pourtant mon algo marche avec un texte composé uniquement de lettres par exemple et meme tres long.........

pourtant j'ai testé le code ASCII du '£' est bien reconnu par mon systeme ....


ta une idee ???? merci

[ben13]

au fait, c'est une question moins importante que la precedente mais bon ...

je vois pas l'interet de stocker les frequences, moi je stocke les codes binaires et je reconstruirai l'arbre a partir de ca.....

[ben13]

bon apres quelques test j'ai une erreur de segmentation (mais pas de message pointer invalide) pour pas mal de caracteres...... 'é' par exemple .......

[ben13]

hum apperement c'est des caractere qui sont dans la 2e moitié du code ASCII prolongé, c'est surement un prob de char qui est pas en unsigned.

je vais voir ca je te tiens au courant

[ben13]

bon beh nom j'ai remplacé tous les char de mon script par des unsigned char et tjs l'erreur de segmentation ....

[ben13]

OK c'est resolu ! 8) 8)

c'etait une erreur d'inatention rien de grave ....

regarde un peut :

-rwxr-xr-x 1 ben ben 15651 2004-12-20 18:54 huff2
-rw-r--r-- 1 ben ben 7553 2004-12-20 18:54 huff2.c
-rw-r--r-- 1 ben ben 5315 2004-12-20 18:56 zip


le fichier nommé zip est la compression de huff2.c .... c'est pas mal quand meme ....

[Mac LAK]

je vais pas faire tout ca lol c juste un projet pour mes cours....

Ben moi aussi, c'était un projet de Licence, et alors ?

je vois pas l'interet de stocker les frequences, moi je stocke les codes binaires et je reconstruirai l'arbre a partir de ca..

Parceque stocker la table de fréquence permet de bien recomposer le même arbre, et de ne pas faire dépendre l'algo d'une implémentation particulière. De plus, stocker les codes pose quelques problèmes : il faut aussi stocker les caractères d'origine, et le code de Huffman lui-même. Or, à ce stade, il ne sont pas encore séparables !!
Il faut aussi stocker leur longueur... Bref, ça prend souvent beaucoup plus de place que de stocker la table des fréquences, surtout si tu optimises un peu ce fameux stockage !

Voici un dump de mon propre projet, sur un fichier de taille/nature similaire :

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
 Compactage de fragment.cpp :
   - Calcul de la table des frequences : OK.
   - Calcul des codes de Huffman       : OK.
   - Sauvegarde de l'en-tete           : OK.
   - Compactage du fichier             : % 67
 
 
 Resultats :
 ===========
 
 Fichier original    : fragment.cpp
 Taille              : 7507 octets.
 
 Fichier compresse   : fragment.HUF
 Taille              : 5087 octets.
 Taux de compression : 67 %
 
 Informations :
 ==============
 
 Taille de l'en-tete         : 1234 bits.
 Longueur d'une frequence    : 10 bits.
 Nombre de frequences codees : 93
 Codage topologique          : Oui.
 Octet le plus frequent      : 32
               Frequence     : 985

Note : la taille de 5087 octets comprend la taille de l'entête, qui lui-même comprend la table des fréquences.
Comme tu peux le constater, l'entête est très petit (un peu moins de 155 octets) par rapport à la taille du fichier : il ne représente qu'environ 3% de la taille de l'archive... Tu comprends maintenant pourquoi j'ai stocké la table des fréquences et non pas les codes ! ;-) 8)

c'est pas mal quand meme ....

Et tu arrives à le décompresser, ou pas encore ? Parceque c'est quand même "ZE" test ! ;-)

[ben13]

j'ai pas encore programmé la decompression mais je vois pas pkoi ca marcherai pas ..... moi je suis tjs pas d'accord ( ) pour stocker la table des frequences.

Avec mon tableau qui donne pour chaque caractere son code et la taille de ce code, je cree un arbre vide, puis je lis le code du premier caractere, si je tombe sur un 0, je descend vers le fils gauche, si je tombe sur un 1, je descends vers le droit....ceci jusqu'a la fin du code puis je fous mon caractere a cet endroit. Je recommence l'operation pour chaque caractere et a la fin je suis SUR de retomber sur l'arbre original, sans les frequences mais celles-ci ne servent plus a rien a ce stade.

Ensuite je lis bit par bit (ce qui va d'alleurs me poser un petit prob mais bon) et je descend dans mon arbre, des que je tombe sur un NULL j'ecrit le caractere dans le fichier qui sera le fichier decompressé....


Pke une chose que j'ai pas trop comprise avec ta methode, c'est que on est bien d'accord que je dois stocker le tableau des frequences mais aussi avec les codes et donc la taille des codes, et vu que je me sens pas de faire pleins d'optimisations comme toi .... ( car j'ai deja passé pas mal d'heures la dessus et j'ai pas mal de matieres a reviser pour les exams....) beh ca risque de me faire quelque chose de tres lourd à stocker ......

[ben13]

chui en train de penser que j'ai dit une belle connerie.

En stockant le tab des frequences tu peut reconstruire l'arbre en utilisant la meme fonction qu'au debut et donc ta les codes, et tu peux donc reconstruire, encore avec la meme fonction, le tableau de codes ... c genial !!!! (bref tavais raison quoi...)

dsl mais j'ai un peu le cerveau en bouillie ces derniers temps ....


par contre si je fais aucune optimisation et que je considere que les indices correspondent aux caracteres, le tableau mesure quand meme 256 int donc 1024 Ko .... c'est lourd


je vais reflechir un peu .....

[ben13]

du coup j'ai mieux regardé les optimisations que ta fait toi .... et c'est pas bete du tout mais je me sens pas de faire ca dans un premier temps je prefere un algo lisible au max pour pas m'y perdre en cas j't reviendrais plus tard .....

si j'ai le temps demain je vais essayer de faire ca donc

a+

[ben13]

bon voila j'ai reconstruit mon arbre a partir du fichier et ca marche (je l'ai affiché c'est ok), demain j'ai plus qu'a faire une fonction qui lit le fichier et qui parcours l'arbre pour afficher les caracteres ...

je pense que je vais faire une sorte de "tableau buffer" dans lequel je mettrais les 0 et les 1 que j'aurai convertit des unsigned char contenus dans le fichier compressé ....

par contre je me tate pour savoir de combien d'octet je devrais faire ce "tableau buffer" remarque a mon avis c'est bonnet blanc, blanc bonnet ....