Despre compresie si Huffman ...

[nash_mit]

        Problema mea suna in felul urmator ... am un text .. pot sa il comprima aplicand un algoritm de tip huffman ... apoi ce rezulta ( sir de 0 si 1.. ) iau cate 8 fi formez carcatere pe care le pot retine intr-un fisier .. evident .. acestea se pot comprima din nou .... si tot asa .. 
        Pe mine ma intereseaza ca la sfarsitul unui sir de comprimari de genul asta sa ajung cu fisierul comprimat la maxim ... intrebarile care survin sunt ... se poate arata ca numarul de apeluri de tip huffman .. este unul destul de mic .. cat sa faca ideea valabila .. ?  Cand stiu ca am ajuns la comprimare maxima si ca nu trebuie sa mai continui ? ... .. Daca se considera ca se stie numarul de pasi pana cand comprimarea devine maxima ... se poate face un algoritm de programare dinamica pe sirul de arbori huffman .. pentru modul optim de comprimare ( ideea este .. ca ori ce arbore huffman.. e posibil sa fie scris diferit pentru o anumita comprimare ) (evident ... prblema e pusa doar din punct de vedere teoretic ... ... )

[•Cosmin]

Cred ca dupa ce comprimi o data orice fisier normal, nu se mai merita sa il comprimi inca o data.

[nash_mit]

   Depinde de cat s-a comprimat .. huffman micsoreaza de la 20% pana pe la 80% .. daca prima comprimare a adus o compresie de 20% ? .. si a doua aduce ... o compresie de 50% ? ... uhm .. eu zic ca se merita ... ( insa e doar o problema teoretica .. )

[•Cosmin]

Stiu la ce te referi, dar intuitia mea spune ca daca folosesti huffman o data, a doua oara nu prea mai ai ce compresa prin aceiasi modalitate. Cand o sa am timp probabil o sa implementez si sa testez sa vad ce se intampla.

[nash_mit]

 Uite unde greseste intuitia ta... dupa compresie .. o sa am un sir de biti ... care .. daca il imparti in cate 8 biti .. o sa pot sa consider ca este scrierea in baza 2 a caracterelor codului ASCII ... nu ai de unde sa sti ...ce va aduce o noua comprimare ... ( mai este si problema .. ca pentru un anumit tip de date se poate forma mai multi arbori optimi ( daca se executa o comprimare ) - adica .. marimea finala sa fie aceasi dupa comprimare ... si.. pentru fiecare astfel de comprimare .. daca incerc o recomprimare prin metoda spusa mai sus .. ma va duce la marimi diferite de fisiere .... 

[•byndrsn]

.. ai incercat sa testezi metoda ta? al doilea pass iti aduce vreo imbunatatire?... sunt curioasa pentru ca intuitiv cred ca a doua aplicare a algoritmului iti poate imbunatati compresia doar din intamplare... intuitia imi spune ca a doua/ treia, etc. distributie pe care o obtii e foarte aproape de distributia uniforma.. 

[nash_mit]

pai cum sa fie foarte aprope ... ? .. uite .. poti .. sa zicem .. sirurile ... 0 100 101 1100 1101 111 ( ex. din cormen) ... dar tu cand ... reformezi siruri de caractere .. nu ei cate 1 sau cate 3 sau cate 4 .. ( cate au astea de lungime inegala ) ci ei cate 8 .. deci .. datoriata faptului ca am avut siruri de lungimi inegale ... cand vom forma caractere .. vom lua ...  din siruri sonsecutive .. gen: 01001011 ( am luat primul al doilea al treilea si primul bit din al patrulea ... ) .. deci se va forma alt sir de caractere care o sa dupa la un alt arbore huffman ....

[•byndrsn]

.. da.. va fi un nou sir de caractere.. ma refeream la faptul ca noile caractere in noul mesaj vor avea probabilitate aproape egala... uite, de exemplu iei primii 8 biti si formezi un caracter din noul alfabet.. de cate ori te astepti sa vezi caracterul acesta in noul mesaj? te astepti sa-l vezi a doua oara? a treia, etc? ma refeream doar la faptul ca nu vei avea caractere repetate in noul mesaj..

[nash_mit]

Ei nu vei avea ... pai .. cate siruri distincte de 8 biti pot sa fie ? 2^8=256 ( si chiar daca am avea atatea caractere noi formate tot ar fi unele care ar aparea de mai multe ori in text ) ... daca sunt mai mult de 256 ( ceea ce este sigur ) ... evident unele se vor repeta ..... 

[•byndrsn]

.. ok.. chiar daca un caracter apare de 1000 ori, al doilea de 1001 ori, si tot asa.. distributia tot (aproape) uniforma ramane.. oricum.. daca ai niste rezultate te rog posteaza-le...

[nash_mit]

pai sa vedem ... orice text ... comprimat are probabilitatea ca in urma comprimarii sa fie cu 20%-80% mai mic ... nu ? cea ce tu spui .. s-ar putea intampla inclusiv la textul initial ... dar comprimarea este garantata in intervalul ala  ( consideram ca aveam un text destul de mare ) .. deci .. nu intaleg de ce .. al doilea text ( rezultat in urma comprimarii ) nu ar putea sa fie comprimat sa zicem ... din nou undeva intre 20%-80% .... daca al doilea text ar fi dat initial si s-ar cere comprimarea lui ?
     uhm ... rezultate daca ai rabdare pana maine ... ca ... implementasem un huffman ... si maine am si examen ... si .. nu prea am timp sa il implementez acum ... din nou ...

[•byndrsn]

pai.. o sa vedem oricum.. daca la fiecare pas ai obtine "garantat" o compresie mai buna, ai putea comprima orice fisier arbitrar de mult  .. btw.. ce ai sa stochezi ca sa poti decomprima fisierul dupa ce ai aplicat huffman de cateva ori? ai sa stochezi pentru fiecare pas matricea  caracter-cod? stochezi distributia? 

[nash_mit]

da .. dar .. la un moment dat ... 20% din ceva foarte mic ..  ar fi prea putin ca sa mai merite inca o compresie ... ( sau un sir de compresii daca ar mai urma ) si atunci .. nu ar trebui sa mai aplicati acesta compresie ...
  si ca sa iti raspund .. la intrebare ... asta e o problema .. mai putin importanta ( e de nivel tehnic ) ... pai .. sa zicem .. ca inceputut fiecarui fisier comprimat .. ar avea ..  codificarea data da arborele huffman ... si apoi sirul de "0" si "1" .... evident ...
  problema este .. ca .. de unde stiu eu .. ca dupa acel sa zicem 20% din ceva mic .. nu o sa urmeze 80% ? ... ( chiar daca e mic ... rezultatul ar fi vizibil ) 

[•Cosmin]

Mai lasa-ma cu povestile si demonstreaza pe cateva date de test k lumea, un text in romana, un mp3 si ce alt set de date iti vine tie in minte. In general numarul de compresii in care intradevar se reduce dimensiunea fisierului o sa fie mic. Pentru zip/rar, adica algoritmi mai buni decat codificarea huffman daca arhivezi de 2 ori aceiasi arhiva ea creste in dimensiune. Ce castigi cu huffman daca faci a 2-a oara e mai mult castig din cauza transformarii in baza 2 si din cauza ca in fisiere normale nu se folosesc in general decat o parte mica din alfabet.

[•Prostu]

Implementarea mea a algoritmului de compresie a datelor a lui Huffman nu are rezultare chiar atat de extraordinare precum se asteapta nash_mit.

La arhivarea romanului "Ultima noapte de dragoste, Prima noapte de razboi", care se afla in format txt simplu si avea dimensiunea de 537.854 B, comprimare avea 297.825 B. In cazul a 2 comprimari avea 296.699 B si in cazul a 3 comprimari avea 298.865B.

In cazul arhivarii melodiei "Stairway to Heaven", care avea 7.686.636 B in format mp3, dupa comprimare avea 7.658.962 B iar dupa 2 comprimari avea 7.661.166 B.

Am incercat si cu o poza, dar nu am reusit sa o convertesc la loc in fisierul initial... 

Am atasat si sursa mea, nu e prea ingrijita, si nici implementarea nu e prea stralucita, e scrisa sa mearga o compresie si o decompresie, dar mai puteti testa. Sursa e in format txt, pt ca nu pot sa atasez fisiere cpp. Precizez ca am folosit fisiere text, nu prea stiu care e treaba cu fisirele binare...
P.S. Este o mare probabilitate ca in urma decompresiei sa mai apara un caracter, doua la sfarsit, dar m-am prins prea tarziu...

[nash_mit]

Mda .. cam asa este ... am incercat si eu .. ( dupa examen :d ) .. am generat un fisier ... de aproximatv 3Mb .. la prima comprimare .... fisieul ajungea la 2,5Mb ... si apoi scadea cu cate 2 sau 3 kb .... ( asta am abservat-o incercat sa comprim comprimarea comprimarii comprimarii etc  .. de .. 15 ori de fiecare data ... doar cate 2 sau 3 k ) .... daca insa fisierul este suficient de mic .. sa zicem .. cam 303kb  ( am generat si asa ceva )... a doua coprimare .... este .. de aceasi marime ... ( deci nu comprimara ) va sa zica .. exista si instante .. care daca vrem sa le comprim .. cu huffman .. nu duc la nimic bun .....

[•byndrsn]

.. uitasem de BARF (Better Archiver with Recursive Functionality)


http://www.cs.fit.edu/~mmahoney/compression/barf.html

.. un citat (the BARF principle):

Recursive compression has long been thought to be impractical. The pigeonhole principle states that it is impossible for a single algorithm to compress all messages of n bits or more, no matter what n is. This is because there are 2n possible messages of n bits, but only 2n-1 possible encodings of n-1 or fewer bits. This means that at least two messages must code to the same encoding. Such an encoding could not be decompressed unambiguously. To avoid this, some messages must inevitably "compress" to an equal or larger size than the original. This limitation has stymied the development of recursive file compression technology because we eventually reach a point at which the "compressed" file is not any smaller.
However, the pigeonhole principle does not apply to a set of algorithms. BARF solves the recursive compression problem by using multiple algorithms arranged in such a way that every nonempty file can be compressed by at least one of them. By choosing the best algorithm, it is guaranteed that every nonempty file can compressed by at least one byte. By repeated compression, any file can be eventually compressed to 0 bytes.