Fișierul intrare/ieșire huffman.in, huffman.out Sursă Cerc informatică Vianu
Autor David Huffman Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 2 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip full
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Explicație

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     ¦
 ————————————————————————————————————————

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii