LZSS

Z Wikipedii

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

LZSS jest nazwą słownikowej metody bezstratnej kompresji danych. LZSS jest to ulepszony wariant metody LZ77.

Nazwa metody pochodzi od nazwisk: Lempel-Ziv-Storer-Szymanski, została opracowana przez J.A. Storera i T.G. Szymanskiego i opisana w 1982 roku w Journal of the ACM, w artykule pt. "Data compression via textual substitution" (str. 928-951).

Algorytm LZSS jest używany między innymi w programach PKZIP i ARJ.

[edytuj] Algorytm kompresji

Metoda LZSS, tak samo jak LZ77, używa bufora, podzielonego na dwie części:

słownik (bufor słownikowy) - przechowującą $k$ ostatnio przetwarzanych symboli, obejmujący indeksy $0\ldots k-1$ )
bufor wejściowy (bufor kodowania) - przechowujący $n$ symboli, które mają zostać zakodowane, obejmujący indeksy $k\ldots k+n-1$ ).

Wartości $n$ i $k$ są dobierane tak, aby były potęgami dwójki. Rozmiar słownika jest dużo większy niż bufora wejściowego, w praktyce ma kilka-kilkadziesiąt kilobajtów.

W każdym kroku algorytmu w słowniku wyszukiwany jest najdłuższy podciąg równy początkowi bufora wejściowego, charakteryzowany parą ( $P \in [0\ldots k-1]$ , $C \in [2\ldots n]$ ), gdzie $P$ - indeks początku podciągu, $C$ - jego długość. Symbol w buforze następujący po dopasowanym ciągu oznaczmy jako $S$ .

Algorytm LZ77 wypisuje na wyjście trójki ( $P, C, S$ ), nawet wtedy, gdy trójka ma większą długość niż opisywaną przez nią ciąg. Algorytm LZSS wypisuje na wyjście tylko pary ( $P, C$ ), ale bierze przy tym pod uwagę fakt, czy para nie zajmuje więcej bitów niż opisywany przez nią ciąg symboli. Jeśli kodowany ciąg jest dłuższy niż para, wówczas opłaca się wypisać na wyjście parę, w przeciwnym razie na wyjście wypisywany jest tylko pierwszy symbol z bufora wejściowego $S'$ . W celu odróżnienia symbolu od pary, poprzedza się je pojedynczym bitem:

(0, $S'$ ),
(1, $P$ , $C$ ).

Formalnie algorytm kompresji przebiega następująco:

Wypełnij słownik pierwszym symbolem, wypisz ten symbol na wyjście; wypełnij bufor wejściowy $n$ pierwszymi symbolami wejściowymi.
Dopóki w buforze wejściowym są dane:
1. Wyszukaj w słowniku najdłuższy podciąg równy początkowi bufora wejściowego - wynikiem są liczby P i C.
  - Jeśli rozmiar pary ( $P$ , $C$ ) jest mniejszy od rozmiaru znalezionego podciągu, zapisz na wyjście trójkę (0, $P$ , $C$ ), przesuń cały bufor o $C$ pozycji w lewo i wprowadź do bufora wejściowego tyle samo kolejnych symboli.
  - W przeciwnym razie wypisz na wyjście parę (1, $S'$ ), przesuń cały bufor o 1 pozycję w lewo i wprowadź do bufora wejściowego kolejny symbol wejściowy.

Uwaga: ponieważ w przypadku wypisywania pary liczba $C$ nigdy nie będzie miała wartości 0 ani 1, toteż można zmniejszyć liczbę bitów wymaganą do zapisania $C$ poprzez przypisanie wartości binarnej 0 liczby 2, wartości binarnej 1 liczby 3, itd. Np. dla $n = 4$ do zapisania $C$ należałoby przeznaczyć 3 bity, a przy takim przyporządkowaniu wystarczą 2 bity.

[edytuj] Algorytm dekompresji

Do dekompresji potrzebny jest bufor o dokładnie takim samym rozmiarze jak przy kompresji; jest on podzielony na słownik ( $k$ symboli) i bufor wyjściowy ( $n$ symboli).

Wypełnij słownik pierwszym symbolem.
Dla kolejnych danych (par i trójek) powtarzaj:
1. Jeśli mamy do czynienia z trójką (0, $P$ , $C$ ) to skopiuj ze słownika na początek bufora wyjściowego symbole z zakresu $P \ldots P+C-1$ , wypisz na wyjście skopiowane symbole i przesuń cały bufor o $C$ pozycji w lewo.
2. Jeśli mamy do czynienia z dwójką (1, $S$ ) to skopiuj symbol $S$ na początek bufora wyjściowego, wypisz na wyjście ten symbol i przesuń cały bufor o jedną pozycję w lewo.

[edytuj] Przykład kompresji

Słownik i bufor wejściowy będą miały rozmiar 4 ( $n = k = 4$ ) a więc do zapisu liczby $P$ i $C$ wystarczą po 2 bity. Przyjmijmy także, że kodowane symbole to bajty (tak jest najczęściej). Wówczas:

rozmiar trójki (0,P,C) - 1+2+2 = 5 bitów;
rozmiar pary (1,S) - 1+8 = 9 bitów.

Kompresji zostanie poddany 12-elementowy ciąg aabbcabbcabd.

#	słownik\|bufor wejściowy	wyjście kodera	komentarz
1	aaaa\|aabb		słownik jest wypełniany pierwszym symbolem, bufor wejściowy pierwszymi czterema symbolami wejściowymi
2	aaaa\|aabb	(0,0,2)	w słowniku znajduje się 2-elementowy podciąg równy początkowi bufora wejściowego - jego rozmiar wynosi 16 bitów, a rozmiar trójki 5 bitów, zatem na wyjście wypisywana jest trójka, a bufor przesuwany o 2 pozycje
3	aaaa\|bbca	(1,`b`)	w słowniku nie ma ciągu rozpoczynającego się od `b`, zatem na wyjście wypisywana jest para, a bufor przesuwany o jedną pozycję
4	aaab\|bcab	(0,3,1)	w słowniku znajduje się 1-elementowy podciąg równy początkowi bufora wejściowego - jego rozmiar wynosi 8 bitów, a rozmiar trójki 5 bitów, zatem na wyjście wypisywana jest trójka, a bufor przesuwany o 1 pozycje
5	aabb\|cabb	(1,`c`)	w słowniku nie ma ciągu rozpoczynającego się od `c`, zatem na wyjście wypisywana jest para, a bufor przesuwany o jedną pozycję
6	abbc\|abbc	(0,0,4)	w słowniku znajduje się 4-elementowy podciąg równy początkowi bufora wejściowego - jego rozmiar wynosi 32 bity, a rozmiar trójki 5 bitów, zatem na wyjście wypisywana jest trójka, a bufor przesuwany o 4 pozycje
7	abbc\|abd	(0,0,2)	w słowniku (na jego początku) znajduje się 2-elementowy podciag równy początkowi bufora wejściowego; na wyjście wypisywana jest trójka, a bufor przesuwany o 2 pozycje
8	bcab\|d	(1,`d`)	w słowniku nie ma ciągu rozpoczynającego się od `d`, zatem na wyjście wypisywana jest para, a bufor przesuwany o jedną pozycję

Rozmiar danych przed kompresją: $12 \cdot 8 = 96$ bitów.

Rozmiar danych po kompresji:

symbol początkowy: 8 bitów.
trzy pary: $3 \cdot 9 = 27$ bitów,
cztery trójki: $4 \cdot 5 = 20$ bitów.

W sumie 55 bitów, co daje współczynnik kompresji ok. 42%.

[edytuj] Przykład dekompresji

Zostaną zdekompresowane dane z poprzedniego przykładu.

#	wejście dekodera	słownik\|bufor wejściowy	wyjście dekodera	komentarz
1	a	aaaa\|		wypełnienie słownika pierwszym symbolem
2	(0,0,2)	aaaa\|aa	aa	skopiowanie do bufora wyjściowego i na wyjście 2-elementowego ciągu; przesunięcie całego bufora o 2 pozycje w lewo
3	(1,`b`)	aaaa\|b	b	dopisanie do bufora wyjściowego symbolu, wypisanie go na wyjście i przesunięcie całego bufora o jedną pozycję w lewo
4	(0,3,1)	aaab\|b	b	skopiowanie do bufora wyjściowego i na wyjście 1-elementowego ciągu; przesunięcie całego bufora o 1 pozycje w lewo
5	(1,`c`)	aabb\|c	c	dopisanie do bufora wyjściowego symbolu, wypisanie go na wyjście i przesunięcie całego bufora o jedną pozycję w lewo
6	(0,0,3)	abbc\|abb	abb	skopiowanie do bufora wyjściowego i na wyjście 3-elementowego ciągu; przesunięcie całego bufora o 3 pozycje w lewo
7	(0,0,3)	cabb\|cab	cab	jw.
8	(1,`d`)	bcab\|d	d	dopisanie do bufora wyjściowego symbolu, wypisanie go na wyjście i przesunięcie całego bufora o jedną pozycję w lewo