Kódování: Cvičení k tvorbě efektivního prefixového kódu

4. Nerovnoměrné kódy

4.6. Cvičení k tvorbě efektivního prefixového kódu

Znáte pravděpodobnost výskytu jednotlivých znaků: K = 14 %, Y = 19 %, N = 9 %, Ž = 6 %, V = 11 %, A = 24 %, R = 5 %, T = 12 %.

Vytvořte efektivní prefixový kód Shannon-Fano metodou a spočítejte průměrnou délku kódového slova a efektivnost.
Vytvořte efektivní prefixový kód Huffmanovou metodou a spočítejte průměrnou délku kódového slova a efektivnost.

Tipy pro řešení

Jak postupovat naleznete v předchozích studijních kapitolách. Pokud je u Shannon-Fano metody v nějaké fázi nejednoznačné dělení, stojí za to si vyzkoušet postupně obě možnosti a výpočtem vlastností porovnat, které bylo lepší uskutečnit. Totéž platí pro Huffmanovu metodu, pokud by došlo na nejasné řazení.

Návrh řešení

Na návrh řešení se podívejte, až se pokusíte vytvořit efektivní kód alespoň jedním způsobem u každé z metod.

1. Jak může vypadat tvorba kódu se zadanými pravděpodobnostmi Shannon-Fano metodou?

        A = 24 % | 1 | 1
                   ----
        Y = 19 % | 1 | 0
           ----
    K = 14 % | 0 | 1 | 1
                      ----
    T = 12 % | 0 | 1 | 0
       ----
V = 11 % | 0 | 0 | 1 | 1
                      ----
N =  9 % | 0 | 0 | 1 | 0
              ----
Ž =  6 % | 0 | 0 | 0 | 1
                      ----
R =  5 % | 0 | 0 | 0 | 0

Průměrnou délku kódového slova zjistíte dosazením do vzorce, protože znáte délku kódových slov i pravděpodobnost znaků, kterým odpovídají: 2 × 0,24 + 2 × 0,19 + 3 × 0,14 + 3 × 0,12 + 4 × 0,11 + 4 × 0,09 + 4 × 0,06 + 4 × 0,05 + = 2,88 b.
Efektivnost kódu opět spočtete po dosazení do vzorce $-\frac{0,24 × log_2 0,24 + 0,19 × log_2 0,19 + 0,14 × log_2 0,14 + 0,12 × log_2 0,12 + 0,11 × log_2 0,11 + 0,09 × log_2 0,09 + 0,06 × log_2 0,06 + 0,05 × log_2 0,05}{2,88} = 0,9847600312$ , což je po vynásobení 100 přibližně 98,48 %.

Shannon-Fano metoda Kynžvart.
Obr. 21: Shannon-Fano metoda a jiný způsob řešení binárním stromem. (Zdroj vlastní)

2. Jak může vypadat tvorba kódu se zadanými pravděpodobnostmi Huffmanovou metodou?

Tab. 3: Huffmanova metoda, postupné sčítání. (Zdroj vlastní)

Zdrojové znaky	[%]	Po prvním součtu	[%]	Po druhém součtu	[%]	Po třetím součtu	[%]	Po čtvrtém součtu	[%]	Po pátém součtu	[%]	Po šestém součtu	[%]	Konečný součet	[%]
A	24	A	24	A	24	A	24	YK	33	ŽRTVN	43	YKA	57	YKAŽRTVN	100
Y	19	Y	19	VN	20	ŽRT	23	A	24	YK	33	ŽRTVN	43
K	14	K	14	Y	19	VN	20	ŽRT	23	A	24
T	12	T	12	K	14	Y	19	VN	20
V	11	ŽR	11	T	12	K	14
N	9	V	11	ŽR	11
Ž	6	N	9
R	5

Tab. 4: Huffmanova metoda, přidělování slov. (Zdroj vlastní)

Zdrojové znaky	Bity	Po prvním součtu	Bity	Po druhém součtu	Bity	Po třetím součtu	Bity	Po čtvrtém součtu	Bity	Po pátém součtu	Bity	Po šestém součtu	Bity	Konečný součet	[%]
A	01	A	01	A	01	A	01	YK	00	ŽRTVN	1	YKA	0	YKAŽRTVN	100
Y	000	Y	000	VN	11	ŽRT	10	A	01	YK	00	ŽRTVN	1
K	001	K	001	Y	000	VN	11	ŽRT	10	A	01
T	100	T	100	K	001	Y	000	VN	11
V	110	ŽR	101	T	100	K	001
N	111	V	110	ŽR	101
Ž	1010	N	111
R	1011

Průměrnou délku kódového slova zjistíte dosazením do vzorce, protože znáte délku kódových slov i pravděpodobnost znaků, kterým odpovídají: 2 × 0,24 + 3 × 0,19 + 3 × 0,14 + 3 × 0,12 + 3 × 0,11 + 3 × 0,09 + 4 × 0,06 + 4 × 0,05 + = 2,87 b.
Efektivnost kódu opět spočtete po dosazení do vzorce $-\frac{0,24 × log_2 0,24 + 0,19 × log_2 0,19 + 0,14 × log_2 0,14 + 0,12 × log_2 0,12 + 0,11 × log_2 0,11 + 0,09 × log_2 0,09 + 0,06 × log_2 0,06 + 0,05 × log_2 0,05}{2,87} = 0,9881912508$ , což je po vynásobení 100 přibližně 98,82 %.

Huffman Kynžvart
Obr. 22: Binární strom Huffmanova kódování. (Zdroj vlastní)