Fișierul intrare/ieșire	huffman.in, huffman.out	Sursă	Cerc informatică Vianu
Autor	David Huffman	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.7 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	4.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Huffman (clasa a 11-a)

Să se implementeze compresia cu arbori Huffman canonici. Arhiva (fișierul comprimat) va avea următoarea structură:

• primii trei octeți vor fi codurile ASCII ale caracterelor ‘CHC’
• următorii 8 octeți vor conține lungimea fișierului original (necomprimat) în format big endian (octetul cel mai semnificativ primul)
• următorii 256 de octeți vor conține lungimile codurilor Huffman ale fiecărui caracter: octetul i este lungimea codului Huffman a caracterului cu cod ASCII i
• următorii octeți, pînă la finalul fișierului, conțin compresia Huffman propriu zisă
• dacă numărul de biți ai compresiei nu este divizibil cu 8 atunci ultimul octet se completează la coadă cu biți zero

Pentru informații detaliate vedeți lecția compresia folosind arbori Huffman

Cerință

Dat un fișier să se comprime, sau, dat un fișier comprimat să se decomprime.

Date de intrare

Fișierul de intrare huffman.in este comprimat dacă începe cu caracterele CHC (Canonical Huffman Coding). El este necomprimat în caz contrar.

Date de ieșire

În fișierul de ieșire huffman.out se va scrie compresia fișierului huffman.in dacă acesta este necomprimat. În caz contrar se va scrie fișierul huffman.in decomprimat.

Restricții

• 0 ≤ mărime fișier intrare ≤ 5000000

Exemplu

Explicație

Numărul de apariții al caracterelor este: a5 b2 c1 d1 r2.

Arborele Huffman construit este: