oui oui notre prof ns a donné aujourd hui le sujet du nouveau projet
Compression Hufmann
a executer sur un fichier ou sur un repertoire
contraintres :  -compression en UNE SEULE passe
-idem pour la decompression
-calcul des occurences et calcul de l arbre en meme temps (donc theoriquement sans passer par une liste chainée triée)
-taux de compression minimum de 30%
-ne pas compresser si le gain est nul
-evidement que ca marche sur tous types de fichiers
-rapide....
 
si ca avait été a faire en methode traditionnelle C tout simple, mais la j avoue que tout faire en une passe pour la compression....
(le prof a précisé qu aucun étudiant n avait a ce jour reussi....)
tout ceci en C bien entendu (mais ca C loin d etre un pbleme)
bref.....je me meurs.
a++
 

--Message édité par ZuL--

tout le monde s en tape ou personne a d idées ?

j'ai pas d'idée

ca fonctionne comment Hufmann, j'me rappelle plus

J'ai pas d'idée mais je reste à l'écoute

Ouaih ! Explique en gros comment ça marche la compression Huffman, t'auras peut-être qq réponses comme ça..

en gros la compression Hufmann, ca doit marcher pour les sons, la video, les fichiers txt et d autres je sais pas trop encore quoiss
on va prendre l exemple d un fichier texte
alors on le parcours et on stocke ds un tablo de 255 cases (le numero de case representant le code ascii du caractere lu)le nbr d occurences de chaque caractere
avec ca on crée une liste chainée croissante ou decroissante (ca depend des cas, c est juste de l optimisation).
on va prendre la phrase "elle est"
on aura la liste chainée suivante :ss
e:3->l:2->s:1->t:1
on crée un arbre avec ca en partant des feuilles
on combine les commets et on reinjecte ds la liste chainée
(j vs donne les etapes de la liste) et on crée ainsi l arbre des codages.
e:3->l:2->s:1->t:1
e:3->1:2->l:2->s:1->t:1
2:4->e:3->1:2->l:2->s:1->t:1
3:7->2:4->e:3->1:2->l:2->s:1->t:1
ss
ce qui donne l arbre (on attribue par defaut 0 aux branches gauches et 1 aux branches droites)
 
ssssss3:7
ssss /0ss1
ssss2:4sse:3
ss /0ss1
ss1:2ssl:2
 /0ss1ss
s:1sst:1
 
on obtient donc les codes de caracteres suivants :ss
e:1
l:01
s:000
t:001
 
apres on a plus qu a parcourir le fichier et remplacer chaque caractere par son code
ca C la methode standard
notre prof ns demande de construire l arbre ci-dessus EN MEME TEMPS que le calcul des occurences de chaque lettre....
c est chaud quoi.....
a++ss
(je sais l explication est pas super claire.......mais C pas facile a expliquer ici

euh... t'es pas cohérent avec toi-meme
 
dans le premier poste tu dis que la compression doit se faire en une seule passe, tandis que dans le dernier, tu dis juste que c'est l'arbre qui doit être construit en meme temps, pas la compression.
 
Dans le deuxieme cas, ca me semble relativement faisable, il faut modifier l'arbre au fur et a mesure, mais ca me parait pas insurmontable.

Oui il veut sans doute que vous encodiez le fichier en une seule passe. C'est intéressant si le fichier est très gros.
 
Par contre ne seulement construire l'arbre en même temps n'est pas intéressant (niveau rapdité) si on doit refaire une passe ensuite pour l'encodage puisque l'arbre a au max 256 noeuds et feuilles (donc sa construction est presque instantanée).

--Message édité par Verdoux--

 
mais si mais si j suis coherent
enfin.....j ressort texto ce que le prof ns a dit
1) encodage en une seule passe
2) calcul des occurences et creation de l arbre en meme temps
 
mais.....une fois l arbre construit, on est quand meme obligés de reparcour le char* pour remplacer au fur et a mesure....y a donc 2 passes du fichier (stocké ds un buffer...ca va + vite)
enfin c est chaud chaud quoi....
merci a++

j ai fait peur a tout le monde ou quoi ?!?

Je vois toujours pas l'intérêt de créer l'arbre en même temps.

moi non plus, mais bon, la pédagogie...

A moins d'etre devin, comment est-ce qu'on peut remplacer un caractere avant de connaitre son code (qui ne peut etre determine qu'a la fin une fois que la frequence du caractere est connue?). A mon humble avis, ton truc c'est pas faisable.

C'est clair que la version optimal de hufmann n'est pas possible, mais on pourrait en trouver un dérivé qui conserverait un état de l'arbre a différent moments et donc faire le truc en une passe...

Si on ne cherche pas l'optimum, on pourrait generer un arbre sur disons le premier tiers du fichier (sans compresser ce tiers) puis en supposant que le fichier est plus ou moins homogene, l'utiliser pour compresser le reste. Il est evident que ca ne marche que pour des tres gros fichiers.

euh.....quand le prof disait en une seule passe, un abus de language surement
ca m etonnerait qu on puisse compresser correctement avec un arbre imcomplet
le principal pbleme est de créer l arbre en meme temps que le calcul des occurences
c est a dire commencer a creer l arbre des le premier caractere...
des idées ?
merci d avance

bah oui, tu construis ton arbre tranquille tant que tu rencrontre des nouveaux symboles. Et quand tu en a un déja rencontrer, si son occurence dépace celle d'un autre, tu les permutte, c'est pas plus dur que ca. Par contre, j'en connais un qui va chier avec les pointeurs

 
non c est plus compliqué que de la simple permutation vu que seules les feuilles sont des lettres, les autres sont des combinaisons soit de feuilles, soit de neouds.....bref C galere.....Et oui j V en chier avec les pointeurs

ET alors, tu permutes les feuilles, c'est bien ce que je dis, je vois pas ou est le probleme vu que l'encodage se fait par après.