====== HW06 - Bezeztrátové kódování ======
^ Termín odevzdání | 2.12.2024 23:59 CET |
^ 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''.
Další informace o bezeztrátových metodách kódování naleznete např. v této prezentaci{{ :courses:bab37zpr:hw:kasa-lec02.pdf |}}.
===== 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.
Symboly ve zprávě na vstupu budou z množiny malých a velkých písmen bez diakritiky, čísel a mezery.
===== 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:
ret = koduj('26251246512326241151262')
ret['slova']
{'2': '11', '1': '10', '6': '01', '5': '001', '4': '0001', '3': '0000'}
ret['zprava']
'1101110011011000101001101100001101110001101000110110111'}