Diferențe pentru problema/huffman între reviziile #2 si #37

== include(page="template/taskheader" task_id="huffman") ==

Să se implementeze compresia cu arbori Huffman canonici.

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":http://algopedia.ro/wiki/index.php/Clasa_VII/VIII_lec%C8%9Bia_29_-_27_mai_2014#Lec.C5.A3ie_-_compresia_folosind_arbori_Huffman

h2. Cerință

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

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

h2. Date de intrare

Fișierul de intrare $huffman.in$ este comprimat dacă începe cu caracterele HCC și este necomprimat în caz contrar.

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

h2. Date de ieșire

h2. Exemplu
table(example).

|_. huffman.in |_. huffman.out |_. Explicație |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| Explicație

|_. huffman.in |_. huffman.out |
| abracadabra
|CHC\0\0\0\0\0\0\0\11\255\255\254...\1\3\5\4...\2...\6\105\231\52
|
 
h3. Explicație
 
table(example).
|_. Frecvențe |_. Arbore inițial |_. Lungimi |_. Coduri |_. Compresie |
| c 1
d 1
b 2
r 2
a 5
|   11
  /  \
 a5    6
     / \
    r2  4
       / \
      2   b2
     / \
    1   d1
   / \
rest  c1
| a 1
b 3
c 5
d 4
r 2
| a 0
b 110
c 11110
d 1110
r 10
| a b r a c a d a b r a
0 110 10 0 11110 0 1110 0 110 10 0
 
regrupăm cîte opt biți:
 
01101001 11100111 00110100
 
convertim în zecimal:
\105 \231 \52
 
Harta rezultatului final:
 --------------------------------------------------------------------------------
¦ SIG ¦ lungimea 8 octeți ¦ lungimi coduri 256 octeți          ¦ codare 3 octeți ¦
 -----+-------------------+------------------------------------+-----------------
¦ CHC ¦ \0\0\0\0\0\0\0\11 ¦ \255\255\254...\1\3\5\4...\2...\6  ¦ \105\231\52     ¦
 --------------------------------------------------------------------------------

|
== include(page="template/taskfooter" task_id="huffman") ==