----
{{:16.4slownikowe_metody_kompresji.pdf|: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 ====
[[http://pl.wikipedia.org/wiki/LZSS|Algorytm LZSS]]

==== Wykład ====

[[http://mars.iti.pk.edu.pl/~chmaj/MM/w06.pdf|Słownikowe metody kompresji]]


==== Dokładny opis wybranych algorytmów (ang.) ====
  * [[http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz77.html|LZ77]]
  * [[http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz78.html|LZ78]]
  * [[http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html|LZW]]


