ALG05

13.2, Kompresja danych metodą Huffmana 305

Tabela 13 - 2.

Prawdopodobieństwa występowania liter w języku polskim.

Litera	Prawdop.	Litera	Prawdop.	Litera	Prawdop.	Litera	Prawdop.
spacja	0.140	f	0.011	n	0.043	U	0.018
a	0.078	8	0.012	ń	0.001	w	0,037
a	0.10	li	0.011	0	0.061	y	0.031
b	0.012	i	0.077	ó	0.007	7	0.055
C	0.036	j	0.018	p	0.025	ż	0,008
Ć	0.004	k	0.025	r	0.037	ź	0.001
d	0.029	1	0.017	s	0.047
e	0.064	1	0.024	i	0.006
	0,013	m	0.023	t	0.029

FAZA REDUKCJI (kierunek: w dół)

1.    Uporządkować znaki kodowanego alfabetu wg malejącego prawdopodobieństwa;

2.    Zredukować alfabet poprzez połączenie dwóch najmniej prawdopodobnych znaków w jeden znak zastępczy, o prawdopodobieństwie równym sumie prawdopodobieństw łączonych znaków;

3.    Jeśli zredukowany alfabet zawiera 2 znaki (zastępcze), skok do punktu 4, w przeciwnym przypadku powrót do 2;

FAZA KONSTRUKCJI KODU (kierunek: w górę)

4.    Przyporządkować dwóm znakom zredukowanego alfabetu słów kodowych 0 i /;

5.    Dopisać na najmłodszych pozycjach słów kodowych odpowiadających dwóm najmniej prawdopodobnym znakom zredukowanego alfabetu 0 i /;

6.    Jeśli powróciliśmy do alfabetu pierwotnego, koniec algorytmu, w' przeciwnym wypadku skok do 5.

Zdaję sobie sprawę, że algorytm może wydawać się niezbyt zrozumiały, ale wszystkie jego ciemne strony powinien rozjaśnić konkretny przykład obliczeniowy, który zaraz wspólnie przeanalizujemy.

Załóżmy, że dysponujemy alfabetem składającym się z sześciu znaków: x_t, x₂, x_}. x₄, Xj i x_fr Otrzymujemy do zakodowania tekst długości 60 znaków, których częstotliwości występowania są następujące; 20, 17, 10, 9, 3 i I. Aby zakodować sześć różnych znaków, potrzeba minimum 3 bity (6<2^J), zatem zakodowany