"structure" d'un fichier compressé... - Page 1

quell eest la tendance "normalisée" quand a la structure d'un fichier compresé, a savoir si on met l (pour huffman) l'arbreaavant, apres le fichier, ou on met la table des différents fichiers qd on en compresse plusieurs, et le cas échéant, comment on les sépare, etc...
aivis au programmeurs de ziplib et runC

Ben déjà la table, pour Huffman, n'est pas obligatoire si on emploie l'algo adaptatif. C'est plus performant sur les gros fichiers. Je pense qu'elle est stockée au début pour la méthode semi-adaptative.

Oui, mais pas sous forme d'arbre. J'ai eu un code pour huffman qui gérait ça très bien.

Pour le format deflate (Zip), l'arbre de l'arbre est au début, après il y a l'arbre compressé, et après il y a enfin les données. Il me semble qu'elles sont prises 512o par 512o.
S'il y a plusieurs fichiers, on les met les uns à la suite, et à la fin seulement il y a une table récapitulative.
http://www.wotsit.org/

dauriez vous d'autre liens en plus que celui que Paxal a gentilment laissé ?

Pour la compression zip, regarde la REF sur le PPG

l'arbre de l'arbre ?

Ouais, l'arbre de compression huffman est lui meme compressé huffman...

c pas clair, paske le texte on fait des stats facilement....
ce vaut dire que l'arbre fo le transformer en pseudo texte....et je vosi pas si on va bcp le simplifier a part les balises "noeud" qu'on aura installées, car l'arbre de l'arbre aura aussi 256 caracteres

C'est pas ça: huffman ne sert pas qu'à compresser des fichiers textes, mais toute sorte de données, un arbre par exemple...

vi mais un arbre c'est une structure interne a la mémoire , pas une structure dans un fichier avec des donnes a la suite
fo ke je le convertisse en suites de bits que je re-huffmanerais la oui

C'est ça!

on en arrive au vrai du vrai pb : lécriture dans un fichier de l'arbre....

C'est ce dont on parlait la dernière fois sur IRC, c'est pour ca que je te proposais de faire une routine d'écriture d'un arbre dans un fichier. En quelque sorte c'est la même chose qu'en C ou en CaML: à Noeud tu associes par exemple le premier bit = 1, à F le premier bit = 0.
N ( N ( F , F ) ,F ) <=> 11000
pour le codage des étiquettes, tu peux faire 8 bits = le numéro du caractère.
N ( N ( F '0', F 'a' ), F 'B' ) <=> 1 1 0 00110000 0 01100001 0 01000010
et voilà!

okay, d'abord la tructure de l'arbre, puis les caracteres..pas bete ! maintenant fo ke je réussisse a faire écrire ca pour l' arbre et de mainiere récursive ou aps c cho !

T'as pas tes cours d'info?
Je sait pas si t'en en Maths Spé Option Info ou autre, mais nous en cours on a vu le traitement préfixe, infixe, postfixe, et ici c'est préfixe qu'il faut utiliser!

let rec traite_rec = function
F a -> Ecrire F; Ecrire a
|N a b -> Ecrire N; traite_rec a; traite_rec b;;

et voilà

euh je suis aps en spé je suis a l'ESIEE....
je fais ca en C++

en caml c super facile puisque en 1 instruction on lui fait écrire l'arbre dans un flux....

et oui, caml a des instructions étonnemetn puissantes !

ca y est g fait pour écrire comme tu m'as dit.
maintenant il faut ke je fasse la procédure inverse, de lecture....

en fait je susi pas passé en spé...(vive l'échec )
et VIVE L'ESIEE !

sinon vala mon prog de huffman en caml ke j'avasi fait en mai dernier (en sup )


[nosmile]___________________________________________________________________________________




type arbre= Feuille of char|Noeud of (arbre*arbre);;


let rec ajoute element liste =
match liste with
[]->[element,1]
|(lettre,nbr)::l-> if element = lettre then (element,(nbr+1))::l
else (lettre,nbr):ajoute element l);;

let rec frequence texte liste =
if texte = "" then liste
else frequence (sub_string texte 1 ((string_length texte)-1) ) (ajoute texte.[0] liste);;





let double_min liste =
let rec mini_aux av ap mini =
match ap with
[]->av,mini
|(a,b)::l->if b < (snd mini) then (mini_aux (mini::av) l (a,b))
else mini_aux ((a,b)::av) l mini
in ( let truc = mini_aux [] (tl liste) (hd liste)
in ( let truc2 = mini_aux [] (tl (fst truc)) (hd (fst truc))
in (fst truc2,(snd truc,snd truc2))));;


let rec normalise liste =
match liste with
[]->[]
|(a,b)::l->((Feuille a),b):normalise l);;

let rec arbreuh liste =
match liste with
[a,b]->a
|_->(let resu = (double_min liste) in (
match resu with
(a,((b,c),(d,e))) -> arbreuh (((Noeud (b,d)),(c+e))::a)
));;

let rec encodage texte table_codage =
match texte with
""->[]
|_->(assq texte.[0] table_codage)@(encodage (sub_string texte 1 ((string_length texte)-1)) table_codage);;


let rec codage bitprec tree =
match tree with
(Feuille a)-> [(a,(rev bitprec))]
|Noeud (a,b)-> (codage (0::bitprec) a) @ (codage (1::bitprec) b);;


let compresse texte =
let arbre_huffman = arbreuh (normalise (frequence texte []))
in ( let table_compression = (codage [] (arbre_huffman)) in (
(encodage texte table_compression),arbre_huffman));;


let decompresse liste arbrini =
let rec decode_aux liste tree =
match liste,tree with
[],(Feuille a)->[(char_for_read a)]
|_,(Feuille a)->(char_for_read a):decode_aux liste arbrini)
|x::l,(Noeud (a,b)) -> if x = 0 then (decode_aux l a) else (decode_aux l b)
in ( concat (decode_aux liste arbrini));;
__________________________________________________________________________

[nosmile]
j'ai édité paske ca métait des simleys dans mon code caml le con de forum

[edit]Edité par farib le 01-12-2001 à 18:50:08[/edit]