Fişierul intrare/ieşire:huffman.in, huffman.outSursăCerc informatică Vianu
AutorDavid HuffmanAdăugată defrancuCristian Francu francu
Timp execuţie pe test2 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

huffman.inhuffman.out
abracadabra
CHC\0\0\0\0\0\0\0\11\255\255\254...\1\3\5\4...\2...\6\105\231\52

Explicaţie

FrecvenţeArbore iniţialLungimiCoduriCompresie
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     ¦
 --------------------------------------------------------------------------------
Trebuie sa te autentifici pentru a trimite solutii. Click aici