Autor: Libor Škarvada

Napište program, který bude komprimovat textové soubory pomocí Huffmanova kódování. Prostudujte princip tohoto kódování (např. zde).

Definujte funkce hEncode::String→[Word8] a hDecode::[Word8]→String, které budou převádět znakové řetězce do binárních dat a naopak. Použijte tyto funkce v programu, který komprimuje nebo dekomprimuje soubor podle jména na příkazovém řádku:

huffman -c soubor.txt
huffman -d soubor.huf

Ke zjištění četností znaků v textech lze přistoupit dvojím způsobem: buď spočítat četnost znaků v každém komprimovaném souboru ještě před jeho kompresí, anebo se omezit na texty v určitém jazyce a použít statistické četnosti pro daný jazyk. První přístup vyžaduje dva průchody vstupním souborem, ale zaručuje optimální kompresní poměr (relativně vzhledem k použité metodě), druhý přístup je rychlejší, ale může vést k horším výsledkům (například při kompresi cizojazyčného textu).

Odhadovaný počet řešitelů: 1