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

Termín odevzdání 4.12.2022 23:59 CET
Bodový zisk 6b + 2b revize kódu

Zadá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.

Další informace o bezeztrátových metodách kódování naleznete např. v této prezentacikasa-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'}

courses/bab37zpr/hw/hw06.txt · Last modified: 2022/11/14 12:54 by viteks