slownikowe_metody_kompresji_danych [mgr Wiki]

[[slownikowe_metody_kompresji_danych]]
mgr Wiki

:16.4slownikowe_metody_kompresji.pdf

### Definicja

Metody słownikowe wykorzystują słownik zawierający możliwe ciągi znaków (np. słowa w kompresji tekstu). Każde słowo z sekwencji wejściowej jest zamieniane na indeks w słowniku.

#### Istnieją dwie metody budowania słownika

- statyczna – słownik ustalamy przed kompresją
- dynamiczna – słownik tworzony jest w czasie kompresji

Istnieje konieczność poprawnej obsługi sytuacji, gdy nie ma słowa w słowniku.

### Metoda statyczna

- wszystkie możliwe słowa znajdują się w słowniku
- dla każdego słowa wyprowadzana jest na wyjście jego pozycja w słowniku
- jeśli słowo nie występuje w słowniku, to wyprowadzamy je, przepisując na wyjście
- przechowanie na początku słownika wyrazów najczęściej występujących pozwala na ich kodowanie za pomocą niewielkiej liczby bitów

#### Zalety:

- szybka kompresja

#### Wady:

- konieczność stworzenia słownika przed kompresją
- jeśli dane zawierają słowa nie występujące w słowniku, to zamiast kompresji możemy otrzymać ekspansję danych

### Metoda dynamiczna

- na początku słownik jest pusty
- na wyjście wyprowadzany jest indeks słowa w słowniku, jeśli znajduje się ono w nim, lub to słowo, jeśli nie ma go w słowniku
- jeśli kompresowane jest słowo, nie znajdujące się w słowniku, to jest ono następnie do niego wstawiane

#### Zalety:

- zawartość słownika dopasowuje się do kompresowanej sekwencji (słownik nie zawiera niepotrzebnych słów)
- metoda dopasowuje się do danych (niezależnie od języka)

#### Wady:

- wolniejsze działanie od metody statycznej z powodu konieczności ciągłej aktualizacji słownika

### Przykładowy algorytm

Algorytm LZSS

### Wykład

Słownikowe metody kompresji

### Dokładny opis wybranych algorytmów (ang.)

- LZ77
- LZ78
- LZW

slownikowe_metody_kompresji_danych.txt · Last modified: 2006/05/19 13:44 by 213.134.172.237