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

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

Poveste și cerință...

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 comprime, sau, dat un fișier comprimat să se decomprime.

h2. Date de intrare

Fișierul de intrare $huffman.in$ ...

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

În fișierul de ieșire $huffman.out$ ...

Î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.

h2. Restricții

* $... ≤ ... ≤ ...$

* $0 ≤ mărime fișier intrare ≤ 5000000$

h2. Exemplu
table(example).
|_. huffman.in |_. huffman.out |

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|

| 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") ==