LZ78

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

LZ78 jest nazwą słownikowej metody bezstratnej kompresji danych. Została opracowana w 1978 roku przez J. Ziva i A. Lempela i opisana w IEEE Transactions on Information Theory, w artykule pt. "Compression of individual sequences via variable-rate encoding" (str. 530-536).

Kompresja polega na zastępowaniu ciągów symboli indeksami do słownika przechowującego ciągi symboli, które wcześniej wystąpiły w kompresowanych danych. Dzięki temu wielokrotnie powtarzające się ciągi symboli (np. te same słowa w tekście) są zastępowane o wiele krótszymi indeksami (liczbami).

Panowie Ziv i Lempel rok wcześniej opracowali metodę LZ77, w której słownik miał stałą wielkość, co powodowało, że jego zawartość zmieniała się cały czas wraz z napływaniem nowych danych. Skutkiem tego, jeśli na wejściu powtórzył się pewien ciąg, który co prawda występował wcześniej, ale w słowniku już go nie było, musiał zostać zapamiętany raz jeszcze.

Ogólnie metoda LZ78 jest bardzo zbliżona do LZ77, z tym jednak wyjątkiem, że słownik jest rozszerzany w miarę potrzeb i żaden ciąg występujący w przetwarzanych już danych nie jest "zapominany". Dzięki temu uzyskuje się lepszy współczynnik kompresji kosztem skomplikowania dostępu do słownika. W LZ77 słownik jest zwykłą tablicą, w LZ78 - ze względu na szybkość dostępu do poszczególnych słów - realizowany jest jako drzewo (binarne, trie) albo tablica haszująca.

Dużą zaletą metody, jest to, że potencjalnie bardzo dużego słownika w ogóle nie trzeba zapamiętywać - zostanie on odtworzony przez dekoder na podstawie zakodowanych danych (patrz: przykład dekompresji). Jednak pewną wadą jest praktycznie jednakowa złożność kodu kompresującego i dekompresującego.

W praktyce najpowszechniej używany jest wariant LZ78 nazywany LZW.

[edytuj] Algorytm kompresji

Kompresowany jest ciąg $S$ zawierający $n$ symboli.

Wyczyść słownik.
$i : = 0$ ( $i$ - indeks pierwszego, nieprzetworzonego symolu w $S$ ).
Dopóki i < n wykonuj:
1. Wyszukaj w słowniku najdłuższy podciąg równy początkowi nieprzetworzonych jeszcze symboli (podciąg ).
  - Jeśli udało się znaleźć taki podciąg, to wynikiem wyszukiwania jest jego indeks $k$ w słowniku; dodatkowo słowo wskazywane przez ten indeks ma pewną długość $m$ . Na wyjście wypisz parę (indeks, pierwszy niedopasowany symbol), czyli ( $k$ , $S [i + m]$ ) oraz dodaj do słownika znaleziony podciąg przedłużony o symbol $S [i + m]$ (innymi słowy podciąg $S[i\ldots i+m]$ ). Zwiększ $i : = i + m$ .
  - Jeśli nie udało się znaleźć żadnego podciągu, to znaczy, że w słowniku nie ma jeszcze symbolu $S [i]$ . Wówczas do słownika dodawany jest ten symbol, a na wyjście wypisywana para ( $0$ , $S [i]$ ). Indeks 0 jest tutaj umowny, w ogólnym przypadku chodzi o jakąś wyróżnioną liczbę. Zwiększ $i$ o jeden!

[edytuj] Algorytm dekompresji

Wyczyść słownik.
Dla wszystkich par (indeks, symbol - ozn. k, s) wykonuj:
1. Jeśli $k = 0$ dodaj symbol $s$ do słownika. Na wyjście wypisz symbol $s$ .
2. Jeśli $k > 0$ weź ze słownika słowo $w$ spod indeksu $k$ . Na wyjście wypisz słowo $w$ oraz symbol $s$ . Do słownika pod kolejnym indeksem dodaj słowo $w + s$ .

[edytuj] Przykład kompresji

Zostanie skompresowany ciąg: abbbcaabbcbbcaaac.

wejście	wyjście	SŁOWNIK		komentarz
wejście	wyjście	indeks	słowo	komentarz
`a`	(0,`a`)	1	`a`	w słowniku nie ma symbolu `a`
`b`	(0,`b`)	2	`b`	w słowniku nie ma symbolu `b`
`bb`	(2,`b`)	3	`bb`	w słowniku jest ciąg `b` (indeks 2), nie ma natomiast `bb`; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo `bb`
`c`	(0,`c`)	4	`c`	w słowniku nie ma symbolu `c`
`aa`	(1,`a`)	5	`aa`	w słowniku jest ciąg `a` (indeks 1), nie ma natomiast `aa`; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo `aa`
`bbc`	(3,`c`)	6	`bbc`	w słowniku jest ciąg `bb` (indeks 3), nie ma natomiast `bbc`; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo `bbc`
`bbca`	(6,`a`)	7	`bbca`	w słowniku jest ciąg `bbc` (indeks 6), nie ma natomiast `bbca`; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo `bbca`
`aac`	(5,`c`)	8	`aac`	w słowniku jest ciąg `aa` (indeks 5), nie ma natomiast `aac`; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo `aac`

Można zauważyć, że do słownika dodawane są coraz dłuższe słowa.

[edytuj] Przykład dekompresji

Zostaną zdekompresowane dane z poprzedniego przykładu.

wejście	wyjście	SŁOWNIK		komentarz
wejście	wyjście	indeks	słowo	komentarz
(0,`a`)	`a`	1	`a`	symbol `a` jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy `a`
(0,`b`)	`b`	2	`b`	symbol `b` jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy `b`
(2,`b`)	`bb`	3	`bb`	na wyjście wypisywane jest słowo `b` ze słownika (indeks 2), wypisywany jest także symbol `b`; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 2. i symbolu: `bb`
(0,`c`)	`c`	4	`c`	symbol `c` jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy `c`
(1,`a`)	`aa`	5	`aa`	na wyjście wypisywane jest słowo `a` ze słownika (indeks 1), wypisywany jest także symbol `a`; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 1. i symbolu: `aa`
(3,`c`)	`bbc`	6	`bbc`	na wyjście wypisywane jest słowo `bb` ze słownika (indeks 3), wypisywany jest także symbol `c`; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 2. i symbolu: `bbc`
(6,`a`)	`bbca`	7	`bbca`	na wyjście wypisywane jest słowo `bbc` ze słownika (indeks 6), wypisywany jest także symbol `a`; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 6. i symbolu: `bbca`
(5,`c`)	`aac`	8	`aac`	na wyjście wypisywane jest słowo `aa` ze słownika (indeks 5), wypisywany jest także symbol `c`; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 5. i symbolu: `aac`