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

Cílem úlohy je implementace 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.

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.

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í:

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'}