ALG4

154 Rozdział 5. Struktury danych

weźmy pod uwagę następującą grupę słów: KROKUS, KROSNO, KRAWIEC, KROKODYL, KRAJ. Gdyby można było zapamiętać je w pamięci w fomiie drzewa przedstawionego na rysunku 5 - 25, to problem kompresji mielibyśmy z głowy. Z 31 znaków do zapamiętania zrobiło nam się raptem 21. co może nie oszałamia, ale pozwala przypuszczać, że w przypadku rozbudowanych słowników zysk byłby jeszcze większy. Zakładamy oczywiście, że w słowniku będą zapamiętywane w dużej części serie słów zaczynających się od tych samych liter-czyli przykładowo pełne odmiany rzeczowników etc.

K

V

R

K""' i

A	o
i	*	*		—-—»
W	w	K		s
¥	¥	V		¥
1	A	o	U	N
;		V	i	i
E		D	s	O
i		¥
c		Y
		V
		L

Rys. 5 - 25.

Kompresju danych zaletą Uniwersalnej Struktury Słownikowej.

Pora już na przedstawienie owej tajemniczej USS w szczegółach. Jej realizacja jest nieco przewrotna, bowiem zbędne staje się zapamiętywanie słów' i ich fragmentów, a pomimo tego cel i tak zostaje osiągnięty!

Program zaprezentuję w szczegółowo skomentowanych fragmentach. Oto pierwszy z nich zawierający programową realizacją USS:

uss.cpp

const int n=29; // liczba rozpoznawanych liter

typedof struct słownik

<

struct słownik *tlnj;

)USS,*USS_PTR;

Mamy oto typową dla C++ deklarację typu rekurencyjnego, którego jedynym elementem jest tablica wskaźników do tegoż właśnie typu. (Tak, zdaję sobie spraw⁽ę, iż brzmi to okropnie). Literze 'a’ (lub ‘A’) odpowiada komórka t[0]. analogicznie literom ‘z’ (lub ‘Z’) komórka t[25]. Dodatkowe komórki pamięci będą służyły do znaków specjalnych, które nie należą do podstawowych liter alfabetu, ale dość często wchodzą w skład słów (np. myślnik, polskie znaki diakrytyczne...).