Podręcznik

6.3. Algorytmy słownikowe

Jak już wspomnieliśmy w zagadnieniach związanych z kompresją danych bardzo ważny jest model matematyczny generacji danych. Algorytmy słownikowe kompresji należą do metod kompresji wykorzystujących cechy strukturalne występujące w danych. Algorytmy słownikowe dzielimy na dwie grupy:

• algorytmy ze statycznym słownikiem
• algorytmy z dynamicznym słownikiem

Istotę algorytmów słownikowych wyjaśnia następujący przykład. Załóżmy, ze dany jest tekst złożony ze słów 4 literowych i każde słowo składa się z czterech znaków. Alfabet, w którym zapisujemy tekst, składa się z 26 małych liter i znaków przestankowych, co daje w sumie 32 znaki (5 bitów na znak). Jeśli wybierzemy ze słów 4 znakowych najczęściej spotykane słowa (np. 256 słów) i umieścimy je w słowniku, to możemy postępować tak:

Analizujemy słowa 4 znakowe (dzielimy cały tekst kompresowany na 4 znakowe bloki) jeśli dane słowo znajduje się w słowniku to przesyłamy tylko jeden bit stwierdzający fakt znalezienia słowa w słowniku i pozycję słowa w słowniku (8 bitów). W sumie więc 9 bitów. Jeśli nie znaleźliśmy słowa w słowniku to 4 znakowe słowo kodujemy tak: jeden bit stwierdzający że słowo jest spoza słownika oraz 4 słowa 5 bitowe kodujące znaki z naszego alfabetu (w sumie 21 bitów).

Efektywność takiego kodowania będzie zależeć od tego, jaki odsetek słów analizowanych znajduje się słowniku.

Jeśli prawdopodobieństwo wystąpienia wzorca ze słownika jest równe p, to średnia liczba bitów poświęcanych na zapis 4 znakowego fragmentu tekstu wyraża się następująco:

L  9 p  21(1  p)  21  12 p

Gdybyśmy nie stosowali powyższego algorytmu to każdy 4 znakowy fragment tekstu zabierałby 20 bitów.

Oczywiście w powyższym schemacie kodowania efekt będzie tym lepszy, im większe jest prawdopodobieństwo p znalezienia wzorca w słowniku.

Popularne pakiety kompresji danych takie jak PKZip, Zip, gzip i ARJ używają algorytmów słownikowych opartych na LZ77. Inne znane słownikowe algorytmy kompresji to m.in. algorytmy LZ 77, LZ 78 (litery LZ są tu skrótem od nazwisk Lempel, Ziv), EZW itd. Powszechnie stosowanym algorytmem kompresji jest również algorytm LZW (Lempel-Ziv- Welch) należący do klasy algorytmów typu LZ 78.

Znane z systemu operacyjnego Unix polecenie compress, specyfikacja V.42.bis wykorzystywana w modemach oraz standard GIF (Graphics Interchange Format) są kolejnymi przykładami zastosowania metod słownikowych kompresji.