Termín odevzdání | 4.12.2023 23:59 CET |
---|---|
Bodový zisk | 6b + 2b revize kódu |
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í:
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'}