6 Huffmanov kód

Úloha je štandardne za 6 bodov, ale sú na ňu dva týždne

Program dostane jeden parameter a to je cesta k súboru. Potom vykoná nasledovné.

  1. Otvorenie súboru binárne.

  2. Výpočet optimálneho Huffmanovho kódu. (Tu si môžete pozrieť vizualizáciu).

  3. Výpis kódu na štandardný výstup vo formáte (vypisujte iba bajty, ktoré sa na vstupe nachádzajú):
    0: kód pre byte 0
    1: kód pre byte 1
    ...
    255: kód pre byte 255

Príklady

Pre vstup je výstup

10: 101111001
13: 101111011
32: 111
33: 00011011000
40: 10111111111101
41: 10111111111011
44: 000111
45: 000110100
46: 0001100
58: 10111111111100
59: 101010100
63: 000101000
65: 000101001
66: 1010101011
67: 1010101010
68: 000110111101
69: 00011011101
70: 10111111110
71: 10111111101
72: 10111111100
73: 10111110
74: 0001101111001
76: 00011011100
77: 1011111111111
78: 1011111100
79: 00011011111
80: 10111101010
82: 101111010011
83: 1011111101
84: 000110101
85: 10111111111010
86: 1011111111100
87: 000101011
89: 00011011001
97: 1001
98: 000100
99: 101011
100: 01110
101: 001
102: 101000
103: 101110
104: 0000
105: 0100
106: 0001010101
107: 10101011
108: 10110
109: 110101
110: 0101
111: 1000
112: 011110
113: 0001010100
114: 11011
115: 0110
116: 1100
117: 110100
118: 1010100
119: 011111
120: 0001101101
121: 101001
122: 10111101011
128: 00010110
148: 101111000
153: 10111101000
156: 101111010010
157: 0001101111000
226: 00010111

Kódy vám môžu vyjsť aj inak Tak isto ako minule treba rátať s obrovskými vstupmi (10GB+).

Bonus

1 bod

Aplikovanie kompresie. Ak urobíte aplikáciu tak, že ak dostane dva parametre, tak urobí to čo má (teda vypíše na štandardný výstup tabuľku) a navyše do výstupného binárneho súboru (druhý parameter) zapíše skomprimovaný súbor (aplikovanú tabuľku). Vo formáte

  • Najprv unit64_t s veľkosťou súboru po kompresii v bitoch.

  • Potom postupne všetky kódy bajtov pôvodného súboru, teda zakódujete súbor do huffmanovho kódu. Tu je veľmi dôležité aby ste dobre pracovali s bitmi, lebo inak to nebude dobre fungovať.

  • Zarovnanie nulami, keďže súbor nemôže mať 47,5B.