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 | 2 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
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
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 ¦ ———————————————————————————————————————— |