====== HW06 - Bezeztrátové kódování ======

^ Termín odevzdání |  <wrap important> 4.12.2022 23:59 CET</wrap> | 
^ Bodový zisk | 6b + 2b revize kódu |

===== Zadání =====

Cílem úlohy je implementace [[https://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding|Shannonovy–Fanovy metody]] bezeztrátového kódování množiny symbolů. Shannonovo-Fanovo kódování je statistická metoda bezeztrátové komprese. Množina znaků je (např. rekursivně) dělena vždy na dvě podmnožiny, aby součet výskytů znaků v obou podmnožinách byl přibližně stejný. Jedné podmnožině je pak v kódu přiřazena binární ''1'' a druhé ''0''. 

<note tip>Další informace o bezeztrátových metodách kódování naleznete např. v této prezentaci{{ :courses:bab37zpr:hw:kasa-lec02.pdf |}}.</note>

===== Odevzdání =====

Do systému BRUTE odevzdávejte soubor pojmenovaný ''komprese.py''. V tomto souboru bude funkce ''koduj(text)''. Návratovou hodnotou funkce bude slovník (''dict''), který bude obsahovat kódy přiřazené jednotlivým symbolům a zakódovanou zprávu. 

<note tip>Symboly ve zprávě na vstupu budou z množiny malých a velkých písmen bez diakritiky, čísel a mezery.</note>

===== Příklad =====

Na vstupu je text ''26251246512326241151262''. Text je dlouhý 23 znaků, abeceda je tvořena znaky ''1'', ''2'', ''3'', ''4'', ''5'' a ''6''. 

Můžeme sestavit následující tabulku výskytů a pravděpodobností:


^ symbol | 1 | 2 | 3 | 4 | 5 | 6 |
^ četnost | 5 | 8 | 1 | 2 | 3 | 4 |
^ pravděpodobnost | 0.22 | 0.35 | 0.04 | 0.09 | 0.13 | 0.17 |  

Příklad volání funkce:

<code python>
ret = koduj('26251246512326241151262')
ret['slova']
{'2': '11', '1': '10', '6': '01', '5': '001', '4': '0001', '3': '0000'}
ret['zprava']
'1101110011011000101001101100001101110001101000110110111'}
</code>